Monday, February 2, 2015

Odd Composite Special Case Property

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}

No comments: