Re: Proof factoring solution is closed form

From: Décio Luiz Gazzoni Filho (decio_at_decpp.removethis.net)
Date: 02/12/05 

Date: Fri, 11 Feb 2005 21:40:56 -0200

Rick Decker wrote:
> <snip>
>
> That's a nice observation. I have to think some more about it
> (it's the end of my work day, it's Friday, so it might actually
> be obvious and I'm just missing it).

Well, actually, it's pretty easy. Think about this. Why is the QS/NFS/etc.
subexponential and not polynomial time? Because the set of admissible (i.e.
smooth) integer has very low density. Dickman's theorem quantifies that: an
integer near x is x^(1/u)-smooth with probability u^-u. When analyzing the
complexity of QS/NFS, one tries to strike a balance between choosing 1/u
too small, so that fewer relations are needed but smooth integers are hard
to come by, and choosing 1/u too big, so that relations come by easily but
you need an ungodly amount of them. It turns out that the optimal
compromise is subexponential in the smoothness bound and other crucial
parameters that determine the algorithm's running time.

Let's look at numbers from an actual factorization, to put this into
perspective. NFSNET factored n = 10^227 - 1 with a degree d = 6 polynomial
using a factor base, including large primes, of 1 billion (I'll simplify
here and assume that we're looking for 1e9-smooth integers.) The integers
generated by the sextic polynomial, according to the NFS analysis, have
size O(n^2/d). We have that log((10^227-1)^(2/6))/log(1e9) = 8.41, and
8.41^-8.41 = 1.68*10^-8, that is, we expect to look at ~60 million
candidates before finding a smooth integer. Of course Dickman's theorem
merely describes the asymptotics, so this may be off by an order of
magnitude or two. Anyway, it's an ungodly amount of integers to look at. On
the other hand, if I were searching for a prime around 10^227 - 1, I'd
expect to find one after log(10^227 - 1) = 522.7 attempts. According to my
heuristic, finding a pair of primes symmetric about 10^227 - 1 requires
sieving through 164 thousand candidates. The two values aren't too far
apart, but recall that in JSH's hypothetic method, I need a single pair of
primes, whereas in the NFS I need at least as many relations as there
primes in the factor base. But most importantly, if one were to compare the
asymptotic behavior, finding 2 primes is much more favorable than finding
smooth integers, even as one varies the degree of the polynomial and
adjusts the size of the factor base.

> However, there seems to be
> a tension here between the ease of factoring M^2 - j^2 and the
> size of the factor sample space.
>
> Your suggestion earlier in this thread, that one pick
> j = 2*3*5...maxp, where maxp is chosen so that j < M is lovely
> insofar as it will likely give a set of factors of T that is
> small. However, if we assume that the resulting "good" candidates
> are more or less the same as trial divisors, so that the chance
> that a candidate factor will also give rise to an x value with
> a factor, p, dividing M will depend solely (or nearly so) on the
> value of p, then it seems as if you want a _larger_ candidate space,
> rather than smaller, so as to eliminate the all-too-common chance that
> x won't have any nontrivial factors in common with M.
>
> [Gad, that was a long sentence. I hope everyone could parse it.]
> I actually broke down and wrote a program myself (well, that's
> part of what I get paid to do, after all) and the empirical
> evidence seems to support my claim. The T values with a smaller
> number of factors are more likely to yield no useful x values than
> those with a larger number of factors. This puts your and Tim's
> suggestions at the opposite ends of the spectrum, as I see it.
> You want to produce a T with few factors, while Tim's (IIRC)
> suggestion to pick j to make M+j or M-j a power of 2 does just
> the opposite: make a T with lots of factors. Tricky (and likely
> pointless) to analyze.

Actually I was just looking for the fastest way to generate a fully
factorizable pair M + j, M - j. Now, it's not my fault that JSH's method
behaves as a random number generator, and thus needs lots of factors to
generate lots of possibilities for g_1 and g_2 to raise the likelihood that
one of these possibilities leads to an actual factorization. If his method
were as good as he claims, then *any* factorizations of M + j and M - j
would lead to a factorization of M, and then the task would be what I set
out to do: find a fully factorizable pair. And in that, I stand by my claim
that the fastest way to do so is to sieve the vicinity of M for primes.

> <snip>
>>
>> And since JSH's method appears to perform worse than trial division, then
>> neither does JSH's method. What's your point? Did you actually believe
>> for a second that his method might indeed factor an RSA challenge?
>>
> Odds are, no. Maybe something useful might come of it, but I'm
> not hopeful.

Come on, you're the one who seems to understand it best, I thought it would
be clear to you that it is completely useless.

Me, I'm just in this because I liked the challenged of finding `relations'
as fast as possible, not because they might lead to a fast factorization
method -- that never even crossed my mind.

> <snip>
>
> It's easy to fantasize what I'd do if I ever came up with a
> fast factorization algorithm based on what has appeared in
> these ngs. There are a range of possible actions, and I'm
> ashamed to admit that very few of them include giving more
> than a mention to JSH. Not that that's likely to happen,
> mind you.

No need to be ashamed, he doesn't write anything coherent anyway. JSH
claiming credit on something that comes out of this is akin to Eolas
claiming they invented browser plugins because of their patent.

Décio

Quantcast