Content deleted Content added
→Basic method: The last 3 edits introduced an error here: "b is a square" is not the same as "b is a squared"! Tag: Reverted |
actually there's more errors here, just restoring old correct version for now |
||
Line 17:
FermatFactor(N): ''// N should be odd''
a ← {{Not a typo|ceiling(sqrt(N))}}
'''repeat until'''
a ← a + 1
// equivalently:
//
// a ← a + 1
'''return''' a - {{Not a typo|sqrt(
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.
| |||