Re: is it sufficient to solve factoring problem

I'm trying to understand your solution in a theoretical way.
As to my poor mathematical backgroud, I need help to check my uncertain
understanding as follows:

let K=f*phi(N)= e*d-1, phi(N) = 2^i *a , f= 2^j *b, then K =
2^{i+j}*a*b,

>Divide K by 2 until it is odd.
It follows K = a*b;

>Take a random X such that 1 < X < N-1.
>Compute X^K mod N
>If X = 1 or X = -1, take an other X and redo the previous step.

if X=1, it follows that: X is in subgroups with order of a's divisors,
the total amount of that kind member is a. And X is a quadratic
residue, and can be rewritten as g^{2^i} where g is not in those
subgroups. When it relates to Z^*_p \times Z^*_q, we could get the
result pair (1,1)

if X=-1, it follows that: X can be rewritten as g^{2^(i-1)} where g is
not a quadratic residue. When it relates to Z^*_p \times Z^*_q, we
could get the result pair (-1,-1)

>Compute the sequence X[i+1] = X[i]^2 mod N until X[i+1] = 1. and check whether X[i] = -1 or not.
>if not, gcd(X[i] +/- 1, N) gives the factors of N.

X[i] != -1 and X[i+1]=1 means we could get result pair of X[i] as
(1,-1) or (-1,1).
We denote s*q +t*p=1 according to gcd(p,q)=1, Using the chinese
remainder theorem, (1,-1) could be rewritten as sp-tq.so X[i]+1 =
sp-tq+1 = 2sp, and gcd(X{i]+1,N) = p at last.
Received on Mon May 1 02:06:06 2006