Re: A factoring algorithm

Bryan Olson wrote:
> Bill Hart (hart_wb@yahoo.com) wrote:
> > I have a new factoring algorithm which seems to be very fast with
> > certain kinds of numbers.
> [...]
> > I don't know if they have a caveat that
> > says RSA primes shouldn't be chosen to be of that class, but they
> > certainly should.
>
> Is there a non-negligible chance that a key generated with the
> popular random methods will fall into this class? If not, then
> there's no need to adjust the methods. *Any* small class of keys
> is weak, just because it's small.

Yes, I guess this didn't actually register with me. And there probably
isn't a non-negligible chance with the algorithm I have.

>
> To make this quantitative, we look at how long it takes the special-
> purpose algorithm to break one key, given an arbitrarily large
> supply of conventionally-generated keys to attack. We try the
> algorithm on key after key, until one turns out to be of the special
> form and thus falls.
>
> What is the expected work to break one key this way? If it's less
> than the work to break a key with the best existing methods, then
> the class of weak keys is significant and we need to adjust our key
> generation methods. If not, then we have no reason to make any
> special effort to avoid this class of keys.

You're absolutely right. There is no need to adjust the key generation
method. To be honest I don't know the exact classes of keys that my
algorithm would factor in its various incarnations. Of cryptographic
size, perhaps only the class I mentioned, which is certainly sparse and
thus not worth adjusting for. I'll mention it again if I find
otherwise.

I suppose I should code up an efficient version of some of the various
versions of the algorithm and run a test to see how long before it
finds a random key it can break of cryptographically useful size.
Thanks for mentioning it. It's another thing I hadn't thought of (but
should have).

It's an interesting question though. I mean, without knowing in advance
the form of the numbers an algorithm will factor, how could your test
be used? It might not factor any numbers in a billion processor cycles,
but might factor one in every hundred of them in a trillion cycles. How
do you balance the time spent on each check, with the number of keys
checked? My guess is you can't. Though I suppose you can run the test
on keys of a smaller size to simulate running it on keys of a larger
size.

>
>
> --
> --Bryan

Bill.
Received on Tue Jan 17 16:49:05 2006