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	variants of a mod 16
1 or D	8±4±3 = { 1,7,9,F }
3 or B	8±4±2 = { 2,6,A,E }
5 or 9	8±4±1 = { 3,5,B,D }
7 or F	6±4±2 = { 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.
So we test for a only 4F, 51, 57 and get result a² - N = 57₁₆² - 1751₁₆ as a perfect square.

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