Shor's Algorithm - Fast Fourier Transform of 3*5

The following table shows Fast Fourier Transform of n=15
q = 512, periodicity r = 2, M = 255, Register 2 = 6, a0 = 2

c FFT
0 255.00
256 255.00

The following table shows Fast Fourier Transform of n=15

q = 512, periodicity r = 2, M = 256, Register 2 = 9, a0 = 1

c FFT
0 256.00
256 256.00

The two tables are slightly different.

All FFT state values from 0 to 20

c FFT c FFT c FFT c FFT c FFT c FFT c FFT c FFT
0 255.00 1 1.00 2 1.00 3 1.00 4 1.00 5 1.00 6 1.00 7 1.00
8 1.00 9 1.00 10 1.00 11 1.00 12 1.00 13 1.00 14 1.00 15 1.00
16 1.00 17 1.00 18 1.00 19 1.00 20 1.00 21 1.00 22 1.00 23 1.00

Probability values > 0.1%

Register 2 = 6, a0 = 2
c p(c)
0 49.80
256 49.80

Grand probability total = 100.0

Register 2 = 9, a0 = 1
c p(c)
0 50.00
256 50.00

Grand probability total = 100.0

Shor's Algorithm - Fast Fourier Transform of 7*17

The following table shows Fast Fourier Transform of n=119
q = 32768, periodicity r = 8, Register 2 = 1, a0 = 0

c FFT
0 4096.00
4096 4096.00
8192 4096.00
12288 4096.00
16384 4096.00
20480 4096.00
24576 4096.00
28672 4096.00

All FFT state values from 0 to 20

c FFT c FFT c FFT c FFT c FFT c FFT c FFT c FFT
0 4096.00 1 0.00 2 0.00 3 0.00 4 0.00 5 0.00 6 0.00 7 0.00
8 0.00 9 0.00 10 0.00 11 0.00 12 0.00 13 0.00 14 0.00 15 0.00
16 0.00 17 0.00 18 0.00 19 0.00 20 0.00 21 0.00 22 0.00 23 0.00

Probability values > 0.1%

c p(c)
0 12.50
4096 12.50
8192 12.50
12288 12.50
16384 12.50
20480 12.50
24576 12.50
28672 12.50

Grand probability total = 100%

Shor's Algorithm - Fast Fourier Transform of 5*11

The following table shows Fast Fourier Transform of 55
q = 8192, periodicity r = 20, Register 2 = 28, a0 = 9

c FFT c FFT c FFT c FFT c FFT c FFT
0 410.00
404 22.02 405 26.84 406 34.32 407 47.57 408 77.38 409 206.54
410 310.12 411 88.69 412 51.79 413 36.60 414 28.31 415 23.09
816 24.27 817 35.16 818 64.19 819 383.50
820 95.47 821 42.25 822 27.05
1226 27.05 1227 42.25 1228 95.47 1229 383.50
1230 64.19 1231 35.16 1232 24.27
1633 23.09 1634 28.31 1635 36.60 1636 51.79 1637 88.69 1638 310.12
1639 206.54 1640 77.38 1641 47.57 1642 34.32 1643 26.84 1644 22.02
2048 410.00
2452 22.02 2453 26.84 2454 34.32 2455 47.57 2456 77.38 2457 206.54
2458 310.12 2459 88.69 2460 51.79 2461 36.60 2462 28.31 2463 23.09
2864 24.27 2865 35.16 2866 64.19 2867 383.50
2868 95.47 2869 42.25 2870 27.05
3274 27.05 3275 42.25 3276 95.47 3277 383.50
3278 64.19 3279 35.16 3280 24.27
3681 23.09 3682 28.31 3683 36.60 3684 51.79 3685 88.69 3686 310.12
3687 206.54 3688 77.38 3689 47.57 3690 34.32 3691 26.84 3692 22.02
4096 410.00
4500 22.02 4501 26.84 4502 34.32 4503 47.57 4504 77.38 4505 206.54
4506 310.12 4507 88.69 4508 51.79 4509 36.60 4510 28.31 4511 23.09
4912 24.27 4913 35.16 4914 64.19 4915 383.50
4916 95.47 4917 42.25 4918 27.05
5322 27.05 5323 42.25 5324 95.47 5325 383.50
5326 64.19 5327 35.16 5328 24.27
5729 23.09 5730 28.31 5731 36.60 5732 51.79 5733 88.69 5734 310.12
5735 206.54 5736 77.38 5737 47.57 5738 34.32 5739 26.84 5740 22.02
6144 410.00
6548 22.02 6549 26.84 6550 34.32 6551 47.57 6552 77.38 6553 206.54
6554 310.12 6555 88.69 6556 51.79 6557 36.60 6558 28.31 6559 23.09
6960 24.27 6961 35.16 6962 64.19 6963 383.50
6964 95.47 6965 42.25 6966 27.05
7370 27.05 7371 42.25 7372 95.47 7373 383.50
7374 64.19 7375 35.16 7376 24.27
7777 23.09 7778 28.31 7779 36.60 7780 51.79 7781 88.69 7782 310.12
7783 206.54 7784 77.38 7785 47.57 7786 34.32 7787 26.84 7788 22.02

