Re: JSH: Not obvious? Simple math test.

On Sun, 13 Jan 2008 17:42:48 -0800 (PST), JSH <jstevh@xxxxxxxxx>
wrote:

On Jan 13, 12:58 pm, rossum <rossu...@xxxxxxxxxxxx> wrote:
On Fri, 11 Jan 2008 16:41:10 -0800 (PST), JSH <jst...@xxxxxxxxx>
[snip]

Sounds good. Have fun.

Question for James:

At step 6, if I find that k is not coprime to nT, do I stick with the
same value of alpha and step n (= "go to step 3") or do I give up on
that alpha and move to the next value (= "increment alpha by 1 and go
to step 2")? Currently I am doing the latter.

Shouldn't matter. It just will not work at all if k is not coprime to
nT.
When I was coding it up I decided that the first option was easier so
I built my code that way.

Having coded it I ran mu usual tests:

As I have done previously, I tested James' latest factoring 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 (both forward and reverse) and
random picking.

JSH Results

Fermat average = 8.14 probes.
JSH average = 666.74 probes.
Probe ratio = 1 : 81.889
Trial average = 119.67 probes.
Reverse average = 12.57 probes.
Random average = 737.48 probes.
500 trials, 0 misfactors found.

Average alphas tried per factorisation: 84.812
Average n's tried per factorisation: 195.066


I also ran a second test of a modified version which did not include
the four GCDs with "-p" in them. This meant that there were only four
GCDs evaluated for each allowed combination of alpha, n, k and p where
the unmodified version had eight GCDs. Overall this change reduced
the number of GCDs (= probes) but increased the number of alphas
tried.

JSH Results - omitting the four "-p" GCDs

Fermat average = 7.52 probes.
JSH average = 480.14 probes.
Probe ratio = 1 : 63.831
Trial average = 120.48 probes.
Reverse average = 12.11 probes.
Random average = 748.97 probes.
500 trials, 0 misfactors found.

Average alphas tried per factorisation: 121.374
Average n's tried per factorisation: 279.416


As is usual with James' methods it will factorise the target number,
but has no speed advantage over existing methods.

rossum

.

Relevant Pages

  • Re: JSH: Not obvious? Simple math test.
    ... that alpha and move to the next value (= "increment alpha by 1 and go ... Reverse average = 12.57 probes. ... Average n's tried per factorisation: ... the four GCDs with "-p" in them. ...
    (sci.crypt)
  • Re: JSH: Not obvious? Simple math test.
    ... that alpha and move to the next value (= "increment alpha by 1 and go ... Trial average = 119.67 probes. ... Average alphas tried per factorisation: ... the four GCDs with "-p" in them. ...
    (sci.crypt)
  • Re: JSH: Not obvious? Simple math test.
    ... that alpha and move to the next value (= "increment alpha by 1 and go ... Trial average = 119.67 probes. ... Average alphas tried per factorisation: ... What I did was just add an additional constraint to the standard ...
    (sci.crypt)
  • Re: JSH: Not obvious? Simple math test.
    ... that alpha and move to the next value (= "increment alpha by 1 and go ... Trial average = 119.67 probes. ... Average alphas tried per factorisation: ... What I did was just add an additional constraint to the standard ...
    (sci.crypt)
  • Re: JSH: Not obvious? Simple math test.
    ... that alpha and move to the next value (= "increment alpha by 1 and go ... Trial average = 119.67 probes. ... Average alphas tried per factorisation: ... the four GCDs with "-p" in them. ...
    (sci.crypt)