Spread sheet lay out: "Blad1"

Factorize

Program Operation: "Blad1"

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. Those two numbers should be entered in the cells (1,B) and (2,B). After that select the button "Factorize"
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 the numbers 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 the numbers 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 three calculated values n = pm1*pm2 in Cell (1,E) x in Cell (2,E) and q in Cell (3,E). 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.

As part of Step 2 the results of x^a mod n is calculated in row 6 as a function of a. The value of a is displayed in row 5

As part of step 3 a list numbers is displayed showing how often each value (x^a mod n) is calculated. The values x^a mod n are displayed in row 7 and the list (the variable M) in row 8. In fact this are the values stored in the array nxn explained in the next paragraph.
Next the following message is displayed: Select a number from Register 2 line
If you do not enter a number than the program selects at random a number out of the list in row 7.

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? S = short list; blank = skip

• 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 ? S = short list; Enter = skip

• If you Enter S than only for those values c are displayed when p(c) is larger than 1/r
• 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 printed in the Debug buffer.
For details see document 1 mentioned above.
At the end of step 6 the most probable periodicity values are displayed
You can also repeat Step 5 and Step 6

For Example in case 5 and 11 try the values 4915, 820 and 410 and observe that the periodicity value is resp a multiple of 5, 10 and 20. 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 in resp. row 11 and row 12. Which both algorithms the number of calculations is displayed in column K.
For Example: try 5 and 43 to observe that Shor's Algorithm has periodicity 84, Classical Algorithm requires 4 calculations and Fermat's Algorithm requires 10 calculations.

Spread sheet lay out: "Blad2"

GetPrime

Program Operation: "Blad2"

Input for the program are two (prime) numbers: pm1 and pm2. Those two numbers should be entered in the cells (2,A) and (2,B). After that select the button "GetPrime"

Those two numbers are used as start values for 50 prime number combinations. Multiplication of those two numbers gives a number n which is factorized 50 times using Shor's Algorithm in 2 steps.

As part of Step 1 for each of the 50 combinations the program displays the three calculated values n = pm1*pm2 in Cell (3,C) x in Cell (3,D) and q in Cell (3,E). q = 2^x

As part of Step 2 for each of the 50 combinations x^a mod n is calculated as a function of a. This calculation terminates when the result is 1 or is equal to any previous calculated value.
When the result is 1 the periodicity is equal to a. This value is stored in Cell (3,G).

When the periodicity is even the calculation is of Type 1

When the periodicity is odd the calculation is of Type 3. In that case Shor's Algorithm does not work.

When the caculation detects any previous result not equal to 1 the calculation is of Type 2

Type is stored in Cell (3,E) as T1, T2 or T3

What the program shows is that the periodicity becomes very large and in worst cases is almost equal to: pm1*pm2/2. This challenges the usefulness of Shor's Algorithm.

The program also works for rather large prime number combinations.

For example: try 1000 and 4000.

The largest periodicity value is 5000000.

Feedback

Back to my home page: Contents of This Document