What the above tables shows is that the highest FFT state values come in clusters.

The highest FFT state values are in lightgreen
The FFT state value for c = 4915 is equal to 383.50. That same value is also calculated for c = 819, 1229, 2867, 3267, 5325, 6963 and 7373.

All FFT state values from 0 to 23 and from 387 to 434

c FFT c FFT c FFT c FFT c FFT c FFT c FFT c FFT
0 410.00 1 0.40 2 0.40 3 0.40 4 0.40 5 0.40 6 0.40 7 0.40
8 0.40 9 0.40 10 0.40 11 0.40 12 0.40 13 0.40 14 0.40 15 0.40
16 0.40 17 0.40 18 0.40 19 0.40 20 0.40 21 0.40 22 0.40 23 0.40
387 5.38 388 5.63 389 5.91 390 6.21 391 6.55 392 6.93 393 7.36 394 7.83
395 8.38 396 9.00 397 9.73 398 10.57 399 11.58 400 12.80 401 14.30 402 16.20
403 18.67 404 22.02 405 26.84 406 34.32 407 47.57 408 77.38 409 206.54 410 310.12
411 88.69 412 51.79 413 36.60 414 28.31 415 23.09 416 19.50 417 16.88 418 14.89
419 13.32 420 12.05 421 11.01 422 10.13 423 9.39 424 8.74 425 8.19 426 7.70
427 7.26 428 6.87 429 6.53 430 6.22 431 5.93 432 5.67 433 5.44 434 5.22

The above table shows is that the FFT state values starts with a maximum at c = 0, and then decreases. There after it slowly increases to a possible maximum at c = 410 and then decreases and increases again.

Probability values > 0.05%

c p(c) c p(c) c p(c) c p(c) c p(c) c p(c)
0 5.005
407 0.067 408 0.178 409 1.270 410 2.863 411 0.234 412 0.080
818 0.123 819 4.379 820 0.271 821 0.053
1227 0.053 1228 0.271 1229 4.379 1230 0.123
1636 0.080 1637 0.234 1638 2.863 1639 1.270 1640 0.178 1641 0.067
2048 5.005
2455 0.067 2456 0.178 2457 1.270 2458 2.863 2459 0.234 2460 0.080
2866 0.123 2867 4.379 2868 0.271 2869 0.053
3275 0.053 3276 0.271 3277 4.379 3278 0.123
3684 0.080 3685 0.234 3686 2.863 3687 1.270 3688 0.178 3689 0.067
4096 5.005
4503 0.067 4504 0.178 4505 1.270 4506 2.863 4507 0.234 4508 0.080
4914 0.123 4915 4.379 4916 0.271 4917 0.053
5323 0.053 5324 0.271 5325 4.379 5326 0.123
5732 0.080 5733 0.234 5734 2.863 5735 1.270 5736 0.178 5737 0.067
6144 5.005
6551 0.067 6552 0.178 6553 1.270 6554 2.863 6555 0.234 6556 0.080
6962 0.123 6963 4.379 6964 0.271 6965 0.053
7371 0.053 7372 0.271 7373 4.379 7374 0.123
7780 0.080 7781 0.234 7782 2.863 7783 1.270 7784 0.178 7785 0.067

Grand total of all probability values is 100%

The highest p(c) values are in lightgreen

5 X                   X                   X                   X                   X 
  X                   X                   X                   X                   X 
  X                   X                   X                   X                   X 
4 X                   X                   X                   X                   X 
  X       X   X       X       X   X       X       X   X       X       X   X       X 
  X       X   X       X       X   X       X       X   X       X       X   X       X 
3 X       X   X       X       X   X       X       X   X       X       X   X       X 
  X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X 
  X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X 
2 X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X 
  X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X 
  X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X 
1 X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X 
  X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X 
  X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X 
0 X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X   X 
  0      819    1638     2458    3277    4096    4915    5734    6554    7373    8192 
     410    1229    2048    2867     3687   4506     5325    6144    6963    7782
Graphical Probability Table

