時鐘加法

指針指向9
前進 6 格之後，會指向哪裡？

9 + 6 = 15

但是，時鐘上沒有15這個數字。
結果：指向 3

(9 + 6) % 12 = 3

時鐘乘法

5 x 3　 指針會指向哪裡？
乘法就是「重複做加法」、每次加一樣的數字

(5 + 5 + 5) % 12 = 3
(5 * 3) % 12 = 3

時鐘乘法(大數字)

121 x 125 指針會指向哪裡呢？
有兩種算法

1. 直接用乘法
   　　(121 * 125) % 12 = 5

2. 各自取餘數 → 餘數互乘 → 再取餘數
   　　(121 % 12) * (125 % 12) % 12 = 5

　　指針指向121，相當於指向 (121 % 12)這個數字
　　從起點前進125次，相當於前進 (125 % 12)次

時鐘乘法(負數)

-1 x 3 指針會指向哪裡呢？

-1 就是：數字12 往後退 1 步的那個數字，
12 + (-1) = 11

-1 * 3 相當於 (11 * 3) % 12 = 9

====================
-1 * 3 = -3

-3 就是：數字12 往後退 3 步的那個數字，
12 + (-3) = 9

-1 x -3 指針會指向哪裡呢？

-1 就是：數字12 往後退 1 步的那個數字，
　　12 + (-1) = 11

-3 就是：移動 9 次
　　12 + (-3) = 9
　　in [時鐘size 12] , 移動 9 次 = 移動 (9 + 12)次 = 移動 (9 + 2*12)次
　　　　　　　　　　　　移動 9 次 = 移動 (9 - 12)次 = 移動 (9 - 2*12)次

-1 * -3 相當於 11 * 9
(11 * 9) % 12 = 3

-1 * -3 = 3

時鐘次方

指針會指向哪裡？

次方就是「重複做乘法」，每次都乘一樣的數字
(2 * 2 * 2 * 2 * 2) % 12 = 8

指針會指向哪裡？

有五種算法：

1. 先計算小括弧裡面
   　　 = 　然後除以12，取餘數

2. 先把指數相乘
   　　 = 　　 然後除以12，取餘數

3. 先把()的餘數算出來
   　　　 →　 　→　 　→　 →　1

4. 規律：
   　　數字7　in　[時鐘size 12]
   　　　　次方 1　2　3　4　5　6
   　　　　餘數 7　1　7　1　7　1

　　7的奇數次方(1、3、5、…)在[時鐘size 12]會指向 7
　　7的偶數次方(2、4、6、…)在[時鐘size 12]會指向 1
　　所以，在[時鐘size 12]會指向 1

5. 根據的餘數
   　　如果知道 的餘數是 7
   　　那麼，的餘數，就是 7 * (7) % 12

　　如果知道 的餘數是 1
　　那麼，的餘數，就是 1 * (7 * 7) % 12

時鐘乘法 - 只會指向那些數字

時鐘size 12 的質因數分解 =

時鐘上的數字分成兩類：
　　和 12的因數「部份相同」or「完全相同」：2、3、4、6、8、9、10、12
　　　　2 乘以某數 → 2的倍數(2、4、6、8、10、12)
　　　　3 乘以某數 → 3的倍數(3、6、9、12)
　　　　4 乘以某數 → 4的倍數(4、8、12)
　　　　6 乘以某數 → 6的倍數(6、12)
　　　　8 乘以某數 → 4的倍數(4、8、12)　　　　　　　(注意這裡)
　　　　9 乘以某數 → 3的倍數(3、6、9、12)　　　　　 (注意這裡)
　　　　10乘以某數 → 2的倍數(2、4、6、8、10、12)　　 (注意這裡)
　　　　12乘以某數 → 12的倍數(12)

　　　　指向的數字，是它和 12 的「最大公因數」的倍數
　　　　不會指向數字 1

　　和 12的因數「完全不同」(除了 因數1 之外)(互質)：1、5、7、11
　　　　1 乘以某數 → 所有數字
　　　　5 乘以某數 → 所有數字
　　　　7 乘以某數 → 所有數字
　　　　11乘以某數 → 所有數字

