Re: JSH factors 15

On Wed, 04 Feb 2009 13:23:10 -0800, Tim Smith
<reply_in_group@xxxxxxxxxxxxxxxx> wrote:


The following is from JSH's latest blog entry. I'll reproduce it here
rather than link to it, so we don't have to worry about it changing mid
discussion.

JSH has finally worked an example using his factoring method. He has
factored 15.

================== BEGIN TRANSCRIPT FROM JSH BLOG ======================

In a prior post I noted a simple approach to factoring using Pell's
Equation and in this post I'll use that technique for a simple,
demonstration factorization.

[snip]

================== END TRANSCRIPT FROM JSH BLOG ======================

As I have done previously, I tested James' latest Pellian 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.

Fermat average = 7.85 probes.
JSH average = 466.43 probes.
Probe ratio = 1 : 59.388
Trial average = 119.32 probes.
Reverse average = 12.29 probes.
Random average = 749.63 probes.
500 trials, 0 misfactors found.

Average v's tried per factorisation: 234.448
Maximum v reached over all tests = 1211


Average timings over 200 numbers:
16 bits: 70.080 mSec / number. 0 misfactors.
18 bits: 102.014 mSec / number. 0 misfactors.
20 bits: 228.915 mSec / number. 0 misfactors.
22 bits: 385.718 mSec / number. 0 misfactors.
24 bits: 905.187 mSec / number. 0 misfactors.

As seems usual with James' methods it will correctly factor the target
number, but has no speed advantage over existing methods. Judging
from the timing tests, this latest method does not scale well to
larger numbers.

rossum

.

Relevant Pages

  • 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)
  • 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)
Quantcast