Talk:Fermat's factorization method
 | Mathematics Start‑class Low‑priority | |||||||||
| ||||||||||
The 1st paragraph under sieve imrovements is very unclear. I assume some of these restrictions come about because of the value of N mod 20 etc? This should be explained. This paragraph needs to be expanded with a better step-by-step explanation. —Preceding unsigned comment added by 210.84.56.174 (talk) 02:52, 21 November 2007 (UTC)
The whole article is unclear...
10:55, 6 September 2008 (UTC)
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)
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 175116.
The right digit of N is 1, from table, right digit of a can only be 1,7,9 or F.
√175116 = 4E, so we test for a only 4F, 51, 57 and get result a² - N = 57162 - 175116 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)
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.