Content deleted Content added
m Reverted edits by 171.78.187.90 (talk) to last version by 109.64.51.240 |
|||
Line 9:
== Fermat's Factorization Running Time ==
Let N = pq is any odd composite. Let N = a^2 - b^2 is the required Fermat factorization. Let d = 2n be the difference between the two closest factors of 'N'. Let 's' is the floor value of square root of N.
In order to attain best case scenario a - s <= 2 following are the minimum required 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
Line 17 ⟶ 18:
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
Example1. let d = 2x9 here n = 9 is odd then
Note:
Line 25:
Conclusion:
Hence irrespective of the difference
== Mod 16 optimization ==
|