Fermat's Factorization Method - Fermat's and Trial Division

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)

    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)