Research Links

Simulating the quantum factoring process in Open Office Calc


Aforehand we keep in mind the solution and watch the method unfold.  See Chapter 10 of the book: Algorithms …. for greater detail.

Pick:   

p,q = 7,11    

p*q= 7 * 11 = 77  

 

Factor 77 using Shor's algorithm

Pick relative prime = 5.   (5^r) mod(77)  will be periodic in r.   The following would be set up in a quantum register to have all the values in the register simultaneously and calculate the function results simultaneously.

5^1mod(77)=5  

5^2mod(77)=25  

5^3mod(77)=48  

5^4mod(77)=9  

5^5mod(77)=45

5^6mod(77)=71  

5^7mod(77)=47  

5^8mod(77)=4   

5^9mod(77)=20  

5^10mod(77)=23  

5^11mod(77)=38

5^12mod(77)=36  

5^13mod(77)=26  

5^14mod(77)=53 

5^15mod(77)=34  

5^16mod(77)=16

5^17mod(77)=3  

5^18mod(77)=15  

5^19mod(77)=75   

5^20mod(77)=67  

5^21mod(77)=27  

5^22mod(77)=58

5^23mod(77)=59  

5^24mod(77)=64  

5^25mod(77)=12 

5^26mod(77)=60  

5^27mod(77)=69

5^28mod(77)=37  

5^29mod(77)=31

5^30mod(77)=1  ……… here we see the form of even power of the variable with 1 left over after the mod.  That gives the (x-1)(x+1)=0mod(77)  form

5^31mod(77)=5  

 

After the above results are piled simultaneously in the quantum register a quantum FFT is performed and the period r found to be 30 with high probability.     All the above mod result values are in the register at the same time and not indexed per time or pure number index as far as I know.  A quantum FFT does not yield a spectrum.  It yields a frequency estimate of highest probability of the input waveform.   Frequency as in probability frequency.  However the above mod result values are KNOWN to be in regular spacing so a frequency that we are accustomed to can be calculated.

Thus using

     5^30 -1    have common factors with 77.  

     5^30-1 =  (5^15-1)(5^15+1) 

 

Each of 77's 2 coprime factors have a common factor with only  one of the 2 terms above.   Use Euclid's rule to find the greatest common denominator.  See chapter 1.2.3 of Algorithms.

Demonstrate this to yourself by using greatest common factor calculator webpage with ( 77,30517578126)  & ( 77,30517578124)

   5^15 +1 = 30517578126 = 7 * 4359654018 

   5^15 -1 = 30517578124 =  11 * 2774325284

 

This yields    

     77= 7 * 11      

and the problem is solved.  


More Links

Leave a Reply

Your email address will not be published. Required fields are marked *