Miller-Rabin 算法與 RSA 算法
Miller-Rabin算法是目前主流的基于概率的素數測試算法）RSA加密算法是計算機世界中最重要的一種非對稱加密算法。本文從SICP 習題1.28出發，主要介紹兩種算法的數學原理以及Scheme的簡單實現，代碼保存在 Gist。
1. Miller-Rabin 素數檢驗算法
一個數是素數（也叫質數），當且僅當它的約數只有1和它本身。為了檢驗 n 是否為素數，最直接的方法就是逐一檢驗 [2,n?1] 能否整除 n：
(define (prime-iter n i)
(cond ((= i n) #t)
((= (remainder n i) 0) #f)
(else (prime-iter n (+ i 1)))))
(define (prime? n)
(prime-iter n 2))但是當數字較大的時候，這一算法的效率非常低下。于是就有了基于費馬小定理的概率算法：
費馬小定理：如果 p 是素數，a 是小于 p 的正整數，那么：ap?1 mod p=1。
所有素數都滿足費馬小定理的條件，因此從小于p的整數中隨機抽取a，只要有一個a不滿足上述條件則p為合數，抽取次數越多，全部通過費馬小定理之后我們準確判定p為質數的概率越高：
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder
(square (expmod base (/ exp 2) m))
m))
(else (remainder
(* base (expmod base (- exp 1) m))
m))))
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (random (- n 1)))))
(define (fast-prime? n times)
(cond ((= times 0) #t)
((fermat-test n)
(fast-prime? n (- times 1)))
(else #f)))然而費馬小定理只是質數的必要而非充分條件，有些數字每一個比它小的整數都能通過費馬測試，但卻是合數，這種數字稱為卡邁克爾數（Carmichael numbers）。最小的卡邁克爾數是 561，[1,1017] 之間有585,355 個卡邁克爾數，這使得費馬測試變得不可靠，于是就有了Miller-Rabin算法。
Miller-Rabin算法基于如下定理：
若 p 是素數，a 是小于 p 的正整數，且 a2 mod p=1，那么要么 a=1，要么 a=p?1。
證明： a2 mod p=1，則說明 a2?1=(a+1)(a?1) 能夠整除 p，由于 p 是素數，能夠整除它的只有 1 和 p 本身，因此 a 的解只能是 a=1 或 a=p?1。
基于上面的定理我們來檢驗最小的卡邁克爾數 561：首先 2560 mod 561=1，通過了費馬測試；進而考慮到 2560=(2280)2，根據規律 [1]：
結合上面的定理，那么 2280 mod 561 也應該是 1 或 560，經驗證 2280 mod 561=1；繼續我們發現 2140 mod 561=67，于是馬上可以得到 672 mod 561=1，違反了上面的定理，由此可以判斷 561 不是質數。
在Miller-Rabin算法中，我們將 p?1 （一定是偶數）不斷提取因子2，最終分解為：2sd（其中 d 是奇數），對于所有的 r∈[0,s?1]，只要存在 r 使得 ad mod p=1 或 a2rd mod p=p?1，即可推斷 p 有可能為素數；反之則一定為合數。
有趣的是在上面Scheme實現的費馬測試算法中，計算 an?1 所用的正是類似將指數不斷除2的遞歸方法，因此我們只需要對(expmod base exp n)方法中的遞歸調用(remainder (square (expmod base (/ exp 2) m)) m)（恰好是規律 [1]）進行檢驗：
;; miller-rabin algorithm
(define (remainder-square a n)
(cond ((or (= a 1) (= a (- n 1))) 1)
((= (remainder (square a) n) 1) 0)
(else (remainder (square a) n))))
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp) (remainder-square (expmod base (/ exp 2) m) m))
(else (remainder (* base (expmod base (- exp 1) m)) m))))
(define (mr-test n a)
(= (expmod a (- n 1) n) 1))
(define (miller-rabin n t)
(cond ((= t 0) #t)
((mr-test n (+ 2 (random (- n 2)))) (miller-rabin n (- t 1)))
(else #f)))
(miller-rabin 561 20)
;;=> #f2. RSA 加密算法
RSA 算法被評為真正統治世界的十大算法之一，雖然并非經過嚴格的權威性論證與投票表決，但大部分人應該不會對此存在異議。RSA 算法的數學原理簡而言之就是：利用對大數進行因數分解的困難，實現以公開密鑰對明文進行加密，而只能以私有密鑰進行解密。具體的數學推導過程可以參考文章最后的鏈接深入了解，這里我們需要了解一個新的數學定理：歐拉函數。
對整數 n，歐拉函數 φ(n) 是小于或等于 n 的正整數中與 n 互質的數的數量。特別的，如果 n 是素數，φ(n)=n?1。
下面我們來看Scheme簡單實現的 RSA 算法及加密解密過程的實例：
;; 1. 隨意選擇兩個大的質數p和q，p不等于q
(define p 61)
(define q 53)
;; 計算N=pq
(define N (* p q))
;; 2. 根據歐拉函數，求得r=(p-1)(q-1)
(define r (* (- p 1) (- q 1)))
;; 3. 選擇一個小于r的整數e，e與r互質
(define e 17)
;; 求得e關于r的模反元素
(define d (modular-multiplicative-inverse e r))
;; 模反元素計算過程
(define (dividable? x y)
(= (remainder x y) 0))
(define (mmii a m k)
(if (dividable? (+ (* k m) 1) a)
(/ (+ (* k m) 1) a)
(mmii a m (+ k 1))))
(define (modular-multiplicative-inverse a m)
(mmii a m 1))
;; RSA 加密需要公鑰(N, e)
;; RSA 解密需要私鑰(N, d)
(define (rsa m KNN Ked)
(expmod m Ked KNN))
;; 4. 利用公鑰對明文m進行加密
(define m 1990)
(display "PlaintText: ")
(display m)
(newline)
(display "Encrypted: ")
(define cipher (rsa m N e))
(display cipher)
(newline)
;;=> PlaintText: 1990
;;=> Encrypted: 1806
;; 5. 根據私鑰對密文進行解密
(display "Decrypted: ")
(display (rsa cipher N d))
;;=> Decrypted: 1990想要根據公鑰 (N,e) 推算出私鑰 (N,d) ，需要對 N 進行因數分解，推導出原始的 p 和 q。上例中用到的 p=61,q=53 很容易就可以從 N=3233 推導出來，然而當 N 非常大（1024或2048位二進制）時，對其進行因數分解在當下看來幾乎是不可能實現的。這也是密碼學中的一個基本原理，如果解密所需的成本高于該信息的價值，那么這種加密就被認為是安全的。