qqz.shor 

 1import random
 2import math
 3from typing import Optional
 4
 5import numpy as np
 6import matplotlib.pyplot as plt
 7from qiskit import QuantumCircuit, Aer, transpile, assemble
 8from qiskit.visualization import plot_histogram
 9from sympy import Rational
10from sympy.ntheory.continued_fraction import continued_fraction, continued_fraction_convergents
11
12from qft import qft
13from elementary import ax_modM
14from order_finding import order_finding
15
16
17def shor(N: int, show_hist: bool = False):
18    """Shor's factoring algorithm: given $N\in\mathbb{Z}$, it finds a prime factor of $N$.
19
20    Args:
21        N (int): $N$
22
23    Returns:
24        A prime factor of $N$
25
26    Examples:
27
28    ```
29    >>> shor(N=9)
30    3
31    ```
32    """
33
34    if N % 2 == 0:
35        return 2
36
37    for _ in range(N):
38        a = random.randint(2, N - 1)
39        gcd = math.gcd(a, N)
40        if gcd != 1:
41            return gcd
42
43        r = order_finding(x=a, N=N, show_hist=show_hist)
44
45        if r % 2 == 1:
46            continue
47        if (x ** (r // 2) + 1) % N == 0:
48            continue
49
50        factor_candidate = math.gcd(x ** (r // 2) - 1, N)
51        if N % factor_candidate == 0:
52            return factor_candidate
53        factor_candidate = math.gcd(x ** (r // 2) + 1, N)
54        if N % factor_candidate == 0:
55            return factor_candidate
56
57    raise Exception('A prime factor is Not found!')
58
59
60if __name__ == '__main__':
61    print(shor(N=9))
def shor(N: int, show_hist: bool = False): 
18def shor(N: int, show_hist: bool = False):
19    """Shor's factoring algorithm: given $N\in\mathbb{Z}$, it finds a prime factor of $N$.
20
21    Args:
22        N (int): $N$
23
24    Returns:
25        A prime factor of $N$
26
27    Examples:
28
29    ```
30    >>> shor(N=9)
31    3
32    ```
33    """
34
35    if N % 2 == 0:
36        return 2
37
38    for _ in range(N):
39        a = random.randint(2, N - 1)
40        gcd = math.gcd(a, N)
41        if gcd != 1:
42            return gcd
43
44        r = order_finding(x=a, N=N, show_hist=show_hist)
45
46        if r % 2 == 1:
47            continue
48        if (x ** (r // 2) + 1) % N == 0:
49            continue
50
51        factor_candidate = math.gcd(x ** (r // 2) - 1, N)
52        if N % factor_candidate == 0:
53            return factor_candidate
54        factor_candidate = math.gcd(x ** (r // 2) + 1, N)
55        if N % factor_candidate == 0:
56            return factor_candidate
57
58    raise Exception('A prime factor is Not found!')

Shor's factoring algorithm: given $N\in\mathbb{Z}$, it finds a prime factor of $N$.

Arguments:
  • N (int): $N$
Returns:

A prime factor of $N$

Examples:

>>> shor(N=9)
3