Python（ショアのアルゴリズム01）

■古典的な方法でロジックの確認。
ショアのアルゴリズムの仕組みを見ていきたいけど、とりあえず古典的な方法でロジックを見る。
素因数分解をする対象として、下の３つを数字を取り上げる。別の方法で確認した素因数も列挙。
26 : [2, 13]
782 : [2, 17, 23]
3741 : [3, 29, 43]

ショアのアルゴリズムでは、f(x) = a^r mod N (ここで a はランダムで N とは互いに素の数字（1 < a < N）、r が周期を見つける乗数、N が素因数分解の対象の数字）で周期を発見して、そこから、a^(r/2) ± 1 と N の最大公約数（gcd: greatest common divisor）で素因数を見つける。

サンプルコードが次。

import random
import math
from math import gcd


def find_period_naive(a, N):
    r = 1
    current = pow(a, r, N)
    while current != 1:
        r += 1
        current = pow(a, r, N)
        print(f"a:{a}, r:{r}, a^r:{a**r}, N:{N}, 余り(a^r/N): {(a**r)%N}, 余り(a^(r+1)/N): {(a**(r+1))%N}, 余り(a^(r+2)/N): {(a**(r+2))%N} ")
        if r > N:
            return None  # 周期なし。
    return r


def try_find_period_randomly(N, max_trials=20):
    for trial in range(max_trials):
        a = random.randint(2, N - 1)
        if math.gcd(a, N) != 1:
            print(f"[{trial + 1}] a = {a} は N と互いに素でないためスキップ（因数：{math.gcd(a, N)}）")
            continue  # 互いに素でない

        print(f"[{trial + 1}] a = {a} を試します...")
        r = find_period_naive(a, N)
        if r is not None and r%2 == 0:
            print(f"  → 周期 r = {r} を発見しました！")
            return a, r
        else:
            print("  → 周期が見つかりませんでした。次へ。")

    print("周期の発見に失敗しました。")
    return None, None


# 実行
N = 782
a, r = try_find_period_randomly(N)

print(f"a:{a}, r:{r}, a^(r/2-1):{a ** (r // 2)-1}")
print(f"素因数(a^(r/2^1) -1とNの最大公約数):{gcd(a ** (r // 2)-1, N)}")
print(f"素因数(a^(r/2^1) +1とNの最大公約数):{gcd(a ** (r // 2)+1, N)}")

結果が下（26）。

a をランダムに選び、互いに素にならない場合は選びなおし（14, 16, 12はスキップ）。互いに素になったら r を１つずつ上げて周期性を探す。上では r = 6 が見つかっている。ランダムに選んだ a = 17 と r = 6 を使って素因数を探索。素因数の候補として2, 26 が見つかる。26を素因数分解すると 2, 13 のため 2 は正解になる。

782、3741 の結果がそれぞれ下のもの。3741では素因数の29が出ているが、782では46, 34とまだ因数分解できるものが表示されている。ただ、さらに因数分解できるので、繰り返せば素因数にたどり着く。

量子コンピュータでは、周期の部分（r）を重ね合わせで計算するよう。上のコードをQiskitでどう表現できるか見たい。