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 14282-2039183=1, clearly an integer.

Then, 1428-1=1427 and 1428+1=1429. By multiplicationPlanetmathPlanetmath, we verify that 2039183=14271429, indeed. It is the product of a twin primeMathworldPlanetmath. By trial divisionMathworldPlanetmath, 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 11882-141104117.4068952. Similar frustration at 1189, 1190, etc.

It’s not until we get to i=235175 that we finally get 2351752-1411041=235172.

Then, 235175-235172=3, and 235175+235172=470347, and we verify that indeed 3470347=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