🚀 go-pugleaf

In article <BvGGME.1nD.2@cs.cmu.edu> jmount+@CS.CMU.EDU (John Mount) writes:
:In article <1992Oct1.172252.13437@vela.acs.oakland.edu>, phkahler@vela.acs.oakland.edu (KAHLER PAUL H.) writes:
:|> I agree that the pseudoprime tests are probably adequate for most use.
:|> However, it is VERY BAD to just choose a large random number and check
:|> that it is prime when using RSA. There are algorithms which can factor
:|> numbers containing certain kinds of primes very quickly. If n=p*q and
:|> either p-1 or q-1 contain no large factors, then n can be factored quickly.
:
:I think Bob Silverman has pointed out many times that if p is a prime chosen by
:the above method then p is VERY unlikely to have only small factors- so it
:isn't a bad idea at all.
:
It is actually more that the Elliptic Curve Algorithm has made such criteria
irrelevent. The problem is that for p sufficiently large, it is likely that
there exists a number near p, p+/-k (say) with k < 2sqrt(p)) such that all of
its factors are small. [the exact probability can be quantified with 
Dickman's function. See my forthcoming paper with Sam Wagstaff to appear in
Math. Comp. which outlines this].  

Under such conditions ECM can get lucky and there is NO way to prevent it.

--
Bob Silverman
These are my opinions and not MITRE's.
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"