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