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);
+ // 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, 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);
+ // 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)