Let 'N' be any odd composite with factors 'p' & 'q'. Then there exist following property for many odd composites S^2 = y^2(mod p) = (y + 1)^2(mod q),
Where
S = Floor(Sqrt(2N+4)) or Ceiling(Sqrt(2N+4))
such that Floor(Sqrt((N+2)^2 - S^2)) = N and
Floor(Sqrt((N+2)^2 - (S-1)^2)) = N +1,
Then calculate k = 4N+4-(S^2),
y = Floor(Sqrt(abs[(2N-k)- S])),
Therefore using 'S' & 'y' we can factorize 'N' such that
p = GCD([S^2-y^2], N) &
q =GCD([S^2-(y+1)^2], N).
{For example. N = 132289 = 263*503,
S = Ceiling(Sqrt((2*132289)+4)) = 515,
k = (4*132289)+4-(515^2) = 263935,
then it is found that
S^2 = 515^2 = 11^2(mod 263) = (11+1)^2(mod 503) here y = 11 = Floor(Sqrt([(2*132289)-263935] -515). }
For some other numbers S = Floor(√(4N+4)) or S = Floor(√(2N+4) and y = Floor(√(k-S)) or nearer to it.
{For example. N = 1091501 = 523*2087,
S = Floor(√((2*1091501)+4)) = 2089,
k = (4*1091501)+4-(2089^2) = 2087,
then it is found that S^2 = 2089^2 = 2^2(mod 2087) = (2+1)^2(mod 523) here y = 2 = √(S-k)+1 =√(2089-2087)+1}
{For example. N = 1091501 = 523*2087,
S = Floor(√((2*1091501)+4)) = 2089,
k = (4*1091501)+4-(2089^2) = 2087,
then it is found that S^2 = 2089^2 = 2^2(mod 2087) = (2+1)^2(mod 523) here y = 2 = √(S-k)+1 =√(2089-2087)+1}
No comments:
Post a Comment