　　　　「與時鐘size 互質之數」x 「與時鐘size 互質之數」
　　　　有機會指向數字 1

最大公因數

用「因數」來組成數字

　　8 = 1 x 8 = 2 x 4
　　8的因數是 1、2、4、8

　　12 = 1 x 12 = 2 x 6 = 3 x 4
　　12的因數是 1、2、3、4、6、12

最大公因數：兩個數字的「最大」「相同」「因數」

　　8 和 12 的最大公因數：4

如何知道「最大公因數」是哪一個數字

方法 1：
　　把 8 和 12 的因數都列出來，
　　找「最大」「相同」的那一個

方法 2：
　　理解 8 和 12 可以用 「最大公因數 4」 組成
　　8 和 12 的「差」，也可以用「最大公因數 4」 組成

　　　　8 = 4 x 2
　　　　12 = 4 x 3
　　
　　　　12 - 8 = 4
　　　　　　　 = 4 x 1

輾轉相除法(歐幾里得算法) - 使用除法

求 130 和 30 的最大公因數

130 - 30 = 100
與其找「130 和 30 的最大公因數」，不如找「100 和 30 的最大公因數」

100 - 30 = 70
與其找「100 和 30 的最大公因數」，不如找「70 和 30 的最大公因數」

70 - 30 = 40
與其找「70 和 30 的最大公因數」，不如找「40 和 30 的最大公因數」

40 - 30 = 10
與其找「40 和 30 的最大公因數」，不如找「30 和 10 的最大公因數」

用減法有點慢。直接用除法
130 % 30 = 10
與其找「130 和 30 的最大公因數」，不如找「30 和 10 的最大公因數」
　　

輾轉相除法(歐幾里得算法)的例子

a = 240
b = 46

240 % 46 = 10
46 % 10 = 6
10 % 6 = 4
6 % 4 = 2
4 % 2 = 0
當餘數為 0，除數 2 就是240 和 46 的最大公因數

觀察上面式子，可以發現：
　　餘數：向左進化成「除數」
　　除數：向左進化成「被除數」

擴展歐幾里得算法

原本的被除數240、除數46也是「餘數」
所以，可以寫成以下式子

L % M = 240
　　與其找「L 和 M 的最大公因數」，不如找「M 和 240 的最大公因數」

M % 240 = 46
　　與其找「M 和 240 的最大公因數」，不如找「240 和 46 的最大公因數」

240 % 46 = 10
46 % 10 = 6
10 % 6 = 4
6 % 4 = 2
4 % 2 = 0

=================================
每代餘數都可以表示成：
　　240*s + 46*t = 餘數
　　240的幾倍 + 46的幾倍 = 餘數

1代餘數：　 240*1 + 46*0 = 240　→ 240* + 46* = 240
2代餘數：　 240*0 + 46*1 = 46　 → 240* + 46* = 46

　　　　到代表「商」(負數)
3代餘數：　 240 + *46 = 10　　→ (1代餘數) + *(2代餘數) = 10
　　　　　　　　　　　　　　　　　　　　↓ 穢土轉生

　　　　　　　　　　　　　　　　(240* + 46*) + *(240* + 46*) = 10
　　　　　　　　　　　　　　　　240*( + *) + 46*( + *) = 10
　　　　　　　　　　　　　　　　　　　　↓
　　　　　　　　　　　　　　　　240* + 46* = 10
　　　　　　　　　　　　　　　　　　( 可以用 計算出來)

4代餘數：　 46 + *10 = 6　　　→ (2代餘數) + *(3代餘數) = 6
5代餘數：　 10 + *6　= 4　　　→ (3代餘數) + *(4代餘數) = 4
6代餘數：　　6 + *4　= 2　　　→ (4代餘數) + *(5代餘數) = 2
7代餘數：　　4 + *2　= 0　　　→ (5代餘數) + *(6代餘數) = 0

