eppstein@tom.columbia.edu (David Eppstein) (01/10/87)
In <9041@duke.duke.UUCP>, srt@duke.UUCP (Stephen R. Tate) writes: > Namely, breaking the RSA protocol has the same complexity as factoring > a very large number. The fastest computer available today would take > several billion years to factor such a large number, giving the security > of the system. This has not to my knowledge been proven. What is true is that the only known method of breaking RSA involves factoring huge numbers, but that is not to say that there is not some other undiscovered method. There are cryptosystems which have been proven equivalent to factoring, but I don't think RSA is one of them. -- David Eppstein, eppstein@cs.columbia.edu, seismo!columbia!cs!eppstein
simsong@mit-amt.MEDIA.MIT.EDU (Simson L. Garfinkel) (01/11/87)
Another real issue in breaking RSA is that factoring is not a well-understood branch of mathematics. We really don't know the "right" way to factor numbers. Right now, it takes a long time for the fastest computers to factor big numbers.... But what if there is a breakthrough and somebody figures out how to factor in parallel (on a connection machine, for example...) What if the NSA knows how to factor but hasn't told anybody? What if I know how to factor but don't tell you? What if I figure out how to do it tomorrow? It's probably wrong to say that an RSA cypher won't be broken for 100 years, because by then we'll know how to factor a whole lot better. Simson L. Garfinkel MIT Media Lab -- Simson L. Garfinkel is a freelance student at the Massachusetts Institute of Technology.
srt@duke.UUCP (Stephen R. Tate) (01/12/87)
In article <4205@columbia.UUCP>, eppstein@tom.columbia.edu (David Eppstein) writes: > What is true is that the > only known method of breaking RSA involves factoring huge numbers, but > that is not to say that there is not some other undiscovered method. > There are cryptosystems which have been proven equivalent to > factoring, but I don't think RSA is one of them. The point about RSA is that if you can break the code, you can get the factorization of the key (this is easy to do). Therefore, it is obviously equivalent in difficulty to factoring. (i.e., you can set up a "fake" RSA scheme using the number to be factored, break RSA, and then you have the factorization of the number -- so while you don't necessarily have to be able to factor a number to break RSA, the problems have the same difficulty. Make sense?) -- Steve Tate UUCP: ..!{ihnp4,decvax}!duke!srt CSNET: srt@duke ARPA: srt%duke@csnet-relay
stewart@ihlpf.UUCP (01/13/87)
>> What is true is that the >> only known method of breaking RSA involves factoring huge numbers, but >> that is not to say that there is not some other undiscovered method. > The point about RSA is that if you can break the code, you can get > the factorization of the key (this is easy to do). Therefore, it is > obviously equivalent in difficulty to factoring. (i.e., you can set > up a "fake" RSA scheme using the number to be factored, break RSA, and > then you have the factorization of the number -- so while you don't > necessarily have to be able to factor a number to break RSA, the problems > have the same difficulty. Make sense?) It's not this easy. You need the factors of your prime to generate the RSA keys. This prevents you from setting up the "fake" RSA scheme to get the factorization. Even if you could set up a fake RSA scheme, it might still be possible to break it without factoring the composite number. RSA is no *more* difficult than factoring, but it still might be *less* difficult. Bob Stewart ihnp4!ihlpf!stewart
tedrick@ernie.Berkeley.EDU (Tom Tedrick) (01/14/87)
>The point about RSA is that if you can break the code, you can get >the factorization of the key (this is easy to do). False. If you can give me an algorithm that will do this efficiently I will eat my words (but send it to me secretly by email so I can publish it :-)
jim@randvax.UUCP (Jim Gillogly) (01/14/87)
in article <9054@duke.duke.UUCP>, srt@duke.UUCP (Stephen R. Tate) says: > > The point about RSA is that if you can break the code, you can get > the factorization of the key (this is easy to do). Therefore, it is > obviously equivalent in difficulty to factoring. The security of an RSA scheme also depends on how the "secret" primes were selected. The company supplying RSA encryption would certainly offer a way to select primes, since most people won't be able to do it themselves. For example, they might say "type a password that you select totally at random, such as your wife's first name or your favorite rock group" and then replicate that totally random password to get two different 100-digit odd numbers. From there count by twos, testing each number for primality (easy), and stop when you have your two totally secret 100-digit primes. I'd expect any scheme to offer an easy way to select your secret primes, and breaking that is not necessarily equivalent to factoring the public key. -- Jim Gillogly {hplabs, ihnp4}!sdcrdcf!randvax!jim jim@rand-unix.arpa
falk%peregrine@Sun.COM (Ed Falk) (01/15/87)
In article <16847@ucbvax.BERKELEY.EDU> tedrick@ernie.Berkeley.EDU.UUCP (Tom Tedrick) writes: >>The point about RSA is that if you can break the code, you can get >>the factorization of the key (this is easy to do). > >False. > >If you can give me an algorithm that will do this efficiently >I will eat my words (but send it to me secretly by email so I >can publish it :-) The original paper by Rivest, Shamir & Adleman says this: [ remember: there are three numbers: e, d & n. n is the product of two large primes, p & q. e & d are functions of these primes. Encryption and decryption are: C = E(M) = M**e mod n M = D(C) = C**d mod n d is any large integer relatively prime to (p-1)*(q-1). e is the "multiplicative inverse" to d mod (p-1)*(q-1). It is calculated by taking gcd(d,T(n)), where 'T' is the totient function. e & n are public, d is secret.] R, S & A consider three approaches to breaking RSA: 1) Factor n. This is proven to be too difficult. 2) Somehow find d without factoring n. Once you know d, you can calculate e*d-1 which is a multiple of T(n). It has been shown that n can be factored using any multiple of T(n). Thus, if you can find d, you can factor n. Therefore, either d is impractical to compute, or R, S & A have stumbled on an easy way to factor large primes. 3) Somehow compute D(C) without knowing d. R, S & A have no answer to this except to conjecture that it also leads to an efficient factoring algorithm. My reference is about 10 years out of date, so it's possible that conjecture (3) has been proven by now. Also, conjecture (2) doesn't *prove* that RSA is unbreakable; only that if it is, then an easy way to factor large primes has been discovered. Does anybody have more recent references? One final note: a few months ago, someone posted that the fastest known algorithm for factoring large numbers is O(exp(sqrt(ln(n)lnln(n)))), and the current record is factoring a 71 digit number in 9.5 hours on a Cray XMP. -ed falk, sun microsystems terrorist, cryptography, DES, drugs, cipher, secret, decode, NSA, CIA, NRO. (The above is food for the NSA line eater.)
stewart@ihlpf.UUCP (01/16/87)
> R, S & A consider three approaches to breaking RSA: > 2) Somehow find d without factoring n. > Once you know d, you can calculate e*d-1 which is a multiple of > T(n). It has been shown that n can be factored using any > multiple of T(n). > > Thus, if you can find d, you can factor n. Therefore, either > d is impractical to compute, or R, S & A have stumbled on an > easy way to factor large primes. This shows that you could factor a number IF you find d AND are given e. Remember that e is computed from d and the prime factors of n. This does not translate into a general scheme for factoring. Bob Stewart ihnp4!ihlpf!stewart [Ignore this. Just wasting space and net capacity so that postnews will let me post this article. ]
jlg@lanl.UUCP (01/17/87)
In article <4205@columbia.UUCP> eppstein@tom.columbia.edu (David Eppstein) writes: >In <9041@duke.duke.UUCP>, srt@duke.UUCP (Stephen R. Tate) writes: >> Namely, breaking the RSA protocol has the same complexity as factoring >> a very large number. The fastest computer available today would take >> several billion years to factor such a large number, giving the security >> of the system. > >This has not to my knowledge been proven. What is true is that the >only known method of breaking RSA involves factoring huge numbers, but >that is not to say that there is not some other undiscovered method. >There are cryptosystems which have been proven equivalent to >factoring, but I don't think RSA is one of them. >-- The original MIT paper on RSA contained a proof that any transformation which decripts an RSA code will also contain the factors of the modulus (perhaps implicitly).
jlg@lanl.UUCP (01/17/87)
In article <163@iris.randvax.UUCP> jim@iris.UUCP (Jim Gillogly) writes: ... >The security of an RSA scheme also depends on how the "secret" primes were >selected. The company supplying RSA encryption would certainly offer a >way to select primes, since most people won't be able to do it themselves. >For example, they might say "type a password that you select totally at >random, such as your wife's first name or your favorite rock group" and >then replicate that totally random password to get two different 100-digit >odd numbers. From there count by twos, testing each number for primality >(easy), and stop when you have your two totally secret 100-digit primes. Scheme: Step 1 - have customer hit space bar N times (to get an N bit number). The output will be an N bit binary number which consists of the least significant bit of the microsecond clock at each space bar detection. If the leading bit is 0 complement the whole number (we are looking for an N bit number, so the leading bit must be one). Step 2 - go forward from this initial seed number until you find a prime that you find satisfactory (ie. the factors of (p-1) meet certain criteria, etc.). Repeat steps 1 and 2 for second prime. This doesn't seem to provide much foothold for the codebreakers to use. Maybe factoring would be easier than trying to reconstruct the generation sequence used.
gwyn@brl-smoke.ARPA (Doug Gwyn ) (01/17/87)
In article <163@iris.randvax.UUCP> jim@iris.UUCP (Jim Gillogly) writes: >I'd expect any scheme to offer an easy way to select your secret primes, >and breaking that is not necessarily equivalent to factoring the public key. Quite so. And this is but one example of how practical cryptanalysis may differ from the academic subject found in recent textbooks.
simsong@mit-amt.UUCP (01/17/87)
In article <163@iris.randvax.UUCP> jim@iris.UUCP (Jim Gillogly) writes: ... >The security of an RSA scheme also depends on how the "secret" primes were >selected. The company supplying RSA encryption would certainly offer a >way to select primes, since most people won't be able to do it themselves. >For example, they might say "type a password that you select totally at >random, such as your wife's first name or your favorite rock group" and >then replicate that totally random password to get two different 100-digit >odd numbers. From there count by twos, testing each number for primality >(easy), and stop when you have your two totally secret 100-digit primes. 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. Simson L. Garfinkel MIT Media Lab -- Simson L. Garfinkel is a freelance student at the Massachusetts Institute of Technology.
falk@peregrine.UUCP (01/19/87)
In article <615@mit-amt.MEDIA.MIT.EDU> simsong@media-lab.MEDIA.MIT.EDU (Simson L. Garfinkel) writes: >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. > Once again, quoting the original paper: ===================================== VII(B). How to Find Large Prime Numbers ... To find a 100-digit "random" prime number, generate (odd) 100-digit random numbers until a prime number is found. By the prime number theorem[9], about (ln 10**100)/2 == 115 numbers will be tested before a prime is found. To test a large number 'b' for primality we recommend the elegant "probabilistic" algorithm due to Solovay and Strassen[14]. It picks a random number 'a' from a uniform distribution on {1,...,b-1}, and tests whether gcd(a,b) = 1 and J(a,b) == a**((b-1)/2) mod b (6) where J(a,b) is the Jacobi symbol[9]. If b is prime (6) is always true. If b is composite (6) will be false with probability at least 1/2. If (6) holds for 100 randomly chosen values of a, then b is almost certainly prime; there is a (negligible) chance of one in 2**100 that b is composite. Even if a composite were accidentally used in our system, the receiver would probably detect this by noticing that decryption didn't work correctly. ... Note that this algorithm does *not* test a number for primality by trying to factor it. Other efficient procedures for testing a large number for primality are given in [8,11,13]. references: [9] Niven, I., and H.S. Zuckerman. "An Introduction to the Theory of Numbers". (John Wiley & Sons, New York 1972). [14] Solovay, R. and V. Strassen. "A Fast Monte-Carlo Test for Primality", SIAM Journal on Computing (March 1977), 84-85. ===================================== For those who care, the original paper is A Method for Obtaining digital Signatures and Public-Key Cryptosystems by R.L. Rivest, A. Shamir, and L. Adleman MIT Laboratory for Computer Science Technical Memo LCS/TM82 Cambridge, Mass. 02139 April 4, 1977 (Revised December 12, 1977) You should be able to get a copy through MIT Press. The first edition was 400 copies which ran out quickly (they had 4000 requests). The Federal government censored the paper for a while, and MIT had to go to court to be able to print further copies. (My copy is 2nd edition). -ed falk, sun microsystems terrorist, cryptography, DES, drugs, cipher, secret, decode, NSA, CIA, NRO. (The above is food for the NSA line eater.)
bs@linus.UUCP (01/19/87)
> One final note: a few months ago, someone posted that the fastest known > algorithm for factoring large numbers is O(exp(sqrt(ln(n)lnln(n)))), and the > current record is factoring a 71 digit number in 9.5 hours on a Cray XMP. > -ed falk, sun microsystems > terrorist, cryptography, DES, drugs, cipher, secret, decode, NSA, CIA, NRO. That was the record in 1983. The current record is 87 digits on a Ethernet Star Configuration of 10 SUN/3's running in parallel. Each ran for about 395 hours or a total of 3950 SUN/3 CPU hours. Adding 3 digits will approximately double the run time. Bob Silverman
bs@linus.UUCP (01/19/87)
> 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
jim@randvax.UUCP (Jim Gillogly) (01/19/87)
In article <11496@lanl.ARPA> jlg@a.UUCP (Jim Giles) objects to my assertion that the RSA encryption-providing company will make it easy for someone to come up with a randomly-selected key; I suggested that they would start from a user-selected key and go forward until we find a suitable prime. He suggests: > Step 1 - have customer hit space bar N times (to get an N bit number). > The output will be an N bit binary number which consists > of the least significant bit of the microsecond clock at > each space bar detection. If the leading bit is 0 complement > the whole number (we are looking for an N bit number, so > the leading bit must be one). >... > >This doesn't seem to provide much foothold for the codebreakers to >use. Maybe factoring would be easier than trying to reconstruct the >generation sequence used. This works fine for getting your initial secret primes; I don't know if microseconds are good enough, but am willing to buy it. But it has the disadvantage that after getting the primes they must stay on the computer as long as this public key will be used. This leaves them unprotected for a long time: public keys will typically be longer-lived than private ones, since you need to publish them in public places, and this can take time as well. Your suggestion would be similar to building a communication package to transfer your files for you that happens to have your login password sitting there in clear. It doesn't give your password to everybody in the world, but it's exposed to anybody on your system. Another poster says that detemining whether a number is prime is just as hard as factoring it. This is false. See Knuth vol 2, for example; the statistical method he gives has been tightened up to certainty in recent years. -- Jim Gillogly {hplabs, ihnp4}!sdcrdcf!randvax!jim jim@rand-unix.arpa
karl@haddock.UUCP (01/19/87)
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
levitin@potak.dec.com (Sam HLO2-1/G11 225-4135) (01/19/87)
Simson Garfinkel writes >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. Come on, Simson. Have you never heard of probablistic factorization? Or read Michael Rabin's paper _Probablistic Algorithm for Testing Primality_ ? To be more precise, I would say "The only way to *prove* if a 100-digit number is prime with 100% certainty is to factor it (or *prove* no factors exist). We can *show* a number to be prime with very high likelihood (as high as you have the computer resources to test) by applying Rabin's algorithm." [Aside from a former to MIT student to another: Mattuck showed Rabin's algorithm in 18.063, and Shafi covered it in detail in 6.875, which is a good graduate course in cryptography.] Sam Levitin Levitin%SEMI.DEC@decwrl [MIT '85, '86] DEC Hudson-LSI 77 Reed Road, Hudson MA 01749 (617) 568-4135
stewart@ihlpf.UUCP (01/19/87)
> It's not this easy. You need the factors of your prime to generate the ^^^^^^^^^^^^^^^^^^^^^ > RSA keys. This prevents you from setting up the "fake" RSA scheme to > get the factorization. I meant, of course, "the prime factors of your composite". Thanks to those who (politely) pointed out my typo. Bob Stewart ihnp4!ihlpf!stewart
srt@duke.UUCP (Stephen R. Tate) (01/19/87)
In article <615@mit-amt.MEDIA.MIT.EDU>, simsong@mit-amt.MEDIA.MIT.EDU (Simson L. Garfinkel) writes: > > 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. > > Simson L. Garfinkel > MIT Media Lab No, no, no, no, no, no...... Not true at all. There are many ways to test if a number is prime that do not involve factoring. Lenstra's theorem provides a fairly quick test, and Shafi Goldwasser at MIT also came up with a fairly efficient test using elliptic groups. And if you don't mind the possibility of error (which you can make very small), you can use some of the randomized algorithms such as the strong pseudoprime test and the Solovay-Strassen primality test. This is what probably all RSA shemes use for selecting p & q..... -- Steve Tate UUCP: ..!{ihnp4,decvax}!duke!srt CSNET: srt@duke ARPA: srt%duke@csnet-relay
steved@sun.uucp (Steve Dever) (01/19/87)
In article <11617@sun.uucp> falk@sun.UUCP (Ed Falk) writes: > >For those who care, the original paper is > > A Method for Obtaining digital Signatures and Public-Key Cryptosystems > by R.L. Rivest, A. Shamir, and L. Adleman > MIT Laboratory for Computer Science > Technical Memo LCS/TM82 > Cambridge, Mass. 02139 > April 4, 1977 (Revised December 12, 1977) > > >You should be able to get a copy through MIT Press. The first edition was >400 copies which ran out quickly (they had 4000 requests). The Federal >government censored the paper for a while, and MIT had to go to court to >be able to print further copies. (My copy is 2nd edition). > > > -ed falk, sun microsystems This paper was later published in the CACM. There is nothing in the published article which indicates it was censored in any way. The reference is: A Method for Obtaining digital Signatures and Public-Key Cryptosystems by R.L. Rivest, A. Shamir, and L. Adleman Communications of the ACM February 1978 Volume 21, number 2 pp 120-126 -- --------------------------- Steve Dever steved@Sun.COM or Sun Microsystems sun!steved
falk%peregrine@Sun.COM (Ed Falk) (01/19/87)
>>You should be able to get a copy through MIT Press. The first edition was >>400 copies which ran out quickly (they had 4000 requests). The Federal >>government censored the paper for a while, and MIT had to go to court to >>be able to print further copies. (My copy is 2nd edition). >> >> >> -ed falk, sun microsystems > >This paper was later published in the CACM. There is nothing in the >published article which indicates it was censored in any way. >The reference is: > > A Method for Obtaining digital Signatures and Public-Key Cryptosystems > by R.L. Rivest, A. Shamir, and L. Adleman > Communications of the ACM > February 1978 > Volume 21, number 2 > pp 120-126 For a while it was completely suppressed. The NSA or CIA or somebody prevented the second edition from being published because of "national security" -- they didn't want a cryptosystem out in the world that they were incapable of breaking. In my opinion, that's the best endorsement RSA could have. Eventually MIT was able to publish. This is either an example of the freedom of the press winning out over the secret police mentality, or it means the the NSA found a way to break it. -ed falk, sun microsystems terrorist, cryptography, DES, drugs, cipher, secret, decode, NSA, CIA, NRO. (The above is food for the NSA line eater.)
devine@vianet.UUCP (Bob Devine) (01/20/87)
> >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. In article <11617@sun.uucp>, (Ed Falk) quotes from RSA paper: > VII(B). How to Find Large Prime Numbers > > To find a 100-digit "random" prime number, generate (odd) 100-digit > random numbers until a prime number is found. By the prime number > theorem[9], about (ln 10**100)/2 == 115 numbers will be tested before > a prime is found. > To test a large number 'b' for primality we recommend the elegant > "probabilistic" algorithm due to Solovay and Strassen[14]. It picks a > random number 'a' from a uniform distribution on {1,...,b-1}, and tests > whether To give the most problems to a cryptanalyst who is trying to factor the number, one technique can be used to generate what the author calls "strong primes". That is, a 100-digit prime number, n, is selected such that n+1 and n-1 both have large prime factors. This is from a paper (circa 1983?) by John Gordon titled "Strong Primes are Easy to Find". He gives the derivations of how to find strong primes and determines that finding such numbers is 19% slower than finding a garden-variety large prime. A suggestion he lists for speeding up the search for primes (which dominates in the search for strong primes) is to eliminate multiples of the first 54 primes (ie, 2,3,5...,251). This leaves roughly 10% of the randomly generated numbers to test for primality. Bob Devine
tim@ism780c.UUCP (Tim Smith) (01/20/87)
In an article, Simson L. Garfinkel writes: >> odd numbers. From there count by twos, testing each number for primality >> (easy), and stop when you have your two totally secret 100-digit primes. > > 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. You can tell if a number is "probably" prime without a lot of computation. Let P be the number that you want to test. Let N be any positive integer smaller than P. One computes (N|P), and compares it to something that I forget ( but it was something real simple, like -1**something). If P is prime, then they will always be equal. Note that (N|P) is about as difficult as computing g.c.d., i.e., not difficult. If P is not prime, then there will be N for which they are not equal. Furthermore, the N for which they are equal form a subgroup of the integers mod P under multiplication. Thus, for composite P, at most half of the choices for N can lead to equality. Thus, if we need to check to see if P is prime, and want to be, say, 99.9% certain of the result, we pick 10 N at random, and test them. If any fail, we know that P is composite. If they all pass, then there is a 99.9% chance ( 1023/1024 ) that P is prime. If we want to be really confident, pick 10 more N. -- Religion: just say "no" Tim Smith USENET: sdcrdcf!ism780c!tim Compuserve: 72257,3706 Delphi or GEnie: mnementh
patc@tekcrl.UUCP (Pat Caudill) (01/20/87)
In article <11496@lanl.ARPA> jlg@a.UUCP (Jim Giles) writes: >Scheme: > Step 1 - have customer hit space bar N times (to get an N bit number). > The output will be an N bit binary number which consists > of the least significant bit of the microsecond clock at > each space bar detection. If the leading bit is 0 complement > the whole number (we are looking for an N bit number, so > the leading bit must be one). > ----- > >This doesn't seem to provide much foothold for the codebreakers to >use. Maybe factoring would be easier than trying to reconstruct the >generation sequence used. You should also use some sort of semirandom technique to select the numbers of digits in the two primes. If you know that the two primes have the same numbers of digits i shoulrd greatly simplify the attempted factoring process. You can work down (or up which ever is shorter) from the square root of the number looking for a factor. It's not easy but it can take several orders of mgnitude off of the difficulty of the factoring. Pat Caudill patc@tekcrl.TEK.COM
stuart@bms-at.UUCP (01/21/87)
In article <615@mit-amt.MEDIA.MIT.EDU>, simsong@mit-amt.MEDIA.MIT.EDU (Simson L. Garfinkel) writes: > 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. What do they teach in the schools these days? You can't test with certainty, but you can test with any desired level of confidence quite efficiently (i.e. you can't tell whether the algorithm or the hardware failed). -- Stuart D. Gathman <..!seismo!dgis!bms-at!stuart>
levy@ttrdc.UUCP (01/25/87)
In article <9087@duke.duke.UUCP>, srt@duke.UUCP writes: >In article <615@mit-amt.MEDIA.MIT.EDU>, simsong@mit-amt.MEDIA.MIT.EDU (Simson L. Garfinkel) writes: >> 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. >> Simson L. Garfinkel >> MIT Media Lab >No, no, no, no, no, no...... Not true at all. There are many ways to test >if a number is prime that do not involve factoring. Lenstra's theorem provides >a fairly quick test, and Shafi Goldwasser at MIT also came up with a fairly >efficient test using elliptic groups. Wai-wai-wait... an earlier posting in this group showing a method that purported to be based on Lenstra's theorem simply produced a big number which is PROBABLY prime, to a degree of probability asymptotically approaching 100% depending on the number of iterations successfully passed in the test. How is this different from the statement below "And if you don't mind the pos- sibility of error (which you can make very small)..."? >And if you don't mind the possibility of error (which you can make very small), >you can use some of the randomized algorithms such as the strong pseudoprime >test and the Solovay-Strassen primality test. This is what probably all >RSA shemes use for selecting p & q..... >Steve Tate UUCP: ..!{ihnp4,decvax}!duke!srt -- ------------------------------- Disclaimer: The views contained herein are | dan levy | my own and are not at all those of my em- | an engihacker @ | ployer or the administrator of any computer | at&t computer systems division | upon which I may hack. | skokie, illinois | -------------------------------- Path: ..!{akgua,homxb,ihnp4,ltuxa,mvuxa, allegra,ulysses,vax135}!ttrdc!levy
srt@duke.UUCP (01/28/87)
In article <1465@ttrdc.UUCP>, levy@ttrdc.UUCP (Daniel R. Levy) writes: > > Wai-wai-wait... an earlier posting in this group showing a method that > purported to be based on Lenstra's theorem simply produced a big number which > is PROBABLY prime, to a degree of probability asymptotically approaching 100% > depending on the number of iterations successfully passed in the test. How > is this different from the statement below "And if you don't mind the pos- > sibility of error (which you can make very small)..."? > I didn't see the earlier posting you refer to, but any test based on Lenstra's theorem is not ramdom, so any number of iterations above 1 is meaningless (and surely doesn't increase the "accuracy" of the test). The other interesting thing about Lenstra's theorem is that it *guarantee's* the result. i.e., if it says a number is prime, then the number *is* prime -- no possibility of error. If interested I'll post what the theorem says... It's kinda cute, but if you want a good discussion of it, see Cohen and Lenstra's paper. Actually a better presentation is given by Dixon in his survey on primality testing. Don't remember exactly where this came out, but if anybody is interested, send me a letter and I'll look it up. -- Steve Tate UUCP: ..!{ihnp4,decvax}!duke!srt CSNET: srt@duke ARPA: srt%duke@csnet-relay
falk@peregrine.UUCP (01/30/87)
In article <9113@duke.duke.UUCP> srt@duke.UUCP (Stephen R. Tate) writes: >I didn't see the earlier posting you refer to, but any test based on Lenstra's >theorem is not ramdom, so any number of iterations above 1 is meaningless (and >surely doesn't increase the "accuracy" of the test). > >The other interesting thing about Lenstra's theorem is that it *guarantee's* >the result. i.e., if it says a number is prime, then the number *is* prime -- >no possibility of error. The earlier posting was a reference to the paper "A fast Monte-Carlo test for primality" by R. Solovay and V. Strassen, SIAM Journal on Computing (March 1977), 84-85. Basicly, there's a test you can apply that's false 100% of the time for composite numbers and false < 50% of the time for prime numbers. If a number passes the test once, it has a better than 50% chance of being prime. If you apply the test 100 times, and the number passes every time, it has only a 1/2**100 chance of being composite. You can be as sure as you want that a number is prime, but you can never be positive. For practical purposes, this is sufficient for RSA. The advantage is that the algorithm is very fast. See also: "Evaluation and Comparison of Two Efficient Probabilistic Primality Testing Algorithms" by Louis Monier, Theoretical Computer Science 12 (1980), 97-108. -ed falk, sun microsystems sun!falk, falk@sun.com terrorist, cryptography, DES, drugs, cipher, secret, decode, NSA, CIA, NRO.
srt@duke.UUCP (02/03/87)
In article <12417@sun.uucp> falk@sun.UUCP (Ed Falk) writes: >The earlier posting was a reference to the paper "A fast Monte-Carlo test >for primality" by R. Solovay and V. Strassen, SIAM Journal on Computing >(March 1977), 84-85. Basicly, there's a test you can apply that's false >100% of the time for composite numbers and false < 50% of the time for >prime numbers. If a number passes the test once, it has a better than >50% chance of being prime. If you apply the test 100 times, and the number Ah, but this has nothing to do with Lenstra's theorem. This test is called the Solovay Strassen test (clever, huh?). I never understood why people use this test any more. A paper that was written quite a while back (by Rabin, I think) showed that the Strong Pseudoprime Test has the same running time as SS, and gave the correct answer every time that SS did. In fact, not only is the "correct answer set" of Solovay- Strassen a subset of the Strong Pseudoprime Test, but you can prove that the Strong Pseudoprime test has a probability of error of only 1/4, instead of 1/2. Therefore, only half as many tests are needed. (And no non-obvious rules like those for computing Jacobi symbols need to be used). -- Steve Tate UUCP: ..!{ihnp4,decvax}!duke!srt CSNET: srt@duke ARPA: srt%duke@csnet-relay
srt@duke.UUCP (02/03/87)
In article <348@bms-at.UUCP>, stuart@bms-at.UUCP (Stuart D. Gathman) writes: > What do they teach in the schools these days? > > You can't test with certainty, but you can test with any desired > level of confidence quite efficiently (i.e. you can't tell whether the > algorithm or the hardware failed). > -- > Stuart D. Gathman <..!seismo!dgis!bms-at!stuart> AARRGGHH!!! How many times does it have to be said? You *CAN* test a number for primality with certainty. Atkins has implemented Shafi Goldwasser's algorithm and it routinely *PROVES* (yes PROVES) primality of numbers up to 400 digits or so..... -- Steve Tate UUCP: ..!{ihnp4,decvax}!duke!srt CSNET: srt@duke ARPA: srt%duke@csnet-relay