Talk:Fermat's factorization method: Difference between revisions

Revision as of 03:09, 16 July 2012

Revision as of 01:15, 2 December 2012

Line 7:

The whole article is unclear...

10:55, 6 September 2008 (UTC)

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

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)

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 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. Similarly condition hold for other cases also.

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.

== Mod 16 optimization ==