时钟加法

指针指向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非对称加密演算法 (四) 利用中国剩余定理加速
• 扩展欧几里得算法 - 维基百科，自由的百科全书