Running_Code

 Below, Shor's algorithm for a classical computer. From merlin (ChatGPT).

import numpy as np from math import gcd from sympy import mod_inverse def classical_shors_algorithm(N): # Step 1: Choose a random integer a in range [2, N-2] a = np.random.randint(2, N-1) # Step 2: Compute gcd(a, N) common_factor = gcd(a, N) if common_factor > 1: # Found a non-trivial factor return common_factor # Step 3: Find the order r of a modulo N r = find_order(a, N) if r is None or r % 2 != 0: return None # Failure to find suitable r # Step 4: Compute x = a^(r/2) mod N x = pow(a, r // 2, N) # Step 5: Check if x^2 ≡ -1 (mod N) if (x * x) % N == (N - 1): return None # Failure # Step 6: Return factors factor1 = gcd(x - 1, N) factor2 = gcd(x + 1, N) return factor1 if factor1 != N else factor2 def find_order(a, N): # Find the order r of a modulo N powers = [] seen = set() for k in range(1, N): power = pow(a, k, N) if power in seen: return k seen.add(power) powers.append(power) return None # Example usage if __name__ == "__main__": N = 15 # Composite number factor = classical_shors_algorithm(N) print(f"A non-trivial factor of {N} is: {factor}")

                                                                                   

                                                                                

COPILOT:

Shor's algorithm; if a and N need to be coprime, how can one factor 25?

Great question! Shor’s algorithm is designed to factorize large numbers efficiently using quantum computing. The requirement that ( a ) and ( N ) be coprime (i.e., their greatest common divisor is 1) is crucial for the algorithm to work correctly. However, when factoring a number like 25, which is ( 5^2 ), the situation is a bit different.

Here’s a step-by-step outline of how Shor’s algorithm can still be applied:

Choose a Random ( a ): Select a random number ( a ) such that ( 1 < a < N ). For ( N = 25 ), you might choose ( a = 2 ), ( a = 3 ), etc.

Check if ( a ) and ( N ) are Coprime: If ( \gcd(a, N) \neq 1 ), then ( a ) and ( N ) are not coprime. In this case, you can directly find a factor of ( N ). For example, if you choose ( a = 5 ), ( \gcd(5, 25) = 5 ), which is a factor of 25.

Quantum Order Finding: If ( a ) and ( N ) are coprime, proceed with the quantum part of Shor’s algorithm to find the order ( r ) of ( a ) modulo ( N ). The order ( r ) is the smallest positive integer such that ( a^r \equiv 1 \mod N ).

Use the Order to Find Factors: Once you have the order ( r ), use it to find the factors of ( N ). For example, if ( r ) is even, you can use the relation ( a^{r/2} \pm 1 ) to find factors.

For ( N = 25 ):

If you choose ( a = 2 ), ( \gcd(2, 25) = 1 ), so they are coprime.

Find the order ( r ) of 2 modulo 25. Suppose ( r = 20 ) (since ( 2^{20} \equiv 1 \mod 25 )).

Then, ( 2^{10} \equiv -1 \mod 25 ), and ( (2^{10} + 1)(2^{10} - 1) \equiv 0 \mod 25 ).

This simplifies to ( 1025 \equiv 0 \mod 25 ), giving factors 5 and 5.

In summary, even if ( a ) and ( N ) are not coprime, you can still factor ( N ) by directly using the greatest common divisor. For numbers like 25, which are perfect squares, the process simplifies significantly12.