Talk:Fermat's factorization method

Archives

This page has archives. Sections older than 365 days may be automatically archived by when more than 2 sections are present.

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)

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. — Preceding unsigned comment added by Yourskadhir (talk • contribs) 01:15, 2 December 2012 (UTC)[reply]

Mod 16 optimization

Need to mention that the optimization section needs some remarks, there are more variants of a.
For each N mod 16, the a mod 16 must be as follows:

N mod 16	a mod 16
1 or D	1,7,9,F
3 or B	2,6,A,E
5 or 9	3,5,B,D
7 or F	0,4,8,C

-in order for a² - N to be square.
As you can notice, all even N are skipped - Fermat method does not test them.

Example in hexadecimal format:
Let N be 1751₁₆.
The right digit of N is 1, from table, right digit of a can only be 1,7,9 or F.
√1751₁₆ = 4E, so we test for a only 4F, 51, 57 and get result a² - N = 57₁₆² - 1751₁₆ as a perfect square.

Is this better than in the article? Got it clear now? Should this be in the article page?

--Neeme Vaino (talk) 20:20, 2 April 2010 (UTC)[reply]

The sieve section should mention that you can combine the results of the sieve operations using a variant of Euclid's algorithm.

Thus, using the given example N = 2345678917, we have N = 5 (mod 16) which requires a = ±3 (mod 8) so as to give b^2 = 4 (mod 16) which is the only possible value for a which leaves b^2 = a^2 - N as a possible square. Similarly N = 7 (mod 9) forces a = ±4 (mod 9) in order for b^2 to be a possible square. Combining a = ±3 (mod 8) with a = ±4 (mod 9) gives a = ±5 or ±13 (mod 72).

Now we note that N = 2 (mod 5) which forces a = ±1 (mod 5), and we can combine this result with the previous results to leave a = ±{59, 131, 139 or 149} (mod 360).

So, after considering only the primes 2, 3 and 5, we see that there are only 8 possible values for a in each period of 360 integers. We can add in further conditions, to increase the acceleration further.

62.253.20.134 (talk) 03:09, 16 July 2012 (UTC)[reply]

Not sure how to write stuff in Wikipedia properly, but I noticed a mistake and this is probably where I should point it out:

"A multiple of four is also a difference of squares: let c and d be even" in the first paragraph is wrong. for example, 8 is a multiple of four (and indeed, a difference of squares), but not a difference of even squares. It is 9-1. The mistake in the argument is that if they are even then you divide the whole equation by 4, and you need to show n/4 is a difference of squares, which it doesn't have to be (8/4=2 isn't a difference of squares) 109.64.51.240 (talk) 15:58, 9 July 2015 (UTC)[reply]