2077を素因数分解できるならせよ！

2077を素因数分解できるならせよ、なんて問題はさすがに中学入試では出ないですよね。「素因数分解」というワードを使うことは決してないと思いますが、事実上その概念が求められていることは既にみた中学入試問題の検討において明らかになっています。
前に素数について述べた稿で、２桁以上の素数の１の位は１、３、７、９になることは示しましたが、他方で素数が無数に存在することの証明もご紹介しました。
再来年の入試では2027が素数であることが一つの論点になるだろうということも述べましたが、2077はどうでしょうか。最初は「素因数分解せよ」というタイトルにしていましたが、「素因数分解できるならせよ」とすることでグッとハードルが高くなりますね。前者であれば、通常素因数分解できると考えて素因数探しになりますが、後者であれば2077が素数かもしれない、そうであれば素因数分解しようにもできません。まずはそのチェックから入ろうということになるでしょう。。
ある整数nが素数かどうかを調べるには、自然数を順次エラトステネスの篩（ふるい）にかけて素数が見つかったら、その素数でnを割ってみて割り切れるかどうか調べ割り切れなければ、次の素数の発見に戻り、…ということをひたすらやらなければいけません。
中学入試の難問を攻略するために、ひょっとすると100の手前の97までの素数を暗記したり、あるいはそれらの掛け算の結果まで暗記…というところまでやっているかもしれません。もしそうなら、2077=31*67 という素因数分解がすぐに解けるかもしれませんね。
しかし、通常（？）の人にとって、2077の素因数分解はかなり厳しいと思われます。
ただ、これくらいの素因数分解ならば、デジタルコンピュータを使えば瞬殺でできてしまいます。これがもっと大きい数の素因数分解となると話が違ってきます。
n までの素数を求めよというプログラムを作るときには、自然数 i （3≦i≦n、初期設定は3）について、素数のリスト（初期設定は[ 2 ]）の要素で割っていって、割り切れなければ i をリストに加え、i に1を足して、同じことを繰り返すという考え方があると思いますが、nの桁数を増やしていくとどんどんアウトプットに時間がかかるようになります。そのようにして素数を探しつつそれらの素数でnが割り切れるかどうかチェックしなければならないため、非常に時間がかかるので、大きな素数の積で得られた合成数を素因数分解するというのは大変困難になります。
ちょっとわかりにくいと思いますので、人間でも手を動かせばできる範囲の話に一旦戻しましょう。
手品をします。まずは15と11という二つの整数を覚えて下さい。
次に15未満の正の整数を一つ考えて下さい。例として、7としましょうか。
それではその整数を11乗して下さい。7ならば、1977326743になります。
次にその値を15で割った余りを求めて下さい。1977326743を15で割ると、商が131821782で余りは13です。私、ガンガン電卓使ってます（笑）。
その余りを私に伝えて下さい。例では13を伝えることになりますね。

それを伝え聞いた私は、13を7乗します。すると62748517です。そしてこれを15で割ります。商は62748510で余りは7です。ほら、相手が考えた整数がここで出てくることになるのです！私は15と11という２つの整数をお伝えして、相手が自由に考えた7という数字を知らされることなく、約束通りの計算をしてもらった結果の13しか聞いていないにもかかわらず、7という数を言い当てることができました。
口頭でやりとりするにしても、文書やメールでやり取りするにしても、第三者には、15, 11, 13という情報しか分かりませんね。本当に伝えたい7という情報はまったく分からないことになります。

何をしたかを一般的に述べます。
まず自分の側で、２つの素数を決めて、その積（aとします）を求めます。
次にそれぞれの素数から１引いた数の積（bとします）を求めます。
bと互いに素（最大公約数が１）である整数を自由に決めてcとします。
Kcをbで割った余りが１になるような K を１つ見つけます。つまり、
Kc＝bn＋１（K, nは整数）という不定方程式の解 ( K , n ) を１つ求めます。
相手には、a と c を伝え、a 未満の自然数を自由に頭に思い浮かべ（これをＸとします）て、それを c 乗し、さらに a で割った余り（ R とします）を教えて下さいと言います。
応答として、相手がRを伝えてきたら、こちらではＲを K 乗します。Kは私しか知りません。R^K が求まったら、それを a で割ります。ここで得られた余りが何とＸになるのです！
このやり方でしたら、複数の相手と同じ方法でやりとりしていても、 K の値を知られていない限り、ある相手とのやり取りを別の相手に察知されても本当に伝えたい X が漏洩することはありません。
これはある暗号化のアルゴリズムを簡単に紹介したものです。実際の運用にあたっては、極めて大きな素数の積を a とします。大きな素数を作るのは、素数の積に１を加えればよい（過日の稿で素数が無数にあることの証明をご紹介しましたがその応用です）のでそんなに難しくはありませんが、逆にそうして作られた素数だけを与えられて、それが素数かどうかを判断するためには、「エラトステネスの篩（ふるい）」を使っても、上で述べたように多数の素数で割り切れるかどうかを調べなければならないので、非常に手間がかかります。重要なので再度言いますが、素数かどうかを判断するプログラムを作って走らせると、桁が上がるにつれて実行速度がどんどん遅くなっていきます。また、累乗計算の結果も非常に大きくなっていきますのでこれもハードルを上げる要素となります。
こういう困難性を利用してデータ通信等の秘匿性をキープしているのです。
もちろん悠久の時間が得られれば秘匿性を破ることは可能ですが、それが実現されるころには太陽系が生存しているのかどうかさえわからない状況なので、既に秘匿する情報自体に意味がなくなっているということになります。

しかしながら、先日GoogleがWillowという量子チップを発表したことが画期的な出来事として報じられたように量子コンピューティングの研究開発も最先端では活発に行われています。量子コンピュータは、古典コンピュータ（つまり今のデジタルコンピュータ）の最高レベルのもの（つまりスパコン）を使っても10^25年程度かかる計算を数分でしてしまうといわれています。量子コンピュータのこのような処理速度をもってすれば、今回述べたRSA暗号を破られてしまうことになるでしょう。ただ、量子コンピュータの実用化にはまだまだかなりの道のりがあるようです。期待と怖れを感じながら注視したいです。