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