New!! 栗まんじゅうでわかるショアのアルゴリズム（③57の素因数分解）

AI要約

ショアのアルゴリズムを学ぶシリーズ第3弾として、57の素因数分解に挑みます。qiskitのシミュレーションで周期18を発見し、その結果とユークリッドの互除法を組み合わせて因数3と19を導出するプロセスを解説します。

はじめに

ショアのアルゴリズムを学ぶシリーズ。これまでに「15個溜まったら捨てて余りが1個になる」「21個溜まったら捨てて余りが1個になる」を試しました。

栗まんじゅうでわかるショアのアルゴリズム（②21個溜まったら捨てる）

AI要約前回の法15に続き、今回は法を21に変更してショアのアルゴリズムの周期発見に挑みます。コントロール10ビット、ターゲット5ビットの回路を構築し、底が2や4の場合の周期をシミュレーションで導き出...

vigne-cla.com

2026/07/20

お察しの通り、実はこれらは15や21の素因数分解の手順の一部です。今回は新たに「57個溜まったら捨てて余りが1個になる」を行い、57の素因数分解までやりきってみましょう。

なお一説によると57は素数らしいですが、果たしてどうなのでしょうか。

問題

何度でも出します！

倍々に増える栗まんじゅうを57個ずつ処分して、ちょうど1個だけ余るタイミングはあるかな？それを僕が食べてトドメを刺すよ！

つまり、1→2→4→8個…と増えていったときに、57の倍数＋1になるタイミングが知りたいんだね！

問題はこちら。

一定時間ごとに2倍に分裂する栗まんじゅうが1個ある。57個溜まるごとに処分する場合、手元に1個だけ残るのは何回分裂したあとか？

手計算してみる

さあ、今回の問題は手強いですよ。

( )の中の数字は、57個溜まる度にちょこちょこ処分した場合です。なんと周期は18、答えは「18回分裂後」のようです。

参考文献：龍の髭

コードで確認

いつもコピペできるコードをもらえると思うなよ！（キレる若者）

前回のコードを各自修正してください。57なのでターゲットビットは6個、コントロールビットは12個としてください。

実行結果がこちら

101010101011010110 | 4/1200
101010101010111000 | 4/1200
110101010100110001 | 4/1200
010101010100111011 | 1/1200
（中略）
010011100010001010 | 1/1200
110001110001100011 | 1/1200
001011100010100110 | 1/1200
100101110000001010 | 1/1200
{'110101010101': 37, '010101010101': 34, (中略), '010001110100': 1, '000011101001': 1}

量子譜↓

ピークを見るグラフ↓

なんじゃこりゃ！コントロールレジスタの範囲0～4096を18等分するピークが現れました。よって周期＝18と求まりました。

ちなみに、底a=5としても周期18が求まります。これをこのあと使います。

ここから素因数分解

ここまでの計算結果を使って57の「因数分解」をやってみましょう。

ちょっと前提条件がありまして、まず、得られた周期が「偶数」である必要があります。もし偶数でなければ底「a」の値を変えて量子計算をやり直してください。また、実はa＝2の結果は不運なことにある種の特殊解のため、因数分解に使えません。この場合もやり直して、a＝5で周期18が求められたとしましょう。

いま、状況を整理すると、「5¹⁸個の栗まんじゅうを57個ずつ捨てると1個余った」

これを式にすると

　　5¹⁸ ＝ (57の倍数)＋1

　　(57の倍数) ＝ 5¹⁸ －1

中学校で習った「和と差の積の公式」を使って

　　(57の倍数) ＝ (5⁹ ＋1)(5⁹ －1) ＝ 1953126×1953124

ユークリッドの互除法で右辺の大きな数と57の共通因数（最大公約数）を求めます。

　　1953126 と 57 の共通因数 → 3
　　1953124 と 57 の共通因数 → 19
　　（このとき、それぞれ共通因数を持っていることが保証される（説明放棄））

よって、

　　(57の倍数) ＝ (57と共通の因数3を持つ数) × (57と共通の因数19を持つ数)

これは57が因数として3と19をもっていることを意味しており、因数分解ができました。

RSA暗号などで57という数字を「2つの素数の積」として作っていたと仮定すれば、「因数分解ができた」それすなわち「素因数分解ができた」ということになります。

グロタンディーク先生。やっぱり57は合成数でしたよ…！

おわりに

以上でショアの解説シリーズを終わります。いや、理論の深いところまでは解説できてないんですが。

ちなみに119とかの素因数分解も挑戦したんですが、qiskitの計算が全然終わらないので諦めました。一晩待ったらさすがに終わるかな？誰かやってみてください ( ˘ω˘ )zzz