Talk:Fermat's factorization method: Difference between revisions

Revision as of 12:34, 3 April 2010

Revision as of 03:09, 16 July 2012

Line 39:

--[[User:Neeme Vaino|Neeme Vaino]] ([[User talk: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.

[[Special:Contributions/62.253.20.134|62.253.20.134]] ([[User talk:62.253.20.134|talk]]) 03:09, 16 July 2012 (UTC)