Re: SF: Back to theory

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

Date: Sun, 27 Feb 2005 15:23:34 -0500

[Paul Murray]
>> BWAHAHAHA! ROFL! Is *that* it? Yes, there is "some chance", I suppose.
>> But wouldn't it be just as quick to factor numbers by rolling dice and
>> then checking to see if the number you rolled is a factor?

[Nora Baron]
> Yes - that was my intended point. However to my surprise, some
> experiments by Tim Peters in this thread seem to indicate that
> factoring T^6 = f * g and letting X = f - g and does significantly
> better than chance. The reason is not clear.

It occurs to me that this part of the argument was never spelled out, so
let's get that out of the way.

M=pq, the product of two primes. An earlier post showed that the
probability of picking k uniformly at random from 1..M-1 s.t. 1 < gcd(k, M)
< M is (p+q-2)/(M-1).

Now pick some f. Since gcd(f-g, M) = gcd((f-g) mod M, M) = gcd(f mod M - g
mod M, M), and any specific value for i mod M is as likely as any other,
I'll only consider f and g both in 0..M-1.

1 < gcd(f-g, M) < M iff p divides f-g or q divides f-g but not both. With f
fixed, there are M/p = q ints in 0..M-1 in the same residue class as f mod
M, M/q = p ints in 0..M-1 in the same residue class as f mod q, and 1 int
(g=f) that's in both simultaneously. So are there p+q-2 ways to pick a
"winning" g, so the probability of picking a winning g at random is
(p+q-2)/M.

That's actually a bit less than the probability of picking a winning k
directly from 1..M-1, but would be exactly the same if we picked k at random
from 0..M-1. So, and utterly unsurprisingly, there's nothing about the
*form* of f-g that gives it a better shot at factoring M than picking one
int at random.

The thing to explain then is why experiment shows that the specific <f, g>
picked by splitting (M-j)^6 as the product f*g does dramatically better at
finding f-g winners than picking f and g at random.

> I think X = f^2 - g^2 may do better still.

I'm almost certain that it will, but is a different question. A test run on
products of 20-bit primes after changing things to pick primes in range
"truly" at random won't complete for a few hours. I'll run f^2-g^2 after
that; since it stuffs more primes into the numerator, I expect it will work
better; indeed, an argument like the above says it would work better than
f-g even if we picked f and g at random (shadow of a sketch: for a fixed f
in 0..M-1, there are then two values for g, instead of just one, s.t. p |
f^2-g^2 = (f-g)*(f+g)).

Relevant Pages

  • Re: SF: Back to theory
    ... the product of two primes. ... M, M/q = p ints in 0..M-1 in the same residue class as f mod q, and 1 int ... That's actually a bit less than the probability of picking a winning k ... finding f-g winners than picking f and g at random. ...
    (sci.math)
  • Re: x|m & x|n => x|gcd(m,n) ?
    ... was the general case of a ring, not necessarily the integers, in ... "Primes" may not even make sense (in the algebraic ... but there may be irreducibles that are not ... and there will not be any good way of picking one over any other the ...
    (sci.math)
  • Re: RSA moduli sizes
    ... pubkeybreaker writes: ... primes are chosen by picking a random starting point and ... finding the next smallest prime which satisfies some criteria. ... primes are certainly not uniformly distributed -- indeed, ...
    (sci.crypt)