Re: JSH: Surrogate factoring, periodic behavior

On Sep 1, 9:31 am, rossum <rossu...@xxxxxxxxxxxx> wrote:
On Sat, 01 Sep 2007 14:44:13 -0000, JSH <jst...@xxxxxxxxx> wrote:
On Sep 1, 2:34 am, rossum <rossu...@xxxxxxxxxxxx> wrote:
On Sat, 01 Sep 2007 05:21:41 -0000, JSH <jst...@xxxxxxxxx> wrote:
Factored trying 5 surrogates on the fifth surrogate using k=1 where
the start was with n=7.

I ran my usual tests again 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 = 7.58 probes.
JSH average = 1635.83 probes.
Probe ratio = 1 : 215.752
Trial average = 118.52 probes.
Reverse average = 12.12 probes.
Random average = 727.79 probes.

500 trials, 0 misfactors found.

Average k's tried per factorisation: 1.000
Average n's tried per factorisation: 47.040

k was fixed at 1 and n was 7, 8, 9, ...

To support a position that surrogate factoring is worse than any other
method, which is kind of odd, to the thinking person, as how is that
possible?

I do not say that surrogate factoring is worse than "any" other
method. I say that it is worse than some other methods. I show my
evidence for this above. Do you have any evidence to show that I am
wrong?


Yes.

Consider a calculator given to scribes in Old England, like it was
sent backwards through time, and some scribes bang on it, and even
manage to turn it on, but think it is just a weird gizmo with funny
lights.

While one plays with it carefully and figures out how to get it to
work.

Or give a computer to someone who hasn't a clue about what a computer
is and watch them bang on the keyboard.

Surrogate factoring to be worse than random must not be being used
properly as if it were random then it would behave randomly.

Surrogate factoring was not designed as a PRNG, hence I am not
surprised that it performs badly as a PRNG. I suspect the problem is
that it is generating repeats more often than the PRNG (which is
statistically limited in the number of repeats it can generate). If
you repeatedly generate an unsuccessful trial factor then you are
doind unneccessary work since that trial factor has already been tried
and failed.


Hand waving.

Wouldn't a detailed analysis give an answer?


Random means chaos, no reason. The worst you SHOULD get from
something that cannot work better.

No. I can try 1, 1, 1, 1, 1, 1, ... as factors and I will never find
a proper factor. If a proposed method gives more repeats of
non-factors then a PRNG would then it is likely to perform worse than
a PRNG. You might like to analyse the number of times you method
throws up the same potential factor.


Why?

What in the math would indicate that is the way to go?

Can you force Fermat's method to behave worse than random if you try,
by changing how you use it? Yes, if you're smart enough and willing
to do the exercise, you can.

No, then it would no longer be Fermat's method. Fermat's method works
systematically through the options without repeating.


You show lack of imagination.

Can anyone ELSE figure out a way to use Fermat's method in a way that
would make it worse than random?


James Harris

.

Relevant Pages

  • Re: Problem with Random function
    ... Resetting the random number generator is something you ... A PRNG generates a sequence of numbers which appear random. ... periodicity is how long that sequence is before it repeats. ...
    (comp.soft-sys.matlab)
  • Re: JSH: Surrogate factoring, periodic behavior
    ... The results are compared to Fermat's method, trial factorisation (both ... To support a position that surrogate factoring is worse than any other ... Surrogate factoring was not designed as a PRNG, ... if it takes no steps to avoid repeating failed trial factors. ...
    (sci.math)