Talk:Fermat's factorization method: Difference between revisions

Revision as of 07:43, 3 December 2012

Revision as of 16:54, 7 December 2012

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

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)