```python
import fractions
import math
import random

import numpy as np
import sympy as sp
import cirq
```


```python
#elements of Z_n
def Z_n(n: int) -> List[int]:
    assert n > 1
    modd = [1]
    for x in range(2, n):
        if math.gcd(x, n) == 1:
            modd.append(x)
    return modd

n = 89
print("The multiplicative group modulo n = is:", Z_n(n))
```

    The multiplicative group modulo n = is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88]



```python
#Computing the order of an element of Z_n, classsically
def classical(x: int, n: int) -> Optional[int]:
    if x < 2 or x >= n or math.gcd(x, n) > 1:
        raise ValueError(f"Invalid x={x} for modulus n={n}.")
    
    # Find order.
    p, q = 1, x
    while q != 1:
        q = (x * q) % n
        p += 1
    return p

n = 89
x = 12
p = classical(x, n)
print(p)
```

    8



```python
#computing the order of an element of Z_n, using quantum approach
def quantum(x: int, n: int) -> Optional[int]:
    if x < 2 or n <= x or math.gcd(x, n) > 1:
        raise ValueError(f'Invalid x={x} for modulus n={n}.')
```


```python
"""Functions for factoring from start to finish."""
def find_factor_of_prime_power(n: int) -> Optional[int]:
    for k in range(2, math.floor(math.log2(n)) + 1):
        c = math.pow(n, 1 / k)
        c1 = math.floor(c)
        if c1**k == n:
            return c1
        c2 = math.ceil(c)
        if c2**k == n:
            return c2
    return None

def find_factor(
    n: int,
    order_finder: Callable[[int, int], Optional[int]] = quantum,
    max_attempts: int = 30
) -> Optional[int]:
   
    if sp.isprime(n):
        print("n is prime!")
        return None
    
    if n % 2 == 0:
        return 2
    
    c = find_factor_of_prime_power(n)
    if c is not None:
        return c
    
    for _ in range(max_attempts):
        x = random.randint(2, n - 1)
        c = math.gcd(x, n)
        if 1 < c < n:
            return c
        
        # Compute the order r of x modulo n using the order finder.
        r = order_finder(x, n)
        if r is None:
            continue
        if r % 2 != 0:
            continue
        y = x**(r // 2) % n
        assert 1 < y < n
        c = math.gcd(y - 1, n)
        if 1 < c < n:
            return c
    return None
```


```python
# Number to factor: a very huge number
n = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
z = find_factor(n, order_finder=quantum)
y = n // z

print("Factoring n = pq =", n)
print("p =", z)
print("q =", y)
```

    Factoring n = pq = 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
    p = 3
    q = 33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333



```python
"""Check the answer is correct."""
z * y == n
```




    True




```python

```

0779fce2e4fda9d3bba9b3dd206cc001d34bebbc
ipynb
Jupyter Notebook
Quiksilver/Shor's Algorithm .ipynb
alt-shreya/qchack
26ba07a02fbd1c377aa0ce560ed28904d35c9859
Apache-2.0
2021-04-10T14:26:36.000Z
2022-02-02T17:11:17.000Z
Quiksilver/Shor's Algorithm .ipynb
Parv-01/qchack
951b038e035db3aa4074e724ff52c0911e68139a
Apache-2.0
2021-04-11T03:29:12.000Z
2021-04-11T14:13:06.000Z
Quiksilver/Shor's Algorithm .ipynb
Parv-01/qchack
951b038e035db3aa4074e724ff52c0911e68139a
Apache-2.0
2021-04-10T14:43:08.000Z
2021-11-01T05:40:05.000Z
Qwen/Qwen-72B
1. YES
2. YES