As I have done previously, I tested James' latest factoring method, as
per his March 5th blog entry, 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 (both
forward and reverse) and random picking.
Fermat average = 6.96 probes.
JSH average = 1.11 probes.
Probe ratio = 1 : 0.160
Trial average = 120.15 probes.
Reverse average = 11.43 probes.
Random average = 757.46 probes.
500 trials, 0 misfactors found.
Average alphas tried per factorisation: 5.184
This is much better than usual James, your current method filters out
unlikely values before calculating the GCD (counted as "probes"), it
is good at focusing in on the likely possibilities.
Three points. Firstly I think there is a typo in your March 5th blog
entry, at one point you talk about "f_1 - p must be less than f_1",
but later you say "p - f_1 is smaller than it [= f_1]". I have gone
with the second version since the first version just says that p is
positive.
Secondly, since I do not know what f_1 is I just started p at the cube
root of nT and worked downwards. This is probably OK for RSA style
numbers, but will not work in general. For a more general method you
would probably have to start p low and work upwards just to be sure
that p < f_1 as required.
Thirdly, you say that k is incremented from k_0 by steps of abs(2ap).
When I tried this about 300 out of 500 trials resulted in a misfactor.
I changed the loop to step through all possible values of k between
k_0 and the maximum you state, k_0 + abs(2ap) * k_0 / 2p. With this
change there were no misfactors. You may want to revisit this part of
your work.
I will now do some work on absolute, rather than relative, timings.
Good work James, much better than your usual results.
rossum
|
