Introduction and Purpose

The purpose of the program FINDPRIM.BAS is to demonstrate

1. Standard factoring of a number which is a multiplication of two prime numbers
2. Shor's Algorithm simulation on a classical computer in 6 steps
3. "Shor's Algorithm" simulation on a classical computer in 2 steps
4. To answer 4 questions: Shor's Algorithm

To get a copy select: FINDPRIM.BAS
To see the listing of the program select: FINDPRIM.HTM
Execution file select: FINDPRIM.EXE and: brun45.exe
The same program writen in Excell: FINDPRIM SHOR.XLS
For a description select: findprim shor.xls.htm

Program Operation

Input for the program are two (prime) numbers: pm1 and pm2. Multiplication of those two (prime) numbers gives a number n which is factorized using Shor's Algorithm
There are two ways to run the simulation:

• In 2 Steps. Input for the program are then two prime numbers.
  For example if you want to factorize 55 in 2 Steps, you should enter 5 and 11.
• In 6 Steps. Input for the program are then two numbers. One number should be 1.
  For example if you want to factorize 55 in 6 Steps, you should enter 1 and 55.

For a description of all those 6 Steps see:http://everest.uwyo.edu/~moorhous/quantum/talk2.pdf
Shor's Algorithm simulation also works for prime numbers:

For Example: You can try the numbers 1 and 11

As part of Step 1 the program displays the two calculated values x and q. q = 2^x
Next the program asks the following question: Option Enter x"
You can Enter a new value for x, if you want. If you do than a new value for q is calculated.
For example: Try 1 and 55 and for x enter 8. The result is almost identical as for x=13. The periodicity in both cases is 20.

As part of step 3 a list showing how often each value (x^a mod n) is calculated. In fact this are the values stored in the array nxn explained in the next paragraph.
Next the following message is displayed: Enter a yellow number from above list
If you do not enter a number than the program selects at random a number out of this list.

In case you want to find the prime numbers 5 and 11 at the beginning of the program for prime number 1 Enter 1 and for prime number 2 Enter 55. Now Enter 28.

As part of step 4 the following message is displayed: All FFT state values? A = All; S = short list; blank = skip

• If you Enter A than for all values of c going from 0 to q the FFT state value is displayed. You can terminate this print out by entering the Letter E.
• If you Enter S than only for those values c the FFT state value is displayed when this number is larger than the sqroot of M.
• Any other key will skip the printout.

What the display shows that the largest values or smallest values are displayed in clusters.

Next the following message is displayed: All probability values ? A = All; S = short list; Enter = skip

• If you Enter A than for all values c going from 0 to q a the probability p(c) that c is selected is displayed. You can terminate this print out by entering the Letter E.
• If you Enter S than only for those values c are displayed when p(c) is larger than 0.1
• Any other key will skip the printout.

What the display shows that the most probable values come in clusters.
At the end of this display the total of all probability values is shown.

At the end of step 4 a list of the most probable measured values is displayed.
This are the values q*d/r for d going from 0 to r.

For Example if you want to find the prime numbers of 55, at the beginning of the program Enter 1 and 55. In step 3 Enter 28 and as part of Step 4 Enter S (Short list) twice . The first time to observe the FFT state values and the second time to observe the probability.

As part of step 5 the following message is displayed: Enter Measured value. Enter = Random . The purpose is to enter a value out of the previous displayed list. You can also enter any value. If no value is selected that the program selects one out of this list.

In step 6 Continued Fraction Convergent of this measured value is displayed.
For details see document 1 mentioned above.
At the end of step 6 the most probable periodicity values are displayed

For Example: in case 1 and 55 try the values 4915 and observe that the periodicity value is a multiple of 5

Finally the following message is displayed: "Repeat Step 5 and 6 ? Y = Yes N = No Enter = No " If you enter y or Y than step 5 and 6 are repeated.
If you enter a number >0 than step 6 is repeated.

For Example: in case 1 and 55 try the values 1, 410, 820 and 4096 and observe that the periodicity value is resp invalid, a multiple of 20, a multiple of 10 and a multiple of 2. That means certain measured values are "better" than others.

This terminates Shor's factorization in 6 steps

Finally the factorization results of Classical Algorithm and Fermat's Sieve Algorithm are displayed. With both algorithms the number of calculations is displayed.

For Example try 5 and 43 to observe that Shor's Algorithm in 2 steps requires 84 calculations, Classical Algorithm requires 7 calculations and Fermat's Algorithm requires 10 calculations.

Program Description

The program simulates Shor's Algorithm in 6 steps.
The variable n is the number which is factorized.
Input to the program are the two variables pm1 and pm2.

n = pm1 * pm2