最後會得到：
　　240*(-9) + 46*(47) = 2
　　「240的幾倍」+「46的幾倍」= 最大公因數

意思(1)：
　　46 是[時鐘 size 240]上的一個數字
　　「前進」 47 次(總共轉了 9 圈)
　　最後指向「數字 2」

　　or
　　240 是[時鐘 size 46]上的一個數字
　　「後退」 9 次(接近 47 圈)
　　最後指向「數字 2」

意思(2)：
　　倍數有多組解

　　240*(-9)　　　　+ 46*(47)　　　　 = 2
　　240*(-9 + 46)　 + 46*(47 - 240)　 = 2
　　240*(-9 - 46)　 + 46*(47 + 240)　 = 2
　　240*(-9 - 46*n) + 46*(47 + 240*n) = 2
　　　　加號左邊：減掉 240*46*n
　　　　加號右邊：加上 240*46*n

　　240*(-9 - 46/2*n) + 46*(47 + 240/2*n) = 2
　　　　加號左邊：減掉 (240*46/2)*n
　　　　加號右邊：加上 (240*46/2)*n
　　　　　　最大公因數 = 2
　　　　　　最小公倍數 = 240*46/2

意思(3)：
　　46 和 47是[時鐘 size 240]上的兩個數字
　　相乘之後，指向 2
　　(46 + 240*幾倍) * (47 + 240*幾倍) 也會指向 2

　　240 和 -9 是 [時鐘 size 46]上的兩個數字
　　相乘之後，指向 2
　　(240 + 46*幾倍) * (-9 + 46*幾倍) 也會指向 2

時鐘次方 - 會不會指回原本的數字

和 12的因數「部份相同」：2、3、4、6、8、9、10
　　　　　　 1　 2　 3　 4　 5 (次方)
　　--------------------------------------------
　　　　2　　2　 4　 8　 4　 8　 (不能指回原本的數字)
　　　　3　　3　 9　 3　 9　 3
　　　　4　　4　 4　 4　 4　 4
　　　　6　　6　 0　 0　 0　 0　 (不能指回原本的數字)
　　　　8　　8　 4　 8　 4　 8
　　　　9　　9　 9　 9　 9　 9
　　　 10　 10　 4　 4　 4　 4　 (不能指回原本的數字)
　　　　有的可以指回原本的數字，有的不行

　　
和 12的因數「完全不同」(除了 因數1 之外)(互質)：1、5、7、11
　　　　　　 1　 2　 3　 4　 5 (次方)
　　-----------------------------------------------
　　　　1　　1　 1　 1　 1　 1
　　　　5　　5　 1　 5　 1　 5
　　　　7　　7　 1　 7　 1　 7
　　　 11　 11　 1　11　 1　11
　　　　全部都可以指回原本的數字
　　　　指回原本的數字之前，會先指向 1
　　　　　　n次方是 1
　　　　　　n+1次方 = 1 x 原數字 = 原數字

　　　　對5、7、11來說：
　　　　　　「首先」在2次方指向 1
　　　　　　所以，週期就是 2
　　　　　　
　　　　　　意思是：
　　　　　　　　0 次方 = 2 次方 = 2n次方 = 1
　　　　　　　　1 次方 = (1+2)次方 = (1 + 2n)次方 = 原本的數字

質數時鐘 - 指回原本數字的週期

　　[時鐘size 19]：
　　　　因為是質數時鐘，數字 1 ~ 18 都和時鐘size 19 互質，
　　　　在進行時鐘次方後，都會指回原本的數字

　　幾個數字的時鐘次方
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　(次方)
　　1　 2　 3　 4　 5　 6　 7　 8　 9　 10　11　12　13　14　15　16　17　18
　　---------------------------------------------------------------------------------------------
2　 2　 4　 8　16　13　 7　14　 9　18　 17　15　11　 3　 6　12　 5　10　 1
　　　　　　　　　　　　　　　　　(18相當於 -1)

6　 6　17　 7　 4　 5　11　 9　16　 1
7　 7　11　 1
18 18　 1
　 (18相當於-1)