This table does not match the probability values as shown at page 20 of 22 in document: "Shor's Algorithm for factorizing large numbers" by G. Eric Moorhouse, UW Math http://www.uwyo.edu/moorhouse/slides/talk2.pdf. In that document the values at c = 0, c =2048, c = 4096 and c = 6144 (c = 8192) are zero.

Shor's Algorithm - Fast Fourier Transform of 5*17

The following table shows Fast Fourier Transform of n=85
q = 16384, M=1024, periodicity r = 16, Register 2 = 1, a0 = 0

c FFT
0 1024.00
1024 1024.00
2048 1024.00
3072 1024.00
4096 1024.00
5120 1024.00
6144 1024.00
7168 1024.00
8192 1024.00
9216 1024.00
10240 1024.00
11264 1024.00
12288 1024.00
13312 1024.00
14336 1024.00
15360 1024.00

Probability values > 0.05%

c p(c)
0 6.25
1024 6.25
2048 6.25
3072 6.25
4096 6.25
5120 6.25
6144 6.25
7168 6.25
8192 6.25
9216 6.25
10240 6.25
11264 6.25
12288 6.25
13312 6.25
14336 6.25
15360 6.25

Grand probability total = 100.000

Shor's Algorithm - Fast Fourier Transform of 83*101

The following table shows Fast Fourier Transform of n=8383
q = 268435456, M=65472, periodicity r = 4100, Register 2 = 2357, a0 = 3921

c FFT c FFT c FFT c FFT c FFT c FFT c FFT c FFT
0 65472.00
65465 575.07 65466 669.94 65467 802.29 65468 999.79 65469 1326.28 65470 1969.38 65471 3823.07 65472 65052.94
65473 4332.41 65474 2096.43 65475 1382.79 65476 1031.63 65477 822.70 65478 684.15 65479 585.55 65480 511.79
130937 1118.26 130938 1300.85 130939 1554.69 130940 1931.61 130941 2549.77 130942 3749.76 130943 7083.29 130944 63805.39
130945 9104.96 130946 4249.33 130947 2771.38 130948 2056.23 130949 1634.46 130950 1356.27 130951 1159.00 130952 1011.84
196409 1609.50 196410 1869.64 196411 2230.07 196412 2762.66 196413 3629.44 196414 5288.78 196415 9743.22 196416 61758.06
196417 14234.81 196418 6381.94 196419 4112.97 196420 3034.23 196421 2403.77 196422 1990.24 196423 1698.11 196424 1480.77
261881 2031.07 261882 2356.06 261883 2804.87 261884 3464.88 261885 4531.09 261886 6545.15 261887 11782.33 261888 58957.86
261889 19627.12 261890 8413.21 261891 5354.15 261892 3926.48 261893 3099.91 261894 2560.82 261895 2181.46 261896 1900.00
327353 2368.21 327354 2743.40 327355 3259.84 327356 4015.80 327357 5228.24 327358 7489.41 327359 13196.99 327360 55468.69
327361 25177.33 327362 10260.15 327363 6442.86 327364 4695.80 327365 3694.10 327366 3044.63 327367 2589.38 327368 2252.57
392825 2609.58 392826 3018.95 392827 3580.66 392828 4399.17 392829 5702.77 392830 8104.32 392831 13999.95 392832 51369.68
392833 30773.76 392834 11840.34 392835 7330.37 392836 5308.41 392837 4160.74 392838 3421.11 392839 2904.75 392840 2523.82
458297 2747.64 458298 3174.49 458299 3758.35 458300 4605.39 458301 5945.31 458302 8384.84 458303 14219.51 458304 46753.01
458305 36300.45 458306 13074.52 458307 7973.12 458308 5735.32 458309 4478.39 458310 3673.35 458311 3113.64 458312 2701.94
523769 2778.90 523770 3206.45 523771 3789.50 523772 4631.70 523773 5955.22 523774 8337.78 523775 13898.11 523776 41721.46
523777 41640.14 523778 13889.07 523779 8334.53 523780 5953.56 523781 4630.69 523782 3788.82 523783 3205.97 523784 2778.54
589241 2703.94 589242 3116.00 589243 3676.23 589244 4482.07 589245 5740.39 589246 7981.02 589247 13090.65 589248 36385.63
589249 46677.30 589250 14218.52 589251 8386.59 589252 5947.24 589253 4607.18 589254 3759.97 589255 3175.94 589256 2748.95
654713 2527.34 654714 2908.86 654715 3426.04 654716 4166.90 654717 5316.58 654718 7342.40 654719 11862.48 654720 30860.96
654721 51301.27 654722 14007.78 654723 8111.27 654724 5708.36 654725 4403.77 654726 3584.55 654727 3022.32 654728 2612.54
720185 2257.47 720186 2595.06 720187 3051.39 720188 3702.44 720189 4706.66 720190 6458.40 720191 10287.10 720192 25264.72
720193 55409.11 720194 13214.18 720195 7501.58 720196 5237.40 720197 4023.11 720198 3265.91 720199 2748.59 720200 2372.74
785657 1906.06 785658 2188.46 785659 2569.11 785660 3110.04 785661 3939.54 785662 5372.47 785663 8443.70 785664 19712.91
785665 58908.45 785666 11809.23 785667 6562.37 785668 4543.62 785669 3474.71 785670 2812.94 785671 2362.92 785672 2037.02
851129 1487.75 851130 1706.15 851131 1999.71 851132 2415.29 851133 3048.93 851134 4133.28 851135 6414.68 851136 14317.31
851137 61719.95 851138 9779.88 851139 5310.68 851140 3644.98 851141 2774.69 851142 2239.88 851143 1877.92 851144 1616.66
916601 1019.46 916602 1167.75 916603 1366.53 916604 1646.89 916605 2071.97 916606 2792.85 916607 4283.01 916608 9182.60
916609 63779.46 916610 7129.54 916611 3775.78 916612 2567.84 916613 1945.45 916614 1565.90 916615 1310.27 916616 1126.39
982073 519.74 982074 594.66 982075 694.82 982076 835.55 982077 1047.79 982078 1404.58 982079 2129.83 982080 4403.80
982081 65039.76 982082 3878.46 982083 1998.80 982084 1346.30 982085 1014.97 982086 814.50 982087 680.16 982088 583.86
1047553 65471.90
1113018 566.28 1113019 659.71 1113020 790.06 1113021 984.60 1113022 1306.23 1113023 1939.91 1113024 3767.55 1113025 65065.91
1113026 4261.14 1113027 2063.05 1113028 1361.00 1113029 1015.46 1113030 809.85 1113031 673.49 1113032 576.43 1113033 503.83

