麻花辮（Braid）

04-24

題圖來自網路，紀念我在Street Fighter中最喜歡的角色——有著麻花辮的滿天飛的「叉子」。

「你那美麗的麻花辮/纏呀纏住我心田/叫我日夜地想念/那段天真的童年」

——鄭智化《麻花辮子》

麻花辮子-鄭智化-單曲-酷我音樂-好音質用酷我?

bd.kuwo.cn

麻花辮是一種髮型，把頭髮分成三股交叉紮起來像麻花樣的辮子：

1. 把頭髮分成三股；2. 把最左邊（右邊）一股頭髮從上面壓到中間一股和右邊（左邊）一股之間（下圖(1)、(3)）；3. 如果還需要繼續編辮子則再把最（右邊）一股頭髮的頭髮從上面壓到中間一股和左邊（右邊）一股之間（下圖(2)、(4)）；4. 如果還需要繼續編辮子則返回步驟2。5. 最後頭髮編完，用頭繩（或皮筋、綁線帶、鐵絲、包裝繩、米線、502等）扎住（下圖(5)）。

https://www.zhihu.com/video/967520392194236416

但為什麼無論古今中外，編麻花辮的方法如此單一，都是上述操作序列不斷重複（或者左右鏡像）？

要分析這個問題，先從最簡單的入手：

（一）頭髮只分為一股，梳為馬尾辮即可。

（二）次簡單的：如果頭髮只分為兩股，則只有下圖所示一種編辮子方式（或者左右鏡像），實際上就是搓麻繩的方法。

這是為什麼呢？

再在這個問題中討論最簡單情況——頭髮只分為兩股時交叉0次或1次，如下圖所示，三種情況分別記為 $e$ 、 $a$ 和 $b$ 。

下面來看交叉至多2次的情況，如下圖所示是上圖的9種組合形式，採用?表示「上下連接」。

然後拉一拉、拽一拽、抻一抻、抖一抖，會發現：

$ecirc e=e$ 、 $ecirc a=a$ 、 $ecirc b=b$ 、 $acirc e=a$ 、 $bcirc e=b$ 、 $acirc b=e$ 、 $bcirc a=e$ 。因此可以將「?」視作 $G$ 上的可交換的運算，其中 $G$ ={所有由 $e$ 、 $a$ 、 $b$ 組成的有限長度的串，字元之間的連接表示「?」}。

於是，只要有「 $acirc b$ 」就可以「消去」、只要有「 $bcirc a$ 」也可以「消去」。例如： $aeabbaaebaa= ae(ab)(ba)ae(ba)a$ 等同於 $a^3$ ，可參看下圖：

於是，「兩股辮子」或者就是 $e$ 、或者就是連續的 $a$ 、或者就是連續的 $b$ ，得到 $G={e}∪{a^i|iinmathbb{Z^+}}∪{b^i|iinmathbb{Z^+}} ={a^i|iinmathbb{Z}}$

$={dots,a^{-3}=b^3,a^{-2}=b^2,a^{-1}=b,a^{0}=e,a^1,a^2,a^3,dots}$ 。

【用「群」的語言就是： $(G, circ)$ 構成一個群，其中 $e$ 是單位元、 $a$ 和 $b$ 互為逆。事實上 $G$ 是一個循環群，生成元是 $a$ 或 $b$ 。】

其中 $a^i$ 中 $i$ 的正負就對應「編麻繩」的兩種（對稱）方式， $i=0$ 時就是「不編」。

也就是說，兩股頭髮時，或者不編，或者必然是「編麻繩」。

下面我們來看三股頭髮的情形：

最簡單的情況（交叉0次或1次）有5種情況：

依然令 $G$ ={所有由 $e$ 、 $a$ 、 $a^{-1}$ 、 $b$ 、 $b^{-1}$ 組成的有限長度的串，字元之間的連接表示「 $circ$ 」}。

【 $(G, circ)$ 同樣構成一個群。】

下面來分析頭髮分為三股時，「通常意義上的美觀」的辮子會是什麼樣子，考察「辮子」其實也就是考察 $G$ 中的一個有限長度的串 $S$ 。

