Article View: sci.crypt
Article #3334Re: Security of RSA and factoring
From: bs
Date: Sun, 18 Jan 1987 22:17
Date: Sun, 18 Jan 1987 22:17
26 lines
1508 bytes
1508 bytes
> WAIT! It is not "easy" to test a 100-digit number for priamity. (sic) > > How do you do that? To tell if a number is prime or not, you factor it. > > Simson L. Garfinkel > MIT Media Lab > -- > Simson L. Garfinkel is a freelance student at the Massachusetts > Institute of Technology. Nothing could be further from the truth. (1) It is sufficient for practical purposes at P,Q be only probable primes. I recommend that they should also be strong probable primes. That is to say if N is the highest power of 2 dividing P-1 then for some positive integer a: a^(P-1) = 1 mod P but a^(P-1/2^i) != 1 mod P for i = 1,2,... N (2) To PROVE primality of a 100 digit number should only take a few seconds on a large mainframe and a few minutes on a VAX via the Cohen-Lenstra algorithm. Bob Silverman
Technical Details
Message-ID:
<349@linus.UUCP>Path:
arc1-ca.pugleaf.net!utzoo!watmath!clyde!rutgers!ames!ucbcad!ucbvax!decvax!linus!bsReferences:
<9041@duke.duke.UUCP> <4205@columbia.UUCP> <9054@duke.duke.UUCP> <615@mit-amt.MEDIA.MIT.EDU>Show Full Headers
Complete Article Headers
Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: arc1-ca.pugleaf.net!utzoo!watmath!clyde!rutgers!ames!ucbcad!ucbvax!decvax!linus!bs From: bs@linus.UUCP Newsgroups: sci.crypt Subject: Re: Security of RSA and factoring Message-ID: <349@linus.UUCP> Date: Sun, 18-Jan-87 17:17:07 EST Article-I.D.: linus.349 Posted: Sun Jan 18 17:17:07 1987 Date-Received: Mon, 19-Jan-87 06:11:30 EST References: <9041@duke.duke.UUCP> <4205@columbia.UUCP> <9054@duke.duke.UUCP> <615@mit-amt.MEDIA.MIT.EDU> Organization: The MITRE Corp., Bedford, MA Lines: 26 Summary: It is in fact trivial via the Cohen-Lenstra Algorithm In fact, for practical purposes it need only be a probable prime.