- public static void main(String[] args) throws MultiplyMatrixException

- // Initialise variables n, q, x and rng

- int n = Integer.valueOf(args[0]);

+ public static void main(String[] args) throws MultiplyMatrixException

+ // Initialise variables n, q, x and rng

+ int n = Integer.valueOf(args[0]);

- // Used to select the value of x.

- Random rng = new Random();

- // Save Hadamard for use later.

- Gate h = new Hadamard();

- // Later, we add 1 each loop, so we cache this value so we don't instantiate each time.

- final Complex constant = new Complex(1,0);

- // Declare quantum registers that are to be used for Shor's Algorithm

- QubitRegister inState,outState;

- // Entangled is used twice in separate parts of program.

- int value_position; // This... kind of makes sense.

+ // Used to select the value of x.

+ Random rng = new Random();

+ // Save Hadamard for use later.

+ Gate h = new Hadamard();

+ // Later, we add 1 each loop, so we cache this value so we don't instantiate each time.

+ final Complex constant = new Complex(1,0);

+ // Declare quantum registers that are to be used for Shor's Algorithm

+ QubitRegister inState,outState;

+ // Entangled is used twice in separate parts of program.

+ int value_position; // This... kind of makes sense.

- // Find power of 2 that lies between n^2 and 2*n^2

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

- Gate iqft = new InverseQFT(q);

+ // Find power of 2 that lies between n^2 and 2*n^2

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

- //Create an array of complex numbers large enough to represent q in a register

- entangled = new Complex[(int)Math.pow(2,findRegisterSize(n))];

- // control variables - either we're done or we're taking too long.

- boolean done = false, fail = false;

- // Tracking our iterations.

+ //Create an array of complex numbers large enough to represent q in a register

+ entangled = new Complex[(int)Math.pow(2,findRegisterSize(n))];

+ // control variables - either we're done or we're taking too long.

+ boolean done = false, fail = false;

+ // Tracking our iterations.

- // 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.

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

- moddedExponents[i] = value_position;

- entangled[value_position].addToMe(constant);

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

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

- outState = new QubitRegister(entangled);

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

+ moddedExponents[i] = value_position;

+ entangled[value_position].addToMe(constant);

- // 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.

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

- if(moddedExponents[i] == k)

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

- entangled[i] = new Complex();

- inState = new QubitRegister(entangled);

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

- inState = inState.multiply(iqft);

- // ...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 start again because the register collapsed into the "wrong" state.

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

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

+ outState = new QubitRegister(entangled);

- // 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;

+ // 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.

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

+ if(moddedExponents[i] == k)

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

+ entangled[i] = new Complex();

+ inState = new QubitRegister(entangled);

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

+ inState = inState.multiply(qft);

+ // ...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 start again because the register collapsed into the "wrong" state.

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

- // So we get it from this function.

- int bestDenominator = findDenominator(c,q);

- // 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)

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

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

- int a = (expd + 1) % n;

- int b = (expd + n - 1) % n;

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

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

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

+ // So we get it from this function.

+ int bestDenominator = findDenominator(c,q);

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

+ int a = (expd + 1) % n;

+ int b = (expd + n - 1) % n;

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

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

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

/* From this point on in the file there are only utility functions that

* would only obfuscate if in the main body of code.*/

- // Recursively calculates the greatest common divisor of ints a and b.

- public static int gcd(int a, int b)

+ // Recursively calculates the greatest common divisor of ints a and b.

+ public static int gcd(int a, int b)

- // Calculates a^b mod n, taking the modulus throughout the calculation such that the intermediate values probably

- // won't overflow. If they were that large the VM would run out of memory before getting to this stage anyway.

- public static int modularPower(int a, int b, int n)

- for(int i = 0; i < b; ++i)

+ // Calculates a^b mod n, taking the modulus throughout the calculation such that the intermediate values probably

+ // won't overflow. If they were that large the VM would run out of memory before getting to this stage anyway.

+ public static int modularPower(int a, int b, int n)

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

- // If we had a register holding a value n, what is its minimum size?

- public static int findRegisterSize(int n)

+ // If we had a register holding a value n, what is its minimum size?

+ public static int findRegisterSize(int 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)

- if (z < 0.5 /(maxQ*maxQ))

- q2 = (int)Math.floor(y)*q1 + q0;

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

+ if (z < 0.5 /(maxQ*maxQ))

+ q2 = (int)Math.floor(y)*q1 + q0;