Fermat's and Trial Division
Consider trying to factor the prime number N=2345678917, but also compute b and a-b throughout. Going up from, we can tabulate:
| a: | 48433 | 48434 | 48435 | 48436 |
| b2: | 76572 | 173439 | 270308 | 367179 |
| b: | 276.7 | 416.5 | 519.9 | 605.9 |
| a-b: | 48156.3 | 48017.5 | 47915.1 | 47830.1 |
In practice, one wouldn't bother with that last row, until b is an integer. But observe that if N had a subroot factor above, Fermat's method would have found it already.
Trial division would normally try up to 48432; but after only four Fermat steps, we need only divide up to 47830, to find a factor or prove primality.
This all suggests a combined factoring method. Choose some bound ; use Fermat for factors between and . This gives a bound for trial division which is . In the above example, with the bound for trial division is 47830. A reasonable choice could be giving a bound of 28937.
In this regard, Fermat's method gives diminishing returns. One would surely stop before this point:
| a: | 60001 | 60002 |
| b2: | 1254441084 | 1254561087 |
| b: | 35418.1 | 35419.8 |
| a-b: | 24582.9 | 24582.2 |
Read more about this topic: Fermat's Factorization Method
Famous quotes containing the words trial and/or division:
“Looks like we got a trial ahead of us. But it’s not the first time. We’ve had to go it alone before, and we’ll have to go it alone again. We’re tough. We’ve had to be tough ever since Brother Brigham led our people across the plain. Well, they survived and I dang it, we’ll, well, we’ll survive too. Now put out your fires and get to your wagons.”
—Frank S. Nugent (1908–1965)
“Imperialism is capitalism at that stage of development at which the dominance of monopolies and finance capitalism is established; in which the export of capital has acquired pronounced importance; in which the division of the world among the international trusts has begun, in which the division of all territories of the globe among the biggest capitalist powers has been completed.”
—Vladimir Ilyich Lenin (1870–1924)