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
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.
As part of step 4 the following message is displayed: All FFT state values? A = All; S = short list; blank = skip
Next the following message is displayed: All probability values ? A = All; S = short list; Enter = skip
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.
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.
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
Back to Shor's Algorithm - 10 Questions
Back to my home page: Contents of This Document