What the above tables shows is that the highest FFT state values come in clusters.
The highest FFT state values are in lightgreen

Probability values > 1/r = 1/4100

c p(c) c p(c) c p(c) c p(c) c p(c) c p(c)
0 0.02439
65472 0.02408
130943 0.00029 130944 0.02316 130945 0.00047
196415 0.00054 196416 0.02170 196417 0.00115
261887 0.00079 261888 0.01978 261889 0.00219 261890 0.00040
327358 0.00032 327359 0.00099 327360 0.01751 327361 0.00361 327362 0.00060
392830 0.00037 392831 0.00112 392832 0.01501 392833 0.00539 392834 0.00080 392835 0.00031
458302 0.00040 458303 0.00115 458304 0.01244 458305 0.00750 458306 0.00097 458307 0.00036
523774 0.00040 523775 0.00110 523776 0.00990 523777 0.00987 523778 0.00110 523779 0.00040
589246 0.00036 589247 0.00098 589248 0.00753 589249 0.01240 589250 0.00115 589251 0.00040
654718 0.00031 654719 0.00080 654720 0.00542 654721 0.01497 654722 0.00112 654723 0.00037
720191 0.00060 720192 0.00363 720193 0.01747 720194 0.00099 720195 0.00032
785663 0.00041 785664 0.00221 785665 0.01975 785666 0.00079 785667 0.00025
851136 0.00117 851137 0.02167 851138 0.00054
916608 0.00048 916609 0.02315 916610 0.00029
982081 0.02407
1047553 0.02439
1113025 0.02409
1178496 0.00028 1178497 0.02318 1178498 0.00046
1243968 0.00054 1243969 0.02173 1243970 0.00114
1309440 0.00079 1309441 0.01981 1309442 0.00217 1309443 0.00040
1374911 0.00032 1374912 0.00099 1374913 0.01754 1374914 0.00358 1374915 0.00060
1440383 0.00037 1440384 0.00111 1440385 0.01505 1440386 0.00536 1440387 0.00079 1440388 0.00030
1505855 0.00040 1505856 0.00115 1505857 0.01248 1505858 0.00746 1505859 0.00097 1505860 0.00036
1571327 0.00040 1571328 0.00110 1571329 0.00994 1571330 0.00983 1571331 0.00110 1571332 0.00039
1636799 0.00036 1636800 0.00098 1636801 0.00757 1636802 0.01236 1636803 0.00115 1636804 0.00040

The probability values are becoming smaller. The largest value in each cluster is in lightgreen

Created: 18 March 2003
Modified: 17 April 2003

Back to Q3: Does FFT work?
Back to my home page Contents of This Document