ｎは自然数であるとします。このとき次が成立します。
ーーーーーーーーーーーーーーーーーーーーーーーー
ーーーーーーーーーーーーーーーーーーーーーーーー
証明しましょう。
（1）ｎ＝ａｂ（ａ，ｂ≠1）とします。
（2）ｎ≠1とし、ｎ＝ａｂｃ……（3つ以上の素数の積）とします。
易しいですね。でも高校で教わった記憶はありません。『暗号の数理』（一松信2005講談社ブルーバックス）では「大きな桁数の素因数分解は困難である」という事実を説明する際にこの定理を紹介しています。ｎの素因数は、あるとすれば√ｎ以下です。だから1000桁のｎが素因数分解できるなら500桁以下くらいの素因数があるはず。計算量は減るが焼け石に水である、といった話でした。
この定理に関してもうひとつ。エラトステネスのふるいというのがあります。100以下の合成数をすべて明らかにするときには2の倍数を除き、3の倍数を除き、5の倍数を除き、7の倍数を除けばよいのです。中学校のときでしょうか、始めてエラトステネスのふるいの話を授業で聞いたとき、もっと大きな素因数を調べなくていいのか疑問でした。それに対する応えがこの定理なのです。√100＝10なので、10以下の素因数を調べればよいということなんですね。（2）は最近整数の本を見ていて初めて知りました。言われてみれば確かに……という感じですが。
いわゆる整数論の初歩の部分です。整数論は「役に立たない」と言われていながらあるとき急に重要な理論に格上げされます。暗号の理論に使われるようになるのです。今や暗号には欠かせない存在です。
整数論は難しいけれど面白い。解けないときには一体何をどうしたらよいのか、見当すら全くつかない。それでもあちこちに面白い問題がたくさんあります。紹介してゆきましょう。
