Any integer N can be written as
N pα1 pα2 pαm
N 1535, α1 α2 1, p1 3,p2 5.
Definition 1 Greatest Common Divisor (GCD) of integers a and b is the largest integer x s.t. x|a and x|b (here | denotes ”divides without a reminder”)
Copyright By PowCoder代写 加微信 powcoder
a33218, b35230 gcdpa, bq 3 2 6.
Let L be the number of bits in the binary representation of N, that is N2 n1 nL, nj 0,1 (Ex. If N 15, then N2 l1o1m1o1on)
12m where αj are positive integers and pj are primes.
Let z be an integer such that
1. z2 pmod Nq 1
2.zpmodNq1(ifzpmodNq1,thenz2 pmodNq1,butwedo not need this case)
3. zpmodNqN1(ifzpmodNqN1,thenz2 pmodNq1,and so we would like to exclude this possibility)
Theorem 1 gcdpz1, Nq or(and) gcdpz1, Nq is (are) non-trivial factor(s) of N.
Note that gcdpz 1,Nq and gcdpz 1,Nq can be computed using only OpL3q Opplog2 Nq3q operations using Euclid’s algorithm.
Theorem 2 Let x be an integer chosen uniformly randomly subject to re- quirements
1 ¤ x ¤ N 1
x is co-prime to N, i.e. gcdpx, Nq 1
be the order of x, i.e., xr pmod Nq1. Then
r{2 1 Prprisevenandx pmodNqN1q¥12m.
If x is such as described in Theorem 2, then we take z xr{2.
Recall that m is the number of primes in factorization of N pα1 pα2 pαm ;
Note that we do not need to check condition 3 formulated for Theo- rem 1, since since if xr{2 pmod Nq 1 then the order of x is r{2, but we assumed that the order is r.
Algorithm for finding a factor of N
1. Randomly choose x P r1, N 1s
2. If gcdpx,Nq ¡ 1, then RETURN gcdpx,Nq (gcdpx,Nq is a nontrivial factor of N), go to Step 7;
else: find the order r of x pmod Nq (use quantum computer here).
3. Ifrisevenandxr{2 pmodNqN1,thenassignzxr{2; elsego to Step 1.
4. Computef1 gcdpz1,Nqandf2 gcdpz1,Nq.
5. If f1|N RETURN(f1q.
6. If f2|N RETURN(f2q.
7. The end.
Example 3 N 15. Assume we randomly took x 7
74 pmod15q1ñr4
xr{2 72 49, 49pmod15q4ñ72 pmod15qN114
ñzxr{2 72 49
f1 gcdpz1,15qgcdp48,15q3 f2 gcdpz1,15qgcdp50,15q5
Both f1 3 and f2 5 are factors of N 15.
Let us also find U for these N and x. Recall that
U|yy Ñ |xy pmod 15qy.
We have L 4 and hence U is a 16 16 permutation matrix that conducts
the mapping
y 7y 7y pmod 15q 000 177 214 14 321 6
Using the correspondence between linear algebra notation and Dirac’s no- tation, we get that the first 4 columns of U are
1000 0000 0000 0000 0 0 0 0 0000 0001
U0100 0000
0000 0000 0000 0000 0000
,
Indeed this matrix moves |0y to |0y:
and |1y into |7y
10 10 U . . ,
. . 00
U .
0 0
0. .
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com