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$ 的正整数，那么：$a^{p-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, 10^17]$ 之间有$585,355$ 个卡迈克尔数，这使得费马测试变得不可靠，于是就有了Miller-Rabin算法。
Miller-Rabin算法基于如下定理：
若 $p$ 是素数，$a$ 是小于 $p$ 的正整数，且 $a^2\ mod\ p = 1$，那么要么 $a=1$，要么 $a=p-1$。
证明： $a^2\ mod\ p = 1$，则说明 $a^2 - 1 = (a+1)(a-1)$ 能够整除 $p$，由于 $p$ 是素数，能够整除它的只有 $1$ 和 $p$ 本身，因此 $a$ 的解只能是 $a=1$ 或 $a=p-1$。
基于上面的定理我们来检验最小的卡迈克尔数 $561$：首先 $2^{560}\ mod\ 561 = 1$，通过了费马测试；进而考虑到 $2^{560} = (2^{280})^2$，根据规律 $[1]$：
$$ \begin{align} if, &\ a\ mod\ p = k \\ then, &\ a^2\ mod\ p = k^2\ mod\ p \end{align} $$
结合上面的定理，那么 $2^{280}\ mod\ 561$ 也应该是 $1$ 或 $560$，经验证 $2^{280}\ mod\ 561 = 1$；继续我们发现 $2^{140}\ mod\ 561 = 67$，于是马上可以得到 $67^2\ mod\ 561 = 1$，违反了上面的定理，由此可以判断 $561$ 不是质数。
在Miller-Rabin算法中，我们将 $p-1$ （一定是偶数）不断提取因子2，最终分解为：$2^sd$（其中 $d$ 是奇数），对于所有的 $r \in [0, s-1]$，只要存在 $r$ 使得 $a^d\ mod\ p = 1$ 或 $a^{2^rd}\ mod\ p = p-1$，即可推断 $p$ 有可能为素数；反之则一定为合数。
有趣的是在上面Scheme实现的费马测试算法中，计算 $a^{n-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)
;;=> #f
2. RSA 加密算法
RSA 算法被评为真正统治世界的十大算法之一，虽然并非经过严格的权威性论证与投票表决，但大部分人应该不会对此存在异议。RSA 算法的数学原理简而言之就是：利用对大数进行因数分解的困难，实现以公开密钥对明文进行加密，而只能以私有密钥进行解密。具体的数学推导过程可以参考文章最后的链接深入了解，这里我们需要了解一个新的数学定理：欧拉函数。
对整数 $n$，欧拉函数 $\varphi (n)$ 是小于或等于 $n$ 的正整数中与 $n$ 互质的数的数量。特别的，如果 $n$ 是素数，$\varphi (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位二进制）时，对其进行因数分解在当下看来几乎是不可能实现的。这也是密码学中的一个基本原理，如果解密所需的成本高于该信息的价值，那么这种加密就被认为是安全的。