VB.NETはじめるに戻る更新日：2002/11/1
２００２／１１の「今月のご挨拶」で「電子申請と公開鍵暗号」と題して、公開鍵暗号のについて、
簡単に紹介した。その中で、省略した事柄について、ここで記載していきたい。
公開鍵暗号では、大きな整数の素因数分解が困難なことが利用されている。同方法では、１００桁以上の整数が使用されている。
大きな整数をVB.NETで扱うためには、どうしても多倍長計算が必要になる。
なぜならば、VB.NETで普通に扱える数の大きさは、最大で３０桁程度であるからである。
UBASICなど一部の言語を除いて、プログラミング言語では、多倍長計算がサポートされていない。
現実世界では、最も精密な物理定数でさえ、８～１０桁程度の精度である。
であるので、これ以上の桁数を保って計算しても（現実世界では）意味がない。
これは、理・工学部の学生になると最初に教えられる点である。「測定値や計算の基礎となる数値の有効桁数を考えて、計算をする必要がある」と。
これが、通常、多倍長計算をサポートしていない主な理由と思われる。
公開鍵暗号を理解するためには、初等整数論の知識が必要である。日本では、数学科の学生を除いて、整数論に触れる機会は、（ほとんど）ない。
少なくとも筆者が学生であった頃の数学の基本的な流れは、実数、複素数を経て解析学・微分方程式へという道程であった。
これは、数学を学ぶ目的が理学・工学への応用のためと考えられているからであろう。
ただ、最近の情報理論や暗号などは、従来の解析学の応用では、理解できない項目が増えているのも事実である。
ところが、複素数やベクトルまでも高校数学から省かれてきているこの頃では、学校数学で整数論に親しむという機会は、更に遠くなったようにも思える。
ただ、パソコンの普及に伴うプログラム作成の授業等では、このような整数論の問題は、取り上げやすいと思う。
なぜならば、問題の理解については、事前の準備があまりいらないから。
以下では、（筆者のために）必要な事柄を簡単にまとめてみたが、読者のために何かの足しになれば、なお幸いである。
「自然数は神が作った。その他の数は人間が作った」とクロネッカー（数学者）は、
言ったと伝えられている。それほど、自然数（１，２，３・・）は、私たちに身近な存在である。
（自然数にゼロを含めていう場合もある。）
古代のギリシャの数学者・哲学者達は、このような自然数をさまざまな見方で分類していた。
例えば、X^2+Y^2=Z^2となる３つの自然数の組は、現在、「ピタゴラス数」と呼ばれている。
彼らは、狩猟家が獲物をねらうようにこのような特別な数達を発見した。
なお、ピタゴラス数については、ｘ，ｙ，ｚが互いに素という条件の下での一般解は、ｘ＝ａ＾２－ｂ＾２、ｙ＝２ａｂ、ｚ＝ａ＾２＋ｂ＾２であることが知られている。
合同式とは、ａ≡ｂ （ｍｏｄ ｎ）という形をしている。
式の意味は、ａをｎで割った場合、余りは、ｂであることを表している。
合同式は、通常の式と異なる側面もある。
例えば、ａ≡ｂであるからといって、ｂ≡ａではない。（５≡２ ｍｏｄ ３を考えれば分かる）
一方、ａ≡ｂ、ｃ≡ｄであれば、通常の式と同様に次が成り立つ。（ｍｏｄ ｎ）
ａ＋ｃ≡ｂ＋ｄ
ａ×ｃ≡ｂ×ｄ
証明は、ａ＝ｎＮ＋ｂ、ｃ＝ｎＭ＋ｄとして、ａ＋ｂ＝ｎ（Ｎ＋Ｍ）＋（ｂ＋ｄ）、
右辺第１項は、ｎで割り切れるから、この式の余りは、ｂ＋ｄであることなどから容易である。
合同式のわり算については、次のことが知られている。
ａとｎが互いに素の場合、ａ×ｋ≡１ （ｍｏｄ ｎ）なるｋが、一つ、存在する。
このｋをａの逆元という。これは、通常の算術の場合のわり算に相当する。
ｋが分かれば、ａ×ｂ≡ｃなるｂは、ｋ×ｃとして求められる。
ドイツの偉大な数学者、オイラーの名前を冠した定理や関数は、随所に現れるが、ここでいうオイラー関数、Φは、次のようなものである。
Φ（ｎ）とは、１～ｎまでの自然数のうち、ｎと互いに素となる数の個数のことである。
例えば、Φ（１０）＝４、（１，３，７，９が１０と互いに素）
一般にｎが素数の時は、Φ（ｎ）＝ｎ－１である。
また、次の定理が成り立つ。
ｎ＝ｐ１＾ｋ１×ｐ２＾ｋ２×・・としたとき、Φ（ｎ）＝ｎ（１－１／ｐ１）（１－１／ｐ２）・・である。
ここで、ｐ１等は、互いに異なる素数、ｋ１等は、自然数。
例えば、ｎ＝ｐ×ｑのときは、Φ（ｎ）＝ｐｑ（１－１／ｐ）（１－１／ｑ）＝（ｐ－１）（ｑ－１）である。
互いに素という意味をここで確認しておこう。（ａ，ｂ）でａとｂの最大公約数を表すと互いに素とは、（ａ，ｂ）＝１であることをいう。
ａとｎが互いに素の場合、ａ＾Φ（ｎ）≡１ （ｍｏｄ ｎ）である。これをオイラーの定理という。
そして、オイラー関数の性質を使えば、（４）よりｎ＝ｐ（素数）の場合、
ａ＾（ｐ－１）≡１ （ｍｏｄ ｐ）が直ちに得られる。これをフェルマーの小定理という。
例えば、ａ＝３、ｎ＝５とすると、３＾４＝５１≡１ （ｍｏｄ ５）である。
ちなみに、フェルマーの大定理とは、ｘ＾ｎ＋ｙ＾ｎ＝ｚ＾ｎを満たす自然数ｎ（＞２）は、存在しない。というものであり、長年にわたり未解決であったが、１９９３年に証明された。
（ｘ，ｎ）＝１となるｘ、（ｘは、１～ｎ）の集合を考える。この集合の個数は、Φ関数の定義によりΦ（ｎ）個である。
（ａ，ｎ）＝１なるａについて、ａｘ≡ｚは、また、この集合に含まれる。
更にｘが決まるとｚが決まり、その対応は、１対１である。（ここ、難しいので証明略す。）
そうすると、すべてのｘについての積、Πａｘ≡Πｘ。
積の個数は、ｍ個あるので、ａ＾ｍΠｘ≡Πｘ、両辺をΠｘで割れば、ａ＾ｍ≡１となる。
例えば、ｎ＝１０、ａ＝３とすれば、Φ（１０）＝４，（１，３，７，９）
３×１≡３
３×３≡９
３×７≡１
３×９≡７
で、ｘが１，３，７，９と変化するのに対して、３ｘは、３，９，１，７と変化している。
１９８６年当時の「数学セミナー」に「かずかずの数」という特集記事があった。
ここに様々な数についての話題が集められている。例えば、前出のピタゴラス数など。
ここでは、それを元に素数と関係の深いものを少し、紹介してみよう。
まず、「カーマイケル数」である。前出のフェルマーの小定理では、素数ｐについて、
ａ＾（ｐ－１）≡１ ｍｏｄ ｐを述べている。
この対偶をとると「ａ＾（ｎ－１）－１がｎで割り切れないときは、ｎは、合成数（素数でない数）である」
ここで、ａは、例えば、ｎが奇数であれば、（２以外の素数は、すべて奇数である。）、２とできる。
（これを素数判定のフェルマーテストという。）
では、割り切れた場合は、ｎは、素数であろうか？
フェルマーの小定理の逆は、必ずしも成立しないので、その真偽は判定できない。
合成数ｎ、ｎと互いに素なａに対して、ａ＾（ｎ－１）≡１ mod ｎ が成立するとき、ｎをａを底とする擬素数という。
特にａ＝２のときを「プーレー数」という。
さらに、どんなａ（ｎと互いに素な数）に対しても、ａ＾（ｎ－１）≡１となる数を「カーマイケル数」という。
例えば、５６１、１１０５、１７２９、２４６５、２８２１、６６０１、８９１１が１００００以下のカーマイケル数である。
カーマイケル数に関しては、次の定理が知られている。（チェルニク）
「ｎがカーマイケル数である必要十分条件は、ｎが３以上の奇素数の積であって、各素数に対して
ｎ≡１ （ｍｏｄ ｐ－１）」
ｎについて、ｎ以外の約数の和がｎ自身になるとき、ｎは、「完全数」であるといわれる。
例えば、６＝１＋２＋３なので、６は、完全数である。
奇数の完全数は、知られていないようである。
F(1)＝Ｆ（２）＝１、Ｆ（ｎ）＝Ｆ（ｎ－１）＋Ｆ（ｎ－２）で定義される数列をフィボナッチ数列といい
個々のＦ（ｎ）をフィボナッチ数という。
もう少し一般化して、Ｌ（１）＝ａ、Ｌ（２）＝ｂ、Ｌ（ｎ）＝Ｌ（ｎ－１）＋Ｌ（ｎ－２）なるものを考えて、特に、ａ＝１、ｂ＝３の場合を「リュカ数」という。
一般の場合は、フィボナッチ数とリュカ数で表される。これらの数と最大公約数などとは、関係が深い。
例えば、Ｆ（ｎ）とＦ（ｎ－１）など隣り合う数同士は、互いに素である。
素数を表す式としては、ｎ＾２－７９ｎ＋１６０１は、ｎ＝０～７９について、すべて素数となる。（エスコット）
かのフェルマーは、生前、２＾（２＾ｎ）は、ｎの如何に関わらず、素数であるといった。
これを「フェルマー数」という。ｎ＝０～４、ｎ＝４の時は、６５５３７となる。
しかし、ｎ＝６で、６４１×６７００４１７と素因数分解されて、フェルマーの言明は、誤りであることが分かった。
このことを示したのは、（またしても）、オイラーであった。
むしろ、最近では、フェルマー数で素数になるものが見つかっていないようである。
これについては、ペパンの判定法というものが知られている。
Ｆ（ｎ）（フェルマー数）が素数であれば、Ｆ（ｎ）は、３＾（（Ｆ（ｎ）－１）／２）＋１の約数、という関係が成立する。
例えば、Ｆ（２）＝１７は、素数であるが、３＾８≡１６ ｍｏｄ １７
ｐとｐ＋２がともに素数の時、この組を「双子素数」という。
双子素数は、無限に存在するらしいが、その程度は、多くはないと予想されている。
素数ｐに対する、２＾ｐ－１の形の数のことである。２＾３１－１＝２１４７４８３６４７は、素数である。
もちろん、素数でないものもある。例えば、２＾１１－１＝２０４７＝２３×８９
これについては、「リュカテスト」という素数判定法が存在する。
Ｓ（１）＝４、Ｓ（ｉ＋１）＝Ｓ（ｉ）＾２－２ ｉ＝１～
のとき、２＾ｐ－１が素数である必要十分条件は、Ｓ（ｐ－１）が２＾ｐ－１で割り切れること。
リュカテストは、計算機向きの方法なので、大きい素数は、大抵、メルセンヌ数であるとのこと。
公開鍵暗号の話では、ａ，ｋが大きな自然数であるとして、ｂを求める必要が出てくる。
例えば、２００２／１１の「今月のご挨拶」では、１９６＾１５７３≡？ （ｍｏｄ １０６７）を求めるという問題が出てくる。
これは、１５７３＝１１×１１×１３であることから、
１９６＾１５７３≡（（１９６＾１１）＾１１）＾１３、
これは、１９６≡１９６、１９６＾２≡４、１９６＾４≡１６、１９６＾８≡２５６などから
１９６＾１１≡１９６＾３×１９６＾８≡１９６×４×２５６≡１０８
そして、１０８≡１０８、１０８＾２≡９９４、１０８＾４≡１０６１、１０８＾８≡３６などから
１０８＾１１≡１０６５、
よって求める値は、１０６５＾１３。
１０６５≡１０６５、１０６５＾２≡４、１０６５＾４≡１６、１０６５＾８≡２５６などから
１０６５＾１３≡３４４となる。
（１）の計算を別の方法でやってみよう。
１５７３＝１０２４＋５１２＋３２＋４＋１となる。
一般に、ａ＾２＾ｋ＝（ａ＾２＾（ｋ－１））＾２であるので、
１９６≡１９６から
１９６＾２≡４
１９６＾４≡１６
１９６＾８≡２５６
１９６＾１６≡４４９
１９６＾３２≡１００５
１９６＾６４≡６４３
１９６＾１２８≡５２０
１９６＾２５６≡４４９
１９６＾５１２≡１００５
１９６＾１０２４≡６４３
となる。
よって、１９６＾１５７３≡６４３×１００５×１００５×１６×１９６≡３４４
となって、（１）の計算値と一致する。
暗号文、３４４を復号化する際に３４４から秘密鍵８７７を用いて３４４＾８７７の余りを計算する。
すなわち、３４４＾８７７≡？ （ｍｏｄ １０６７）を求める。
これも（２）の方法に従えば、８７７＝５１２＋２５６＋６４＋３２＋８＋４＋１
３４４≡３４４
３４４＾２≡９６６
３４４＾４≡５９８
３４４＾８≡１５９
３４４＾１６≡７４０
３４４＾３２≡２２９
３４４＾６４≡１５８
３４４＾１２８≡４２３
３４４＾２５６≡７４０
３４４＾５１２≡２２９
となる。
よって、３４４＾８７７≡２２９×７４０×１５８×２２９×１５９×５９８×３４４≡１９６
確かに元の平文の値、１９６になる。
暗号化は、ａを平文として、ａ＾ｋ≡ｂなる暗号文ｂを求める操作である。
この際、ｍｏｄ ｎのｎは、公開鍵の一つである。
また、ｋは、Φ（ｎ）＝ｍと互いに素となる数として選ぶ。ｋも公開鍵となる。
一方、秘密鍵は、ｋ×ｓ≡１ （ｍｏｄ ｍ）となる、ｓである。
さて、秘密鍵で復号化する操作は、ｂ＾ｓ≡？である。
この？がａであれば、確かに復号化が保証される。
ａ＾ｋ≡ｂから（ａ＾ｋ）＾ｓ≡ｂ＾ｓ≡ａ＾（ｋ×ｓ）
ところで、ｋ×ｓ≡１から、ｋ×ｓ＝ｍＭ＋１であるので、与式は、ａ＾（ｍＭ＋１）となる。
（Ｍは、自然数）
ａ＾ｍ≡１ （ｍｏｄ ｎ）（オイラーの定理）であるから、（ａ＾ｍ）＾Ｍ×ａ≡１＾Ｍ×ａ≡ａ、
よって、与式は、ａとなることが分かる。
秘密鍵ｓを知るためには、ｋとｍを知る必要がある。ｋは、公開されているが、ｍは、秘密である。
ｍは、オイラー関数Φを用いてΦ（ｎ）として計算する必要がある。
ｎの素因数分解を知っていれば、オイラー関数の個所に記載した公式によりｍは、容易に計算できる。
特にｎがＲＳＡ暗号のようにｐとｑという２つの素数の積であれば、ｍ＝（ｐ－１）×（ｑ－１）となる。
ところが、ｐとｑが分からないと、すなわち、ｎの素因数分解ができないとΦは容易に求まらない。
これがＲＳＡ暗号のよりどころである。換言すれば、大きな数の素因数分解が容易にできてしまうとＲＳＡ暗号は、破られてしまうことになる。
剰余の計算のフォームを作成してみよう。
多倍長の工夫については、追って考えるとして、取りあえず、ここで取り上げた程度の計算ができることを当面、目標とする。
関数FMODを次のように考える。
FMOD(a,k,n)＝MOD(a^k,n)である。しかし、ａ，ｋが半端な数ではない場合を考えたいので、このままではできない。
そこで、ｋ＝ｋ（０）×２＾０＋ｋ（１）×２＾１・・と分解すると、
（これは、ｋを２進数に分解しようということと同一である。）
ｉ番目の項については、FMOD（ａ，ｋ（ｉ），ｎ）とFMOD（ａ，２＾ｉ，ｎ）との積に分解できる。
FMOD（ａ，２＾ｉ，ｎ）≡（FMOD（ａ，２＾（ｉ－１），ｎ））＾２、
ここで、FMOD（ａ，１，ｎ）は、ａ MOD ｎとすれば、計算できる。
また、ｋ（ｉ）は、ゼロか１であるので、FMOD（ａ，０，ｎ）＝１に注意する。
そこで、求めたい値をＱと書けば、Ｑは、次のように繰り返し計算で求められる。
Ｂ＝ａ MOD ｎ
もし、Ｂ＝０であれば、Ｑ＝０である。（ａがｎの倍数の場合。互いに素の場合は、こうはならない）
Ｂがゼロでない場合で、
もし、ｋ（０）がゼロでない場合は、Ｑ＝Ｂとおく。ゼロの場合は、Ｑ＝１とする。
そして、ｉ＝１～ｍについて、
Ｃ＝Ｂ×Ｂ MOD ｎを計算する。
もし、Ｃがゼロの場合は、このループを抜ける。
もし、ｋ（ｉ）がゼロでない場合は、Ｑ＝Ｑ×Ｃ MOD ｎとする。
Ｂ＝Ｃにして、繰り返す。
これで、Ｑ＝ａ＾ｋ MOD ｎが計算できたことになる。
（１）の方針に基づき、VB.NETでのフォームを作成した。
これを例によって、「自作もの」コーナーに掲載しておく。
ただし、これは、多倍長計算を使用してないため、あまり多くの桁数の計算はできない。
数値か否かのチェックもしてないので、ａやｋ等に数値以外のものを入力して実行すると実行時のエラーが発生する。