🚀 go-pugleaf

gilgalad@quip.eecs.umich.edu (Ralph Seguin) writes:
: A friend of mine posessing a masters in mathematics said that he had heard
: and saw a flyer in his local math dept that RSA had been cracked.  I told

Could this flyer be obtained?

: him that I thought that this was a load of bunk.  We got into a heated
: discussion and he claimed that methods of factoring large composites had
: been developed that were several orders of magnitude faster than older
: methods.  I told him that this was irrelevant, since you  could generated
: arbitrarily large composites to form your key.  Even going 12 orders of
: magnitude faster (1 trillion times faster), it could still take easily
: several billion years to factor some of the smaller sized keys.  The
: question that I have is: am I completely wrong here (ie, have I stuck
: my foot and a good portion of my leg in my mouth ;) ?  Personally, I feel

If in fact there was a fundamental breakthrough in factoring it could make
the size of the composite irrelevant but I am sure we would know about
that.

: that the NSA posted that flyer to get people to refrain from using something
: they are unable to crack ;>

Not even the NSA is that stupid (I hope :-)

: 
: My second question is:  what is the best means available for generating
: truly huge primes (200+ digits)?  Fermat and Mercene (sp?) numbers
: are NOT secure.

Generating big random numbers and then testing them probabilistically for
primality.  Sounds crude but it works.  The density of primes up in the 
range desired is higher than intuition would lead one to believe.  I think
that 100 attempts is larger than what is encountered on the average (and
I'll be corrected if not :-)  The probibalistic test can be iterated
for an arbitrarilarily high theoretical probability that one is prime.
Well, I know that one is prime, you understand what I mean. :-)

I am less sure of this but I think that if the probabilistic test for
primality actually yields a composite then the product of this with a
real prime is about as hard to factor as a two prime composite.  The
probability of getting two such composites is exceedingly small.

Bob
-- 
Bob Cain    rcain@netcom.com   408-358-2007

    'The meek shall inherit the earth--the rest of us will move on..'
                                                    Sameer Parekh


               PGP 1.0 or 2.0 public key available on request.