時鐘加法
指針指向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
時鐘次方
25 指針會指向哪裡？
次方就是「重複做乘法」，每次都乘一樣的數字
(2 * 2 * 2 * 2 * 2) % 12 = 8
(72)25 指針會指向哪裡？
有五種算法：
1. 先計算小括弧裡面
(72)25 = (49)25 然後除以12，取餘數
2. 先把指數相乘
(72)25 = 750 然後除以12，取餘數
3. 先把(72)的餘數算出來
(72)25 → (49)25 → (49 % 12)25 → (1)25 → 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
所以，(72)25在[時鐘size 12]會指向 1
5. 根據7n的餘數
如果知道 749的餘數是 7
那麼，750的餘數，就是 7 * (7) % 12
如果知道 748的餘數是 1
那麼，750的餘數，就是 1 * (7 * 7) % 12
時鐘乘法 - 只會指向那些數字
時鐘size 12 的質因數分解 = 22 * 3
時鐘上的數字分成兩類：
和 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*s1 + 46*t1 = 240
2代餘數： 240*0 + 46*1 = 46 → 240*s2 + 46*t2 = 46
q3到q7代表「商」(負數)
3代餘數： 240 + q3*46 = 10 → (1代餘數) + q3*(2代餘數) = 10
↓ 穢土轉生
(240*s1 + 46*t1) + q3*(240*s2 + 46*t2) = 10
240*(s1 + q3*s2) + 46*(t1 + q3*t2) = 10
↓
240*s3 + 46*t3 = 10
(s3 可以用 s1 s2 q3 計算出來)
4代餘數： 46 + q4*10 = 6 → (2代餘數) + q4*(3代餘數) = 6
5代餘數： 10 + q5*6 = 4 → (3代餘數) + q5*(4代餘數) = 4
6代餘數： 6 + q6*4 = 2 → (4代餘數) + q6*(5代餘數) = 2
7代餘數： 4 + q7*2 = 0 → (5代餘數) + q7*(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」 的差別
共同點：
ap 指向 a
不同點：
a等於p：ap-1 指向 a
a小於p：ap-1 指向 1
a2 會不會指向 a ？ 大部份的數字不會
(只有 a=1 或 a=p a2 會指向 a)
如果a2會指向 a
表示：
a的1倍 到 a的a倍
從位置 a ，轉了n圈之後，又回到原來的位置a
a2 - a = p的倍數
對大部份的數字而言，
a2 - a = a x (a - 1)
a 和 (a - 1) 都和 p 互質
所以，a2 不會指向 a
=============================================
以上是質數時鐘的情形
然而，在合成數時鐘 [時鐘size 12]
92指向 9
92 - 9 = 12的倍數
92 - 9 = 9 x (9 - 1)
9 和 8 沒有和 [時鐘size 12] 互質、有大於1的相同因數
9 x 8 等於 12的倍數
a2 會不會指向 1 ？ 只有 a=1 和 a=-1會
當 a2指向 1
表示：a2 - 1 = p的倍數
(a+1)(a-1) = p的倍數
a的「前面數字」 x a的「後面數字」 = p的倍數
(前面數字 = p 或 後面數字 = p)
1 和 (-1) 的前面 or 後面
有一個數字是 p
所以，12 和 (-1)2會指向 1
其他數字的隔壁數字：
不會是 p
和 p 互質、沒有大於1的相同因數
所以(其他數字)2不會指向 1
=============================================
以上是質數時鐘的情形
然而，在合成數時鐘 [時鐘size 12]
52指向 1
72指向 1
5的的隔壁數字 4 和 6
沒有和 [時鐘size 12]互質
有大於1的相同因數
4 x 6 = 12 的倍數
7的的隔壁數字 6 和 8
沒有和 [時鐘size 12]互質
有大於1的相同因數
6 x 8 = 12 的倍數
a3指向 1 的情形
a3不一定會指向 1 ，要根據時鐘size而定
以下是 [時鐘size 19] 的例子
73 = 72 x 7
= 11 x 7 (指向 1)
a9指向 1 的情形
a9不一定會指向 1 ，要根據時鐘size而定
以下是 [時鐘size 19] 的例子
69 = 63 x 63 x 63
= 7 x 7 x 7 (指向 1)
其中，
63 = 62 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)
(2p)2 p * 2 * (2p)
(2p)3 p * 2 * (2p*2p)
(2p)4 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)
加密：
me 使指針指到別的數字 c
解密：
cd 使指針指回原數字 m
cd ≡ (me)d ≡ med ≡ 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座標都會復原狀 → 也就是指回原本的數字
參考資料
沒有留言:
張貼留言