　　2的週期　= 18
　　6的週期　= 9
　　7的週期　= 3
　　18的週期 = 2

　　每個數字的「個別週期」有的較長、有的較短
　　它們的共同點是：
　　　　「個別週期」的某倍，等於「共同週期」
　　　　「個別週期」會指向 1
　　　　「共同週期」也會指向 1

　　質數時鐘的「共同週期」= 時鐘size - 1

質數時鐘 - 週期的組成

　　質數時鐘 size p
　　時鐘上的數字 a

「a等於p」 和 「a小於p」 的差別

　　共同點：
　　　　 指向 a

　　不同點：
　　　　a等於p： 指向 a

　　　　a小於p： 指向 1

會不會指向 a ？ 大部份的數字不會

　　(只有 a=1 或 a=p　 會指向 a)

　　如果會指向 a
　　表示：
　　　　a的1倍 到　a的a倍
　　　　從位置 a ，轉了n圈之後，又回到原來的位置a
　　　　 - a = p的倍數

　　對大部份的數字而言，
　　 - a = a x (a - 1)
　　a 和 (a - 1) 都和 p 互質
　　所以， 不會指向 a
　　=============================================
　　以上是質數時鐘的情形
　　然而，在合成數時鐘 [時鐘size 12]
　　指向 9
　　 - 9 = 12的倍數

　　 - 9 = 9 x (9 - 1)
　　9 和 8 沒有和 [時鐘size 12] 互質、有大於1的相同因數
　　9 x 8 等於 12的倍數

會不會指向 1 ？ 只有 a=1 和 a=-1會

　　當 指向 1
　　表示： - 1 = p的倍數
　　　　(a+1)(a-1) = p的倍數
　　　　a的「前面數字」 x a的「後面數字」 = p的倍數
　　　　(前面數字 = p 或 後面數字 = p)
　　
　　1 和 (-1) 的前面 or 後面
　　有一個數字是 p
　　所以， 和 會指向 1
　　
　　其他數字的隔壁數字：
　　　　不會是 p
　　　　和 p 互質、沒有大於1的相同因數
　　所以(其他數字)^2不會指向 1

　　=============================================
　　以上是質數時鐘的情形
　　然而，在合成數時鐘 [時鐘size 12]
　　指向 1
　　指向 1

　　5的的隔壁數字 4 和 6
　　　　沒有和 [時鐘size 12]互質
　　　　有大於1的相同因數
　　　　4 x 6 = 12 的倍數

　　7的的隔壁數字 6 和 8
　　　　沒有和 [時鐘size 12]互質
　　　　有大於1的相同因數
　　　　6 x 8 = 12 的倍數
　　

指向 1 的情形

　　不一定會指向 1 ，要根據時鐘size而定
　　
　　以下是 [時鐘size 19] 的例子
　　 = x 7
　　　 = 11 x 7　(指向 1)

指向 1 的情形

　　不一定會指向 1 ，要根據時鐘size而定
　　
　　以下是 [時鐘size 19] 的例子
　　 = x x
　　　 = 7 x 7 x 7 (指向 1)

　　其中，
　　 = x 6
　　　 = 17 x 6 (指向 7)

時鐘次方 - 共同週期

適用的數字

　　與「時鐘size」互質的數字
　　(不是質數的數字，仍然有可能與時鐘size 互質)

共同週期

　　與「時鐘size」互質的數字的「總數」，就是共同週期

時鐘size =「質數 p」

　　共同週期 = (p - 1)
　　因為 1 到 (p - 1) 都和 p 互質
　　
　　(p - 1)次方指向 1
　　p 次方指回原本的數字
　　1 + 某倍(p-1)次方 也會指回原本的數字

時鐘size = 「質數 p」 X 「質數 q」

　　扣掉「p的倍數」、「q的倍數」，剩下的數字就是和「時鐘size」互質
　　1*p 2*p 3*p … q*p　 →　 q 個
　　1*q 2*q 3*q … p*q　 →　 p 個

