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:
“Going to trial with a lawyer who considers your whole life-style a Crime in Progress is not a happy prospect.”
—Hunter S. Thompson (b. 1939)
“That crazed girl improvising her music,
Her poetry, dancing upon the shore,
Her soul in division from itself
Climbing, falling she knew not where,
Hiding amid the cargo of a steamship
Her knee-cap broken.”
—William Butler Yeats (1865–1939)