Article View: sci.crypt
Article #3332Re: Security of RSA and factoring
From: karl
Date: Mon, 19 Jan 1987 00:14
Date: Mon, 19 Jan 1987 00:14
15 lines
1436 bytes
1436 bytes
In article <615@mit-amt.MEDIA.MIT.EDU> simsong@media-lab.MEDIA.MIT.EDU (Simson L. Garfinkel) writes: >In article <163@iris.randvax.UUCP> jim@iris.UUCP (Jim Gillogly) writes: >>[To generate your secret primes, start with a random 100-digit odd number.] >>From there count by twos, testing each number for primality (easy), ... > >WAIT! It is not "easy" to test a 100-digit number for priamity. >How do you do that? To tell if a number is prime or not, you factor it. WRONG! It *is* easy to test a number n for primality without factoring it. Why, all you have to do is test whether n divides (n-1)!+1. :-) :-) :-) Seriously, though, I think a better algorithm is to keep selecting a new large random number until you find one that's prime. (I.e. don't "count by twos".) Karl W. Z. Heuer (ima!haddock!karl or karl@haddock.isc.com), The Walking Lint
Technical Details
Message-ID:
<307@haddock.UUCP>Path:
arc1-ca.pugleaf.net!utzoo!watmath!clyde!ima!haddock!karlReferences:
<9041@duke.duke.UUCP> <4205@columbia.UUCP>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!ima!haddock!karl From: karl@haddock.UUCP Newsgroups: sci.crypt Subject: Re: Security of RSA and factoring Message-ID: <307@haddock.UUCP> Date: Sun, 18-Jan-87 19:14:07 EST Article-I.D.: haddock.307 Posted: Sun Jan 18 19:14:07 1987 Date-Received: Mon, 19-Jan-87 02:09:10 EST References: <9041@duke.duke.UUCP> <4205@columbia.UUCP> Reply-To: karl@haddock.ISC.COM.UUCP (Karl Heuer) Organization: Interactive Systems, Boston Lines: 15 Summary: Test primality without factoring