Re: Surrogate factoring mysteries resolved
From: Rick Decker (rdecker_at_hamilton.edu)
Date: 02/17/05
- Next message: Larry Hammick: "Re: Surrogate factoring, corrected algorithm"
- Previous message: mensanator_at_aol.compost: "Re: Collatz conjecture"
- In reply to: jstevh_at_msn.com: "Surrogate factoring mysteries resolved"
- Next in thread: Tim Peters: "Re: Surrogate factoring mysteries resolved"
- Reply: Tim Peters: "Re: Surrogate factoring mysteries resolved"
- Messages sorted by: [ date ] [ thread ]
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
- Next message: Larry Hammick: "Re: Surrogate factoring, corrected algorithm"
- Previous message: mensanator_at_aol.compost: "Re: Collatz conjecture"
- In reply to: jstevh_at_msn.com: "Surrogate factoring mysteries resolved"
- Next in thread: Tim Peters: "Re: Surrogate factoring mysteries resolved"
- Reply: Tim Peters: "Re: Surrogate factoring mysteries resolved"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
