# examples of the Fermat method on a few integers

Take $n=2039183$. The square root is approximately 1428, so that’s what we set our iterator’s initial state to. The test cap is 339865.

At $i=1428$, we find that $\sqrt{{1428}^{2}-2039183}=1$, clearly an integer.

Then, $1428-1=1427$ and $1428+1=1429$. By multiplication^{}, we verify that $2039183=1427\cdot 1429$, indeed. It is the product of a twin prime^{}. By trial division^{}, this would have taken 225 test divisions.

However, there are integers for which trial division performs much better than the Fermat method. For example, take $n=1411041$. Our iterator starts at 1188 and the test cap is 235175.

At $i=1188$, we find that $\sqrt{{1188}^{2}-1411041}\approx 17.4068952$. Similar frustration at 1189, 1190, etc.

It’s not until we get to $i=235175$ that we finally get $\sqrt{{235175}^{2}-1411041}=235172$.

Then, $235175-235172=3$, and $235175+235172=470347$, and we verify that indeed $3\cdot 470347=2039183$. This took 233987 instances of squaring, subtraction and square root extraction, which would have taken just 196 test divisions in trial division.

How about 4393547637856664251490043044051018234292171475232959? The square root is approximately 6628384145368058140794809 and the test cap is 732257939642777375248340507341836372382028579205495. At worst, the Fermat method could take as many as 732257939642777375248340500713452227013970438410686 instances of squaring, subtraction and square root extraction to give a result. Clearly a more sophisticated method is needed to factorize an integer of this magnitude.

Title | examples of the Fermat method on a few integers |
---|---|

Canonical name | ExamplesOfTheFermatMethodOnAFewIntegers |

Date of creation | 2013-03-22 16:39:28 |

Last modified on | 2013-03-22 16:39:28 |

Owner | PrimeFan (13766) |

Last modified by | PrimeFan (13766) |

Numerical id | 5 |

Author | PrimeFan (13766) |

Entry type | Example |

Classification | msc 11A41 |