examples of the Fermat method on a few integers
Take . The square root is approximately 1428, so that’s what we set our iterator’s initial state to. The test cap is 339865.
At , we find that , clearly an integer.
However, there are integers for which trial division performs much better than the Fermat method. For example, take . Our iterator starts at 1188 and the test cap is 235175.
At , we find that . Similar frustration at 1189, 1190, etc.
It’s not until we get to that we finally get .
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|
|Date of creation||2013-03-22 16:39:28|
|Last modified on||2013-03-22 16:39:28|
|Last modified by||PrimeFan (13766)|