Re: Surrogate factoring mysteries resolved

From: Rick Decker (rdecker_at_hamilton.edu)
Date: 02/17/05 

Date: Wed, 16 Feb 2005 21:10:50 -0500

jstevh@msn.com wrote:

<snip>
>
> 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.

Even under the most generous interpretation of what you mean,
(cubic in what?) this is simply wrong.
>
> 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?

> The flawed approach that I was focusing on earlier, before I figured
> things out, used
>
> sqrt((Ax - 2j^2)^2 + 4j^2 T)
>
> so if you tried it, you iterated through *fewer* combinations.
>
> Roughly speaking, with n being the combinations of T, and m, being the
> combinations of j^2, you have a ratio of about
>
> (n+m)^3/(3n+m)^3

Oh good grief! There's no justification I can see for this.
Cubing T does NOT increase the number of factors three-fold.

Even worse, assuming (to the contrary) that your expression
above were true, aren't you just slowing your algorithm even more
by increasing the size of the factor space?
>
> which is
>
> (n^3 + 3n^2 m + 3n m^2 + m^3)/(27n^3 + 27 n^2 m + 9 n m^2 + m^3)
>
> and dividing both top and bottom by n^3, you get
>
> (1 + 3m/n + 3m^2/n^2 + m^3/n^3)/(27 + 27 m/n + 9 m^2/n^2 + m^3/n^3)
>
> and if the number of prime factors plus their exponents was less than
> the number of prime factors of T, plus its exponents--rough estimate
> here--then you had about a 1/27 chance of getting a factorization.

No. No. No.
>
<snip>
>
> 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.
No one doubts that factoring is hard (as far as we know).
>
> Now a primary issue for me for a while, as I realized that Ax couldn't
> be an integer was the question of what the prime factors of its
> denominator must be.
>
> As with those prime factors, you can make the method work, so that
> there's not a probability element at all, but certainty.
>
That's a long way from being proven.

<snip>

Regards,

Rick

Relevant Pages

  • 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)
  • 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.math)
  • 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)
Loading