Ｎ＝１４７５７３９５２５８９６７６４１２９２７＝２^67−１

をあなたは素因数分解できますか？

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　この数はずっと素数だと考えられていたが，実は２つの素因数がある．１９０３年に

　　Ｎ＝２^67−１＝ｐｑ

　　ｐ＝１９３７０７７２１，ｑ＝７６１８３８２５７２８７

が発見されたことは大きな驚きであった．コンピュータができるよりもさらにずっと前のことで，計算はすべて手計算で行われたからである．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

［１］Ｎを２から√Ｎを超えない最大の整数まででひたすら割り，割り切れるかどうかを調べる方法は効率的ではない．

　　√Ｎ＝２^(1/2logN)

なので，多項式時間の範囲では終わらないからである．　　

［２］１９９４年，ショアは量子コンピュータなら，任意のＮを多項式時間で因数分解できることを示した．

　ショアのアルゴリズムでは，Ｎ＝ｐｑ，ｐ≠２，ｑ≠２，ｐ≠ｑであることが要請されるが，それはたいした制約にはならないだろう．

　最初の３つの素数は２（唯一の偶数の素数），３，５であるから，Ｎ＝１５はショアのアルゴリズムを使って素因数分解できる最小の数である．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

［３］Ｎ個のデータ検索では少なくとも１回，多ければＮ回，平均してＮ／２回の検索を行うことになる．

［４］１９９６年，グローヴァーは量子コンピュータなら，Ｎ個のデータ検索を√Ｎ回だけですみ探索アルゴリズムを見つけた．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