Talk:Fermat's factorization method

Mathematics Start‑class Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-priority on the project's priority scale.

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)[reply]

The whole article is unclear... 10:55, 6 September 2008 (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 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]