（一）首先假定 $S$ 中不會連續出現「 $acirc a^{-1}$ 」、「 $a^{-1}circ a$ 」、「 $bcirc b^{-1}$ 」和「 $b^{-1}circ b$ 」（否則可以拉一拉、拽一拽、抻一抻、抖一抖而「消去」）。

（二）為了辮子的美觀，盡量避免出現 $a^2$ 、 $(a-1)^2$ 、 $b^2$ 或 $(b-1)^2$ 的情況（否則會出現「一邊單股，另一邊搓麻繩」的情況）：

（三）由前兩個假設可知，沒有兩個 $b$ 或 $b^{-1}$ 相連、也沒有兩個 $a$ 或 $a^{-1}$ 相連，所以「通常意義上的美觀」的辮子應該是 $b$ 或 $b^{-1}$ 、 $a$ 或 $a^{-1}$ 交錯形成的有限長度的串。

而後，可以驗證：

$aba^{-1} = ba^{-1}b^{-1}$ ，

$ab^{-1}a^{-1} = bab^{-1}$ ，

$a^{-1}ba = b^{-1}a^{-1}b$ ，

$a^{-1}b^{-1}a = b^{-1}ab$ ，

$ab^{-1}a = b^{-1}ab^{-1}$ ，

$a^{-1}ba^{-1} = ba^{-1}b$ 。

例如，對於「 $a^{-1}b^{-1}a = b^{-1}ab$ 」，可以參看下圖，其中左圖和中圖實質上都是右圖。

於是可以得到：

$abab^{-1} = a(ab^{-1}a^{-1}) = a^2b^{-1}a^{-1}$ —— （出現了 $a^2$ ）；

$aba^{-1}b = a(a^{-1}ba^{-1}) = ba^{-1}$ —— （串的長度縮短）；

$aba^{-1}b^{-1} = a(aba^{-1}) = a^2ba^{-1}$ —— （出現了 $a^2$ ）；

……

例如下圖表示 $b^{-1}a^{-1}ba^{-1} = a^{-1}baa^{-1} = a^{-1}b$ ，其中左圖和中圖實質上都是右圖。

最終可以得到 ${a^{i_1}b{j_1}a^{i_2} b^{j_2},b^{j_1}a^{i_1}b^{j_2}a^{i_2}, i_k, j_k= pm1}$ 共32個元素（串）中，除了 ${abab, a^{-1}b^{-1}a^{-1}b^{-1}, baba, b^{-1}a^{-1}b^{-1}a^{-1}}$ 外，其他28個串或者（等價地）將會出現 $a^2$ 、 $b^2$ 、 $(a^{-1})^2$ 和 $(b^{-1})^2$ 的情況；或者串可以化簡變短。

綜合上述討論，可以看出，如果編辮子中的「交叉」數至少是4的話（在現實中，這是一個合理的條件），「通常意義上的美觀」的辮子就是 ${(ab)^n, (ab)^na, (ba)^n, (ba)^nb, (a^{-1}b^{-1})^n, (a^{-1}b^{-1})^na^{-1}, (b^{-1}a^{-1})^n, (b^{-1}a^{-1})^nb^{-1}, ngeq 2}$ 。

通俗地講就是：

$a$ 、 $b$ 交替出現的串——對應之前描述的編麻花辮方法（或者左右鏡像方法）；或者是
$a^{-1}$ 、 $b^{-1}$ 交替出現的串——對應之前描述的編麻花辮方法的前後翻轉（也即將「壓住另一股頭髮」改為「被另一股頭髮壓住」，本質上沒有區別，但是在「編」辮子時會感覺不順手）。

所以，無論古今中外，編「通常意義上的美觀」麻花辮的方法只能如此單一！

最後，辮子群在公鑰密碼學中具有非常重要的地位和價值，只是它不適於在這個專欄介紹了——現在世面上密碼學的教材介紹橢圓曲線密碼體制（ECC）的都不算多，更何況辮群密碼體制。