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