Re: A factoring algorithm

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.

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.

-- 
--Bryan