Problem 60790. Implement Shor's algorithm

Shor's algorithm, proposed in 1994 by Peter Shor, is an algorithm for factoring numbers that runs in polynomial time (polynomial in the number of digits/bits of the input) on a quantum computer. It works as follows.
To find a factor of a given integer N, which we assume to be an odd composite number that is not a prime power, pick a random integer . Next, if a is coprime to N, compute the order of a in the group : that is, find the smallest integer r such that . (If a and N are not coprime, their GCD is a factor of N.) If r is odd, choose a new a and begin anew; if it is even, compute , and compute the GCDs of N and and respectively. If one of these is non-trivial – neither 1 nor N – it is the desired factor; if both are trivial, choose a new a and start over.
On a quantum computer, for given a and N, r can be found efficiently. On a classical computer, it can't (as far as we know), but it can still be computed.
Your task is to implement Shor's algorithm. The input will be the product of a small number of distinct primes, and your function should return a factor f, the randomly-chosen a, its order r, the number q, and (for informational purposes only) the number of a's tried until the algorithm found a factor. If a and N are not coprime, you may return NaN for r and q.
Note 1: a and N not being coprime should be a rare event for such N. As such, the test suite will check that you don't get lucky too often. Solutions that call factor() and claim that a just so happened to be one of the factors returned every single time will get rejected; valid solutions should not be affected by this. If yours is, or if you otherwise happen to get unlucky with the inputs such that the test suite times out, submit your solution again.
Note 2: the test suite bans a few keywords, and "factor" is among them, so avoid this word in comments, variable names etc.
Solve

Solution Stats

100.0% Correct | 0.0% Incorrect
Last Solution submitted on Feb 18, 2025

Problem Comments

Solution Comments

Show comments

Problem Recent Solvers4

Suggested Problems

More from this Author17

Problem Tags

factoring shor

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!