　　共同週期 = p*q - p - q + 1
　　　　　　= (p - 1) * (q - 1)
　　
　　(p - 1) * (q - 1)次方指向 1
　　1 + 某倍(p-1)(q-1)次方 會指回原本的數字

和[時鐘size p*q] 不互質的數字(除了 p*q自己之外)

　　1*p 2*p 3*p … (q-1)*p　　 週期：q - 1
　　1*q 2*q 3*q … (p-1)*q　　 週期：p - 1
　　所以，也適用 共同週期 (p - 1) * (q - 1)

　　以 2p 為例：
　　時鐘　　 p * q　
　　2p　　　 p * 2 * (1)

　　　　p * 2 * (2p)
　　　　p * 2 * (2p*2p)
　　　　p * 2 * (2p*2p*2p)
　　指回原本數字 2p：
　　　　當2p*2p*2p*… 在[時鐘size q]指向 1 時
　　　　(q是質數，2p 和 q 互質，有機會指向 1)

RSA公開金鑰加密

時鐘size n = 「質數 p」 X 「質數 q」

時鐘上的數字 m
　　有的數字和 n 互質，有的數字沒有和 n 互質
　　都適用於共同週期 (p - 1) * (q - 1)

加密：
　　 使指針指到別的數字 c

解密：
　　 使指針指回原數字 m

≡ ≡ ≡ m
共同週期 (p - 1) * (q - 1)的意思：
　　1 + 1 (p - 1)(q - 1) 次方
　　1 + 2 (p - 1)(q - 1) 次方
　　1 + 3 (p - 1)(q - 1) 次方
　　1 + 4 (p - 1)(q - 1) 次方
　　1 + 5 (p - 1)(q - 1) 次方
　　　　在這些次方會指回原數字
　　　　e x d = 1 + 某倍(p - 1)(q - 1)

除了 「n = p*q」時鐘之外，
現在又多一個(p - 1)(q - 1)時鐘

選擇一個數字 e，必須與 (p - 1)(q - 1)互質
當 e 在做乘法時，才有機會指向 1　in (p - 1)(q - 1)時鐘

用「擴展歐幾里得算法」計算出 d
ed + (p - 1)(q - 1)*轉幾圈 = 1

比共同週期更小一點的週期

共同週期：(p - 1) X (q - 1)
更小一點的週期：(p - 1)和(q - 1)的最小公倍數

因為 時鐘size n = p x q (質數相乘)
時鐘上的每個數字 1 到 n
　　「除以p」、「除以q」都可以獲得獨一無二的「座標」
例如：
　　n = 3 x 5
　　每個數字分別 「除以 3」 「除以 5」
　　1 → (1,1)　 6 → (0,1)　 11 → (2,1)
　　2 → (2,2)　 7 → (1,2)　 12 → (0,2)
　　3 → (0,3)　 8 → (2,3)　 13 → (1,3)
　　4 → (1,4)　 9 → (0,4)　 14 → (2,4)
　　5 → (2,0)　10 → (1,0)　 15 → (0,0)

時鐘上的某一個數字，不同次方時，(x,y)座標會改變
　　次方週期 (p - 1) ： x座標回復原狀
　　次方週期 (q - 1) ： y座標會復原狀

　　次方週期 (p - 1)和(q - 1)的最小公倍數：
　　　　x座標 y座標都會復原狀 → 也就是指回原本的數字

參考資料

• 桑老師的瘋狂數學課( Marcus du Sautoy著 ; 郭婷瑋 譯)
• 圖解密碼學與比特幣原理(作者： 結城浩; 譯者： 吳嘉芳)
• 密碼學與網路安全( William Stallings著 ; 賴榮樞 譯)
• RSA算法原理（一） - 阮一峰的网络日志
• RSA算法原理（二） - 阮一峰的网络日志
• Jimmy's Blog: RSA非對稱加密演算法 (四) 利用中國剩餘定理加速
• 擴展歐幾里得算法 - 維基百科，自由的百科全書