Re: JSH: Contradictory behavior, issue of math fraud

Tim Peters 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.

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.

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

I downloaded the root certificates of Verisign from:
< https://www.verisign.com/support/roots.html >

It comes as no surprise to me that the signature parameters are SHA1 hash with
a 2048-bit RSA key.

I also watched their "Life of a Threat" video, from
< http://www.verisign.com/Resources/Managed_Security_Services_Tours_&_Demos/security-threat-video.html >

which is pretty good.

David Bernier
.

Relevant Pages

  • 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)
  • Re: JSH: Contradictory behavior, issue of math fraud
    ... but accept the FACT that surrogate factoring is twice as slow as ... James gets the factorisation of S "for free" - I ... Also it is worth mentioning that your count of "probes" potentially ... distort the success of surrogate factoring in the negative, ...
    (sci.math)
  • Re: JSH factors 15
    ... In a prior post I noted a simple approach to factoring using Pell's ... Fermat average = 7.85 probes. ... Average timings over 200 numbers: ... from the timing tests, this latest method does not scale well to ...
    (sci.math)
  • Re: JSH factors 15
    ... In a prior post I noted a simple approach to factoring using Pell's ... Fermat average = 7.85 probes. ... Average timings over 200 numbers: ... from the timing tests, this latest method does not scale well to ...
    (sci.math)
  • Re: Proof factoring solution is closed form
    ... >> Whether your approach to factoring leads to anything remains to ... RSA1024 and all primes up to 1000 would suggest that, individually, each of ... M - j and M + j is 4.1 times more likely to be prime than other candidates ... Then use a sieve to further remove invalid values of k, ...
    (sci.crypt)