boolean done = false, fail = false;

// Tracking our iterations.

-~~ // First random x, will be refined in the loop if necessary.~~

+ // Generate a random x between 1 and n.

+ // It cannot be 1 or have a gcd of 1 with n (because then it's a factor).

while((gcd(x,n) != 1) || (x <= 1))

+ // An array of x^(0..q) mod n.

moddedExponents = new int[q];

+ // Adding to this before the break statement.

+ // the array used for entangling later is initially set to zero all over.

for(int i = 0; i < entangled.length; ++i)

entangled[i] = new Complex(0,0);

+ // Here We take the x^i mod n. moddedExponents[i] is assigned this while the entangled register's moddedExponent position

+ // is increased. This represents an increase in probability amplitude.

for(int i = 0; i < q; i++)

value_position = modularPower(x, i, n);

entangled[value_position].addToMe(constant);

+ // After this we form the register from the complex array but it will need to be normalised.

outState = new QubitRegister(entangled);

+ // We now repurpose entangled, it is no longer needed for its previous purpose.

entangled = new Complex[q];

+ // Observing the output register to allow us to collapse the in register, see next comment.

int k = outState.observe();

// In a quantum computer, this register would automatically collapse into the correct state.

// However, because this is a simulation, we must do it manually.

inState = new QubitRegister(entangled);

- // Making inverse discrete quantum fourier transform, same size as the register.

+ // Making inverse discrete quantum fourier transform gate, same size as the register.

Gate iqft = new InverseQFT(inState.getLength());

// This will hopefully transform the register into a particular value...

// ...the observed value should be a multiple of a number formed from the period.

int multiple = inState.observe();

- // Occasionally it's not, this means we must choose another x / start again because the register collapsed into the "wrong" state.

+ // Occasionally it's not, this means we must start again because the register collapsed into the "wrong" state.

+ // Or that our choice of x was not 'good' enough - such is randomness.

// c is this multiple divided by q from the beginning of the program, we now want the rational approximation to this.

double c = (double)multiple/(double)q;

// So we get it from this function.

int bestDenominator = findDenominator(c,q);

- // If the denominator isn't even, it probably won't work. There are ways around this, but...

+ // If the denominator isn't even, it won't work. However, if twice this value is still less than q, we can use

+ // twice the approximation instead.

if(bestDenominator % 2 == 0)

if(bestDenominator*2 < q)

// There are two roots formed from this expression; the GCD of each with n is calculated. Hopefully, we have

// some nontrivial ones! OTOH the program can return 1 and n.

int expd = modularPower(x, bestDenominator/2, n);

System.out.println(gcd(n,a));

System.out.println(gcd(n,b));

System.out.println("Algorithm failed!");

+ // Finds the closest rational approximation to c where the denominator is less than maxQ.

+ // Uses method of continued fractions.

public static int findDenominator(double c, int maxQ)