  |
2. モジュラスの計算: N = p * q
3. オイラーのトーシェント関数: φ(N) = (p-1)(q-1) を計算する。
4. 公開鍵と秘密鍵の生成: 公開鍵は (N, e) であり、e は gcd(e, φ(N)) = 1 を満たす整数である。秘密鍵は d であり、d * e ≡ 1 (mod φ(N)) を満たす。
RSA暗号の安全性は、合成数 N の素因数分解が計算的に困難であることに依存している。具体的には、次の問題が考えられる：
N = p * q
ショアのアルゴリズムは、量子コンピュータ上で動作する効率的な素因数分解アルゴリズムである。以下にその主要なステップを示す。
任意の整数 a を選択し、N に対して次の条件を満たすことを確認する：
整数 a の順序 r を求める。順序とは、次の条件を満たす最小の整数である：
a^r ≡ 1 (mod N)
量子フーリエ変換は、状態ベクトルを重ね合わせて次のように表現される：
|x⟩ = Σ(k=0 to N-1) |k⟩
ここで、量子フーリエ変換を適用することで周期性に関する情報が得られる。具体的には、
QFT |x⟩ = (1/√N) Σ(j=0 to N-1) Σ(k=0 to N-1) e^(2πi jk / N) |j⟩
得られた状態から測定を行うことで周期情報が得られる。この周期情報を用いて次の式を考える：
x = a^(r/2) - 1
y = a^(r/2) + 1
これらが非自明な因子である場合、p と q を次のように計算できる：
p = gcd(x, N)
q = gcd(y, N)
ショアのアルゴリズムは確率的であり、成功率は高いものの100%ではない。そのため、誤り訂正技術や複数回実行することで成功確率を向上させる必要がある。
22
