RSAのmのe乗mod nの計算、卒業までに完了できるか

投稿者: | 2010年12月14日

RSA暗号で公開鍵(n,e)を用いて、平文m\in [0,n-1]を暗号化して、暗号文を得るに、
m^enで割った余りを求める計算が必要になる。実用的に、n,e2^{1024}程度を想定する。

jkで割った商と余りをそれぞれ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年間では実行が終了しないので、彼らは卒業できないことになる。

数学だけではなく、物理や生物の学生もいる。むずかしいことから逃げないで、考え抜いてほしいと思っている。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です