1. In Step 1 the values x and q are calculated.
   
   q = 2^x
   q is greater than 2*n^2
   In Step 2 the variables xn = x^a MOD n are calculated for a going from 0 to q-1. Each of variables xn are stored in the array sxn. sxn(a) = xn
   For example in case of 5 and 11 array sxn contains the values:

   1,13,4,52,16,43,9,7,36,28,34,2,26,8,49,32,31,18,14 and 17

   For example sxn(9) = 28

   The variables xn are also counted and stored in the array nxn. nxn(xn) = nxn(xn) + 1
   For each xn a test is done to calculate if this particular xn is a stop sign.
   This is done by comparing xn with all previous values xn (stored in sxn). When a match is found than xn is the stop sign.
   Five tests are performed when a>0:

   1. If xn = sxn(0)= 1 and a is even then Shor's Algorithm works. y = sxn(a/2). p = GCD(y-1,n). q = GCD(y+1,n)
   2. Except if xn = sxn(0) = 1 and a is even and a = n-1 then n is prime number
   3. Except if xn = sxn(0) = 1 and a is even and y = n-1 then Shor's Algorithm does not work. This is called Type 4. For example: Try 3 and 29
   4. If xn = sxn(0) = 1 and a is odd then Shor's Algorithm does not work. This is called Type 3. For example: Try 5 and 29
   5. If xn = sxn(1) then y = sxn(1). p = GCD(y,n). q = n/p. In this case there is no stop sign =1. This is called Type 2. For example: Try 5 and 19 or 3 and 5
   6. If xn = sxn(aa) with aa>1 then y = sxn(aa). p = GCD(y,n). q = n/p. In this case there is no stop sign=1. This is called Type 5. For example: Try 2 and 18 or 2 and 54

   This ends Shor's Algorithm simulation in 2 steps if both pm1>1 and pm2>1.
   Step 2 terminates with a print out of a Frequency List i.e. all the values nxn which are greater than zero.

   In Step 3 one of the values xn is selected.
   As part of Step 3 a0 is calculated. a0 is the smallest value for which x^a0 Mod n = xn.
   In order to calulate a0 the array sxn is used. See above.

   For example in case xn=28 is selected then a0 is 9.

   The total number of xn values is M as stored in the array nxn(xn).

   In Step 4 FFT is performed and the result is stored in Register 1
   The FFT is calculated for all values c going from 0 to q-1 in two ways: as tot1 and as tot2
   

   First for each value of c the calculated state value tot1 is the sum of all values cos(2 * pi * r * c * d / q + w0) with d going from 0 to M-1 i.e. this is called a loop structure.

   The Initial value of w0 is 2 * pi * a0 * c / q with a0 as calculated previous.

   Secondly for each value of c the calculated state value tot2 is the sum of all values sin(2 * pi * r * c * d / q + w0) with d going from 0 to M-1

   The final state value tot as a function of c = SQR(tot1*tot1 + tot2*tot2)

   However it is also possible to implement tot1 and tot2 each as one calculation. See Shor's Algorithm - FFT Optimisation for details.

   Also the probability p(c) is calulated for all values c going from 0 to q-1
   For each value of c the probability p(c) is also calclated in two ways as tot1 and tot2.

   First calculated as tot1 as the sum of all values cos(2 * pi * r * c * d / q) with d going from 0 to M-1.

   Secondly calculated as tot2 as the sum of all values sin(2 * pi * r * c * d / q) with d going from 0 to M-1.

   The final sum tot (as a function of c) = SQR(tot1*tot1 + tot2*tot2)

   However it is also possible to implement tot1 and tot2 each as one calculation. See Shor's Algorithm - FFT Optimisation for details.

   Finally p(c) is calculated as sum * sum * 100 divided by q * M

   At the end of step 4 the most probable values p(c) are printed as q * d / r for all d going from 0 to r. r is periodicity.

   In Step 5 Register 1 is measured.

   In Step 6 a continued Fraction Convergent is performed to find the periodicity. This terminates Shor's Algorithm Simulation.

At the end of the program first a classical factorization is performed by using a recursive subroutine FACTOR. Each time when FACTOR is called; FACTOR calculates one factor.
FACTOR consists of four parameters: n, n1, lc and level.

• n is the number that is factorized.
• n1 is a counter. The initial value is 1. The inner part of the subroutine consists of one LOOP. Each time when the LOOP is executed n1 is increased with 1 and a test is done if n1 is a whole divisor of n i.e. if n mod n1 is zero.
  If this is true the new number n to factorize is equal to n/n1, n1 is saved in the array nxn, n1 is decreased with one and the subroutine FACTOR is called again.
  If this is not the case a test is done if n1*n1 > n. If this is not the case the LOOP is executed again, else the LOOP terminates.
• lc is loop counter or step counter. Each time when the LOOP is performed this value is increased with one.
• level is a level counter. Each time when FACTOR is called this value is increased with one. The highest value is stored in maxlevel.

After FACTOR a test is done with maxlevel. When maxlevel is 1 then n is a prime number. When maxlevel is 2 n consists of two prime numbers. When maxlevel is > 2 the value n was in Error.

At the final end of the program factorization is done using Sieve algorithm.
For a description of Fermat's factoring method see: http://www.math.ksu.edu/math511/notes/925.html

Reflection

1. The probability values for n=55 do not match the document as mentioned at the beginning of this page.

Feedback

Back to Shor's Algorithm - 10 Questions
Back to my home page: Contents of This Document