Re: JSH: Contradictory behavior, issue of math fraud

On Sep 3, 3:32 pm, rossum <rossu...@xxxxxxxxxxxx> wrote:
On Mon, 03 Sep 2007 16:53:52 -0500, Tim Peters <tim....@xxxxxxxxxxx>
wrote:



[JSH]
But if the idea turns out to be a brilliant one which means
factoring is not a hard problem after all, then how can
mathematicians who not only couldn't figure it out, but who
ignored it when presented with it be considered to be true experts
in the field?

[rossum]
In its current version surrogate factoring is too slow to be
considered "brilliant". Only when you have speeded it up
sufficiently

[JSH]
I asked, what if?

[Mas Plak]
Stick to reality, James, I know it can be hard for you, very hard,
but accept the FACT that surrogate factoring is twice as slow as
random guessing.

TWICE AS SLOW AS RANDOM GUESSING.

[rossum]
Not always.

Be a little careful here, lest Jimmy leap to (yet another :-( ) wrong
conclusion. Because his "methods" always have strange convolutions, "a
probe" in a JSH method is typically a lot slower than "a probe" in the
random-gcd algorithm. For example, random-gcd kicks out candidates just
as fast as random (or pseudo-random) numbers can be generated, while
James usually has you /in addition/ putzing around with systematically
generating all two-integer factorizations of some other number too.

You are correct, James gets the factorisation of S "for free" - I
don't log it against his probe count. If I really did want to make
James' method look bad then I would use it recursively to find all the
factors of S and count all the probes used for that.



But I DO look at that with my own research, checking how many
iterations are done to factor S, as my program works by recursively
calling itself to factor the surrogate, though I do give some parts of
it for free as it will check the primes up to 100 directly.

Also it is worth mentioning that your count of "probes" potentially
distort the success of surrogate factoring in the negative, as let's
say research determines that you can pick k and n such that you are
guaranteed to factor an RSA number with surrogate factoring, and it
takes 100,000 probes or more to figure out which combination of
factors works.

Is that a method with only a 1 in 100,000 chance of success or a 100%
successful method?

For those who wonder more about what I mean, if you have

(x+k)^2 = y^2 + 2k^2 + nT

and have k and n that you know will work, you STILL have to loop
through factorizations of 2k^2 + nT, to find one that will work.

The poster counts that looping as "probes", so if it takes 100,000
checks to find the right combination he'd call that 100,000 probes.

The terrible thing is that the potential for surrogate factoring may
be with very large numbers where that number of probes is significant
and far better than random, but with small numbers and an inability to
pick k and n properly it can vastly inflate that number of checks to
support opinions against surrogate factoring.





Some of the iterations of James' method are better than
random. For example, with k = 30, n = 7, 8, 9 ... and a suggestion by
Tim Peters of using S = 27000 * (2*k^2 + n*T) then the results are:

Fermat average = 8.35 probes.
JSH average = 608.86 probes.
Probe ratio = 1 : 72.883
Trial average = 118.63 probes.
Reverse average = 12.70 probes.
Random average = 745.43 probes.
500 trials, 0 misfactors found.

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

This version is better than random. Tim's reasoning for his
suggestion was that by ensuring a lot of small factors in S, 27000 =
(2 * 3 * 5)^3, each S will generate a lot more factor pairs and so is
more likely to hit a factor of T. The results show that with Tim's
suggestion fewer values of n have to be tried before hitting a factor.

James will never understand this, but "Mas Plak" may: James guesses at
method after method that /essentially/ feed pseudo-random integers into
a gcd calculation. But viewed as pseudo-random generators, they're of
poor quality, so an effective way to improve their "performance" has
always been for me to treat them /as/ nothing more than PRNGs, and make
simple changes that improve the coverage of the pseduo-random candidates
generated. Since the number of integer factors of an integer (the
surrogate S) depends on the /powers/ of the primes in S's prime
factorization, artificially multiplying S by 2^3 * 3^3 * 5^3 first can
greatly boost the number of candidate pairs generated, and without
making S itself any harder to factor.

Taking this further, I tried k = 30 with n = 12, 18, 24, 30, ... and I
got James' method down to about 580 probes.

I was following your idea here - these choices added at least another
2 * 3 to the prime factorisation of S.



Nevertheless, I bet it was still much slower (by clock time) than plain
old random-gcd.

I don't know since I don't time the methods separately. I will look
closer when James' method gets closer to trial factorisation. Until
then, "probes" are enough to tell if James actually has anything worth
pursuing seriously.

rossum

And I explained above how that can be a distortion of results, which
seems to be about a pet theory some posters now have to justify
claiming negatives about surrogate factoring.

But I did a complete mathematical analysis, which gives the decision
equations that tell when surrogate factoring works, so no pet theories
are needed.


James Harris

.

Relevant Pages

  • Re: surrogate factoring
    ... quality "SF time" than anyone other than James ... ... "surrogate factoring" doesn't really mean anything specific. ... since the set of all non-zero rationals constituted the search space ...
    (sci.math)
  • Re: JSH: What is surrogate factoring? Once more.
    ... Sieve as well as James' method. ... factoring, periodic behavior', or your post of September 4 in this ... his surrogate factoring method rarely results ... sub main ...
    (sci.math)
  • Re: JSH: SF Algorithm
    ... around with k and n and factoring of some surrogate. ... Let's compare that with Fermat's method. ... So Fermat's method works after just 6 probes. ... Except the guarantee is that with my surrogate factoring you'll get a ...
    (sci.math)
  • Re: JSH: Contradictory behavior, issue of math fraud
    ... but accept the FACT that surrogate factoring is twice as slow as ... For example, random-gcd kicks out candidates just as fast as random (or pseudo-random) numbers can be generated, while James usually has you /in addition/ putzing around with systematically generating all two-integer factorizations of some other number too. ... Reverse average = 12.70 probes. ...
    (sci.math)
  • Re: JSH: Contradictory behavior, issue of math fraud
    ... [JSH] ... but accept the FACT that surrogate factoring is twice as slow as ... James usually has you /in addition/ putzing around with systematically ... Reverse average = 12.70 probes. ...
    (sci.math)