Fermat's factorization method: Difference between revisions

Revision as of 20:53, 6 October 2024

Revision as of 20:35, 2 December 2024

Line 17:

FermatFactor(N): ''// N should be odd''

a ← {{Not a typo|ceiling(sqrt(N))}}

b2b^2 ← a*a - N

'''repeat until''' b2b^2 '''is''' a square:

a ← a + 1

b2b^2 ← a*a - N

// equivalently:

// b2b^2 ← b2b^2 + 2*a + 1''

// a ← a + 1

'''return''' a - {{Not a typo|sqrt(b2b^2)}} ''// or a + {{Not a typo|sqrt(b2b^2)}}''

For example, to factor <math>N = 5959</math>, the first try for ''a'' is the square root of {{math|5959}} rounded up to the next integer, which is {{math|78}}. Then <math>b^2 = 78^2-5959 = 125</math>. Since 125 is not a square, a second try is made by increasing the value of ''a'' by 1. The second attempt also fails, because 282 is again not a square.