Thursday, March 5, 2015

Euler's Totient Function of Odd Composite

Let 'N'  be any odd composite. 

Find semi-prime Sp = uv such that 

(2u+1)(2v+1) <= N <= 3(2Sp+1). or N <= (2u+1)(2v+1) < 3(2Sp+1)

 [[ For example let N = 65 then required semi-prime is 14 = 2*7 such that 65 < (2*2 + 1)(2*7 +1)  < 3*(2*14 + 1) i.e., 65 < 5*15 < 3*29 i.e., 65 < 75 < 87]]
{{ Note: Finding Semi-prime Sp will be optimized through Trial & Error }}

Let Lsp be any semiprime nearer and lesser than Sp compared to other.

Then Euler's Totient function Phi(N) = 4*(Sp - k) where 0 <=  k <= (Sp - Lsp).

[[ For example for 65 = 5*13 Phi(65) = 4*12 = 48 =  4*(14-2) Look above example Sp = 14, Lsp = 9, Sp - Lsp = 14-9 = 5; here we saw that 0 < k < 5]]

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}