Re: Surrogate factoring mysteries resolved

From: Tim Peters (tim.one_at_comcast.net)
Date: 02/17/05 

Date: Thu, 17 Feb 2005 12:04:06 -0500

[JSH]
[...]
>> Now combinations of factors are important, as the proper algorithm
>> cycles through integers w, such that
>>
>> sqrt((w^2 - 2Tj^2)^2 + 4j^2 T^3)
>>
>> is an integer, so it helps to know how many combinations there are.
>>
>> It turns out that the equation telling you how many combinations there
>> are, given the number of prime factors, and to what power they are
>> raised, is a cubic.

[Rick Decker]
> Even under the most generous interpretation of what you mean,
> (cubic in what?) this is simply wrong.

It's not really new, though. For example, in an earlier reply to you he
wrote:

    Now I've actually calculated, while you appear to be trying to
    convince others to ignore my work without even bother to give
    mathematics, and my calculations show that if you form a number by
    multiplying the first one thousand primes together you get about
    150 million combinations by two's.

It was explained at least twice then that the correct answer is greater than
10^300, once with a combinatorial proof, and once urging him to generalize
from small concrete examples (starting with an exhaustive list of the
distinct ways to split the product of the first 4 primes). Of course those
were in replies in his threads, so I suppose that counts as hiding them
<wink/sigh>.

At least saying the function "is a cubic" appears new.

>> So as the number of prime factors increase, the number of combinations
>> increases as a cubic.

> No. Gee whiz, James, look up the formula for the number of factors
> a number can have. Here: if N = (p_1)^{r_1} ... (p_t)^{r_t} is the
> prime factorization of N, then N will have
>
> (r_1 + 1)(r_2 + 1)...(r_t + 1)
>
> divisors. As you increase N's prime factors, in what possible way
> does the number of divisors increase in a cubic fashion?

[...]

If I agree, will that be evidence of a conspiracy? I'll be bold and risk
that: yup.

[...]
>> Posters interpreted failures as proof of randomness, as I don't think
>> many of you actually bother to look over the mathematics really
>> carefully and believe that the factoring problem is a hard one.

> Actually the responses you've gotten don't say that. What they do
> say is that empirical evidence supports the assertion that your
> algorithm might not be any better than trying random trial divisors.

My informal experiments on older versions of the algorithm suggested they
did worse overall than factoring by random-gcd, as measured by the number of
gcds computed per success. That's one half of it. The other half is that
the formulas for Ax or w (depending on the specific algorithm) "look a lot"
like summing three pseudo-random integers; that half is an intuitive (not
rigorous) attempt to account for the results of experiments.

It's true anyway that _some_ posters interpreted failures as proof of
randomness, despite that there is no such proof.

> No one doubts that factoring is hard (as far as we know).

He didn't really mean to say that "I don't think many of you ... believe
that the factoring problem is a hard one". I'll reword his last paragraph
so the intended meaning is clearer:

    Posters interpreted failures as proof of randomness. They did
    so because they didn't bother to study my mathematics, and so
    still cling to the erroneous belief that factoring is hard.

This is scary: it's getting easier <wink>.

[...]

Relevant Pages

  • Re: Surrogate factoring demonstrated
    ... > The algorithm is so simple that it's amazing how often it does work. ... bits from T while multiplying the number of divisors of the cofactor of T ... > anything, but if you try it, you will be amazed at the high factoring ... Why don't you try running surrogate factoring by hand, on paper, using no ...
    (sci.math)
  • Re: Surrogate factoring mysteries resolved
    ... > does the number of divisors increase in a cubic fashion? ... >> carefully and believe that the factoring problem is a hard one. ... > algorithm might not be any better than trying random trial divisors. ... randomness, despite that there is no such proof. ...
    (sci.crypt)
  • Re: Surrogate factoring demonstrated
    ... > The algorithm is so simple that it's amazing how often it does work. ... bits from T while multiplying the number of divisors of the cofactor of T ... > anything, but if you try it, you will be amazed at the high factoring ... Why don't you try running surrogate factoring by hand, on paper, using no ...
    (sci.crypt)
  • Re: Surrogate factoring mysteries resolved
    ... > Now combinations of factors are important, as the proper algorithm ... does the number of divisors increase in a cubic fashion? ... No one doubts that factoring is hard. ...
    (sci.crypt)
  • Re: Surrogate factoring mysteries resolved
    ... > Now combinations of factors are important, as the proper algorithm ... does the number of divisors increase in a cubic fashion? ... No one doubts that factoring is hard. ...
    (sci.math)