What is the next Prime that is 3 mod 4 from this one?
in [Cryptography]
|
Prev: Adi Shamir's Cube Attacks
Next: Merry Christmas 7
From: Dave Seaman on 30 Aug 2008 09:02 On Sat, 30 Aug 2008 13:18:18 +0200, Boon wrote: > Unruh wrote: >> There are deterministic primality tests -- i.e. if it is prime it >> will say so and if not it will say not. > And you would run one such "deterministic primality test" on a computer, > right ? > Suppose you run the program, which completes after 42 hours, and > displays "the input is a prime number with probability 1". How can you > be sure that there was no bug in the CPU ? How can you be sure that a > high-energy photon did not flip one or two bits in RAM ? > Regards. If the computer returned a probability statement, then the algorithm would hardly be deterministic, would it? Google for "Agrawal Primes is in P". You check the results in the same way you would any other scientific experiment: you get independent confirmation. A different person can implement the algorithm and run it. And the output would not be simply "P is prime" or "P is not Prime", but rather "P is prime and here is a certificate that can be used to verify the result", or "P is not prime and here is a factor". -- Dave Seaman Third Circuit ignores precedent in Mumia Abu-Jamal ruling. <http://www.indybay.org/newsitems/2008/03/29/18489281.php>
From: Boon on 30 Aug 2008 09:57 Phil Carmody wrote: > Boon wrote: > >> Unruh wrote: >> >>> There are deterministic primality tests -- i.e. if it is prime it >>> will say so and if not it will say not. >> >> And you would run one such "deterministic primality test" on a >> computer, right ? >> >> Suppose you run the program, which completes after 42 hours, and >> displays "the input is a prime number with probability 1". > > Stop right there. You're confused. There's a whole world of > difference between "proved prime" and "prime with probability 1". Perhaps I should not have written "with probability 1" in the context of a deterministic test. However, AFAIU, the statement is true: Should the test determine that the input is, indeed, prime, then it is prime with probability 1 (deterministic test), else the input is composite, which could be said prime with probability 0. Or am I stretching definitions too thin ? > Are primes "odd with probability 1"? Given a random prime number greater than 2, I'd say it is odd with probability 1, yes. Would that be wrong? Regards.
From: Phil Carmody on 30 Aug 2008 10:18 Dave Seaman <dseaman(a)no.such.host> writes: > On Sat, 30 Aug 2008 13:18:18 +0200, Boon wrote: >> Unruh wrote: > >>> There are deterministic primality tests -- i.e. if it is prime it >>> will say so and if not it will say not. > >> And you would run one such "deterministic primality test" on a computer, >> right ? > >> Suppose you run the program, which completes after 42 hours, and >> displays "the input is a prime number with probability 1". How can you >> be sure that there was no bug in the CPU ? How can you be sure that a >> high-energy photon did not flip one or two bits in RAM ? > > If the computer returned a probability statement, then the algorithm > would hardly be deterministic, would it? > > Google for "Agrawal Primes is in P". Note that a deterministic result is different from a result in deterministic time. AKS is both, but that's not needed if all you want is a strict binary predicate (yes or no, no maybe). > You check the results in the same way you would any other scientific > experiment: you get independent confirmation. A different person can > implement the algorithm and run it. And the output would not be simply > "P is prime" or "P is not Prime", but rather "P is prime and here is a > certificate that can be used to verify the result", or "P is not prime > and here is a factor". Not all proofs have (useful) certificates. APR-CL doesn't, for example. In order to verify an APR-CL proof, you have to run it again. The Pocklingtom/Lehmer family have a minor speedup, as you no longer have to hunt for witnesses, and so you typically see a small constant factor speedup for verification. ECPP, however, is the canonical case of a real-world useful certificate for primality. Years of proving work (mostly blindly hunting), can be verified independently in a matter of no more than hours. Phil -- The fact that a believer is happier than a sceptic is no more to the point than the fact that a drunken man is happier than a sober one. The happiness of credulity is a cheap and dangerous quality. -- George Bernard Shaw (1856-1950), Preface to Androcles and the Lion
From: Phil Carmody on 30 Aug 2008 10:20 Boon <root(a)localhost> writes: > Phil Carmody wrote: > >> Boon wrote: >> >>> Unruh wrote: >>> >>>> There are deterministic primality tests -- i.e. if it is prime it >>>> will say so and if not it will say not. >>> >>> And you would run one such "deterministic primality test" on a >>> computer, right ? >>> >>> Suppose you run the program, which completes after 42 hours, and >>> displays "the input is a prime number with probability 1". >> >> Stop right there. You're confused. There's a whole world of >> difference between "proved prime" and "prime with probability 1". > > Perhaps I should not have written "with probability 1" in the context > of a deterministic test. Absolutely. Never bring probability into anything when you want to deal with absolutes. > However, AFAIU, the statement is true: > > Should the test determine that the input is, indeed, prime, then it is > prime with probability 1 (deterministic test), else the input is > composite, which could be said prime with probability 0. > > Or am I stretching definitions too thin ? You're introducing probability where you don't need to, and in doing so weakening the statement so that it's no longer an absolute. >> Are primes "odd with probability 1"? > > Given a random prime number greater than 2, I'd say it is odd with > probability 1, yes. Would that be wrong? Don't change the question - who said anything about 'greater than 2'? If you want a different question, are primes greater than 2 with probability 1? Phil -- The fact that a believer is happier than a sceptic is no more to the point than the fact that a drunken man is happier than a sober one. The happiness of credulity is a cheap and dangerous quality. -- George Bernard Shaw (1856-1950), Preface to Androcles and the Lion
From: Unruh on 30 Aug 2008 13:00
Dave Seaman <dseaman(a)no.such.host> writes: >On Sat, 30 Aug 2008 13:18:18 +0200, Boon wrote: >> Unruh wrote: >>> There are deterministic primality tests -- i.e. if it is prime it >>> will say so and if not it will say not. >> And you would run one such "deterministic primality test" on a computer, >> right ? >> Suppose you run the program, which completes after 42 hours, and >> displays "the input is a prime number with probability 1". How can you >> be sure that there was no bug in the CPU ? How can you be sure that a >> high-energy photon did not flip one or two bits in RAM ? >> Regards. >If the computer returned a probability statement, then the algorithm >would hardly be deterministic, would it? >Google for "Agrawal Primes is in P". >You check the results in the same way you would any other scientific >experiment: you get independent confirmation. A different person can >implement the algorithm and run it. And the output would not be simply >"P is prime" or "P is not Prime", but rather "P is prime and here is a >certificate that can be used to verify the result", or "P is not prime >and here is a factor". No, the primality proofs do NOT give the factors if it is not prime. Otherwise factoring would be easy. They just say-- it is not prime. >-- >Dave Seaman >Third Circuit ignores precedent in Mumia Abu-Jamal ruling. ><http://www.indybay.org/newsitems/2008/03/29/18489281.php> |