Re: Surrogate factoring and the k/T ratio

On Wed, 28 Feb 2007 18:53:42 -0600, "Nomen Lapetos"
<nospam@xxxxxxxxxx> wrote:

As I have done previously, I tested James' method on 500 random
composite odd numbers that are multiples of two different primes, each
in the range 500 to 1000. The results are compared to Fermat's
method, trial factorisation and random picking.

Each "probe" is a GCD, trial division or equivalent. It is not a
count of the number of k's tried since each k results in many possible
factors of 2k^2 - T. I have indicated separately the mean number of
values of k tried.

Fermat average = 7.238 probes.
JSH average = 6464.48 probes.
Probe ratio = 1 : 893.13
Trial average = 119.35 probes.
Random average = 368.228 probes.
500 tries, 0 misfactors found.
Average k's tried per factorisation: 74.806

As seems usual with James' methods it will factorise the target
number, but more slowly than existing methods.

Previously Tim Peters suggested that multiplying the surrogate by
27,000 would result in a faster factorisation. Trying this
modification the figures are:

Fermat average = 7.65 probes.
JSH average = 1512.02 probes.
Probe ratio = 1 : 197.65
Trial average = 120.134 probes.
Random average = 359.302 probes.
500 tries, 0 misfactors found.
Average k's tried per factorisation: 12.712

These figures would indicate that rather than using

S = 2k^2 - T

for the surrogate (S) it would be better to use

S = 27,000 * 2k^2 - T

However the improvement is not sufficient to make James' method faster
than existing factorisation methods. Even with the suggested
improvement it is nearly 200 times slower than Fermat's method.

rossum


so JSH method is 198 times SLOWER.

On my figures, the original JSH method is about 900 times less
efficient than Fermat. Tim Peters' modification improves it to about
200 times less efficient.

The relative figures are "probes" which is a GCD for JSH and a test
for squareness for Fermat. These may not translate exactly into
timings. These results are typical for James' methods; they work but
not very efficiently. He is not currently in any danger of factoring
an RSA number.

rossum

.