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:
“You may talk about Free Love, if you please, but we are to have the right to vote. To-day we are fined, imprisoned, and hanged, without a jury trial by our peers. You shall not cheat us by getting us off to talk about something else. When we get the suffrage, then you may taunt us with anything you please, and we will then talk about it as long as you please.”
—Lucy Stone (1818–1893)
“For in the division of the nations of the whole earth he set a ruler over every people; but Israel is the Lord’s portion: whom, being his firstborn, he nourisheth with discipline, and giving him the light of his love doth not forsake him. Therefore all their works are as the sun before him, and his eyes are continually upon their ways.”
—Apocrypha. Ecclesiasticus 17:17-9.