Factor 891612722879 by shors algorithm Factor 891612722879 b

Solution

procedure shor(int number) { int width=ceil(log(number,2)); // size of number in bits qureg reg1[2*width]; // first register qureg reg2[width]; // second register int qmax=2^width; int factor; // found factor int m; real c; // measured value int x; // base of exponentiation int p; int q; // rational approximation p/q int a; int b; // possible factors of number int e; // e=x^(q/2) mod number if number mod 2 == 0 { exit \"number must be odd\"; } if testprime(number) { exit \"prime number\"; } if testprimepower(number) { exit \"prime power\"; }; { { // generate random base x=floor(random()*(number-3))+2; } until gcd(x,number)==1; print \"chosen random x =\",x; Mix(reg1); // Hadamard transform expn(x,number,reg1,reg2); // modular exponentiation measure reg2; // measure 2nd register dft(reg1); // Fourier transform measure reg1,m; // measure 1st register reset; // clear local registers if m==0 { // failed if measured 0 print \"measured zero in 1st register. trying again ...\"; } else { c=m*0.5^(2*width); // fixed point form of m q=denominator(c,qmax); // find rational approximation p=floor(q*m*c+0.5); print \"measured\",m,\", approximation for\",c,\"is\",p,\"/\",q; if q mod 2==1 and 2*q1 and factor