RSA暗号で公開鍵\((n,e)\)を用いて、平文\(m\in [0,n-1]\)を暗号化して、暗号文を得るに、
\(m^e\)を\(n\)で割った余りを求める計算が必要になる。実用的に、\(n,e\)は\(2^{1024}\)程度を想定する。
\(j\)を\(k\)で割った商と余りをそれぞれ\(j\div k, mod(j,k)\)とかくと、
\(mod(m^e, n) =
\left\{
\begin{array}{ll}
mod(\{mod(m^{e\div 2},n)\}^2\cdot m^{mod(e,2)},n)&(e\not=0)\\
1&(e=0)
\end{array}\right.\)
とできる。さらに、\(m,n\)を大域変数として、\(pm(e):=mod(m^e, n)\)とおくと、
\(pm(e) =
\left\{
\begin{array}{ll}
mod(pm({e\div 2})^2\cdot m,n)&(e: odd)\\
mod(pm({e\div 2})^2,n)&(e: even, e\not=0)\\
1&(e=0)
\end{array}\right.\)
とできる。すなわち、\(pm(e)\)が再帰的に定義され、\(pm(e\div 2)\)を計算する問題に帰着される。さらに、\(e\rightarrow e\div 2 \rightarrow (e\div 2)\div 2 \rightarrow \cdots \rightarrow 1\rightarrow 0\)となり、高々\(\log_2 e\)(の整数への切上げ)だけの回数で\(mod(m^e, n)\)が計算できる。
このような再帰的なプログラミングを施さないで、まともにmを\(2^{1000}\)回かけると、一番高速な計算機を用いても10年かかる。逆に再帰をもちいると、1秒とかからない。現在、大阪大学理学部1年の実験科目で、上記の演習を課している。このことに気がつかないと、4年間では実行が終了しないので、彼らは卒業できないことになる。
数学だけではなく、物理や生物の学生もいる。むずかしいことから逃げないで、考え抜いてほしいと思っている。