暗号革命と素数（２）大きな数の素因数分解／知的生産の方法（１６２）

【2017年7月12日 (水)：暗号革命と素数（１）暗号化の基礎／知的生産の方法（１６１） 】から続く。

因数分解を初めて教わった時、何だか大人の世界の扉が開いたような気がしたことを覚えている。
算数から数学への変化の実感であったのだろうか。
因数分解の一種に、素因数分解がある。
正の整数、すなわち自然数を素数の積で表すことである。

3分でわかる！素因数分解とはなんだろう？？

つまり、自然数を素数の因数に分界することであり、素数の因数すなわち素因数である。

例えば、35＝5×7であるから

自然数は正の整数のことであり、０や負の整数は含まない。
中学１年生のガンバレ数学！９０点コース

上図のように、0は自然数ではない。
素数とは、約数が1と「その数自身」の2つだけである自然数のことであり、2、3、13などである。
1は約数が1だけなので素数ではない。

12を素因数分解すると、2・2・3になる。
12=3×4であるが、4は素数ではないから素因数分解ではない。
12や35＝5・7などの比較的小さな自然数ならば、素因数分解は容易である。

それでは、6887 はどう素因数分解されるだろうか？
2つの素数に分解できるが、簡単には思いつかない。
現在のところ大きな数を素因数分解できる効率的な方法は見つかっていない。
2つの素数 P と Qを掛けて P×Qを求めることは簡単にできるが、逆に掛けた結果の P×Q から P と Qを効率的に求めることは極めて難しいということである。

6887＝71×97
であるが、簡単には思いつかない。
この素因数分解の難しいことが、現代の暗号技術の革命の基礎となった。