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]]

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}

Odd Semi-prime Property

Let N = pq be any odd semiprime. Let 's' be the ceiling of square root of 'N'.
If 's' is even then there exist odd 'l' and k = l + 2 such that (s^2 - k^2) < N < (s^2 - l^2) else
If 's' is odd then there exist even 'l' and k = l + 2 such that (s^2 - k^2) < N < (s^2 - l^2)

Let r = q + Δ,
 where 'Δ' is very small +ve integer compared to 'p' & 'q'

When 2l + 4 < p then pr will be less than and nearer to (s^2 + l^2) and p(r + 1) will be greater than and nearer to  (s^2 + k^2)


When 2l + 4 > p then pr will be greater than and nearer to (s^2 + l^2) and depends upon 2p, p(r + 1) will be either greater or lesser than and nearer to  (s^2 + k^2)

Odd Composite Property

Let N = pq be any odd composite. Let k = 1, 2, 3, ...., p, ...., q, ... n. Let u = (N- 1)/2 & v = u +1. Let x = u^2(mod k) and y = v^2(mod k). Then | x - y | = 0 when k = p or k = q else | x - y | != 0. Let p(r -1) < u^2 < pr where r is some integer and let ps < v^2 < p(s + 1) where s is some integer then s - r = q - 1 or s - r = q - 3.
Example 161 = 7*23, here u (161 -1)/2 = 80, v = 81, 80^2 = 2(mod 7) = 6(mod 23), 81^2 = 2(mod 7) = 6(mod 23). 7*914 < 80^2 < 7*915 and  7*937 < 81^2 < 7*938, 937 - 915 = 22 = 23 -1.

Fermat's Factorization Running Time

Let N = pq  is any odd composite. Let d = 2n be the difference between the two closest factors of 'N'. ( For e.g., 105 = 3x35 = 5x21 = 7x15 here 15 and 7 is close to each other compare to other. Therefore d = 15 - 7 = 8 therefore n = d/2 = 4 ). Let 's' be the floor value of square root of 'N'. Let N = a^2 - b^2 be the Fermat factorization of N. In order to attain best case scenario a - s <= 2 following are the required condition for factors of N. I call these factors as Best Fermat Factors.

Case1: If 'n' is odd then p should be (n(n-4) + 7)/4 and q should be (n(n+4) + 7)/4

Case2: If 'n' is even & m = n/2 is odd then p should be (m(m -2) + 2) and q should be (m(m + 2) + 2)

Case3: If 'n' is even & m = n/2 is also even then p should be (m - 1)^2 and q should be (m + 1)^2

(Note:  Try the practical testing using any numbers even very big numbers then you can understand my ideas. I used the smaller numbers as an inductive proof for simplicity. Please read the 3 cases and its note point. May be explanations won't be in a polished way, please adjust.)


Case 1: Explanation Below
Example1. let d = 2x9 here n = 9 is odd then p = (9x5 + 7)/4 = 13 & q = (9x13 + 7)/4  = 31 Therefore N = 13x31 =  403 = 22^2 - 9^2 and floor value of sqare root of 403 is  20, here a = 22 & s = 20 and a -s = 2.

Note:
Here p = 13 and q = 31 for the given d = 2x9 running time complexity is 2 for Fermat factorization. The other set of factors with same difference like (11, 29), (9, 27)..... (3, 21) the running time complexity will increase gradually and worst case will occur. And the few set of factors greater than p and q with same difference like (15, 33), (17, 35)... will remain same time complexity for Fermat factorization. Let M = rs where s - r = q - p (where q and p are best Fermat factors) and r < p and s < q then time complexity will increase compared to N = pq. For e.g.,  11x29 = 319 = 20^2 - 9^2 floor of square root of 319 is 17. Now 20 - 17 = 3 complexity increased compared to Best Fermat factors (13, 31)


Case2: Explanation Below
Example2. let d = 2x14 here n = 14 is even and m = n/2 = 7 is odd then p = 7*5 + 2 = 37 and q = 7*9 + 2 = 65 Therefore N = 37x65 = 2405 = 51^2 - 14^2 and floor value of square root of 2405 is 49, here a = 51 & s = 49 and a -s = 2.

Note:
Here p = 37 and q = 65 for the given d = 2x14 running time complexity is 2 for Fermat factorization. The other set of factors with same difference like (35,63), (33,61)..... (3, 31) the running time complexity will increase gradually and worst case will occur. And the few set of factors greater than p and q with same difference like (39,67), (41,69)... will remain same time complexity for Fermat factorization.

Case3: Explanation Below
Example3. let d = 2x16 here n = 16 is even and m = n/2 = 8 is even then p = (8-1)^2 = 49 and q = (8 + 1)^2 = 81  Therefore N = 49x81 = 3969 = 65^2 - 16^2 and floor value of square root of 3969 is 63, here a = 65 & s = 63 and a -s = 2.

Note:
Here p = 49 and q = 81 for the given d = 2x16 running time complexity is 2 for Fermat factorization. The other set of factors with same difference like (47,79), (45,77)..... (3, 35) the running time complexity will increase gradually and worst case will occur. And the few set of factors greater than p and q with same difference like (51,83), (53,85)... will remain same time complexity for Fermat factorization.

Conclusion:
Hence irrespective of the difference there exist Best Fermat Factors, so that factorization complexity is easy. The logic that odd composite with least difference will be factored easily and large difference would factored hardly is wrong. Hardness is depends upon the how much the factors are deviated from the Best Fermat Factors. And i had a new methodology to factorize the given number based on above properties.

Hi Everyone

Welcome to the Fantasy of Numbers. This page reveals my own discoveries on Number Theory. Sorry if something i re-introduced which i unaware of.