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:
“For he is not a mortal, as I am, that I might answer him, that we should come to trial together. There is no umpire between us, who might lay his hand on us both.”
—Bible: Hebrew, Job 9:32-33.
Job, about God.
“Major [William] McKinley visited me. He is on a stumping tour.... I criticized the bloody-shirt course of the canvass. It seems to me to be bad “politics,” and of no use.... It is a stale issue. An increasing number of people are interested in good relations with the South.... Two ways are open to succeed in the South: 1. A division of the white voters. 2. Education of the ignorant. Bloody-shirt utterances prevent division.”
—Rutherford Birchard Hayes (1822–1893)