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 16:44 On Sat, 30 Aug 2008 20:28:08 +0200, Boon wrote: > Phil Carmody wrote: >> Boon wrote: >> >>> Phil Carmody wrote: >>> >>>> 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'? > Meh. Given that there are infinitely many primes numbers and only one > even prime number, then, if I remember the terminology correctly, we can > say the a random pri�e number is odd "almost surely" (i.e. with > probability 1). > http://en.wikipedia.org/wiki/Almost_everywhere You didn't specify a probability distribution on the primes. There is no such thing as a uniform probability distribution on a countably infinite set, and therefore you must have in mind some nonuniform probability distribution. Which one is it? >> If you want a different question, are primes greater than 2 with >> probability 1? > As a matter of fact, yes :-) > The set of primes not greater than 2 is a null set. > http://en.wikipedia.org/wiki/Null_set Same objection applies. It cannot be the case that each prime has probability zero, since probability is countably additive and the sum over all primes is required to be 1. -- Dave Seaman Third Circuit ignores precedent in Mumia Abu-Jamal ruling. <http://www.indybay.org/newsitems/2008/03/29/18489281.php>
From: Dave Seaman on 30 Aug 2008 16:48 On Sat, 30 Aug 2008 20:31:32 +0200, Boon wrote: > Dave Seaman 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". 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". > Are you referring to the AKS primality test? > http://en.wikipedia.org/wiki/AKS_primality_test Yes. It's a deterministic algorithm. >> You check the results in the same way you would any other scientific >> experiment: you get independent confirmation. > I wouldn't equate scientific experiment and the output of an algorithm. In the context where the implementation and execution of the algorithm were being called into question, I think repeatability and independence of implementation are important. -- Dave Seaman Third Circuit ignores precedent in Mumia Abu-Jamal ruling. <http://www.indybay.org/newsitems/2008/03/29/18489281.php>
From: Phil Carmody on 30 Aug 2008 17:12 David Bernier <david250(a)earth.sol> writes: > Phil Carmody wrote: >> Boon <root(a)localhost> writes: >>> 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". Are primes "odd with probability 1"? > > What about the likelihood of a hardware error in either test? > In the GIMPS project, at least two Lucas-Lehmer tests are done > for every exponent p that is left after divisibility tests > are passed. It happens occasionally that the 2nd test and > the 1st one yield inconsistent results. It appears that many contributors to GIMPS like overclocking, and the reliability of their results is seriously questionable, so double checking is essential. However, as soon as a positive is found in either the first or second run, about 3 extra runs are performed, on at least 2 different architectures, with at least 2 different implementations. It is unfeasable that such independent tests would all return the same incorrect answer. The numbers are not publically announced until at least one of the verification runs has been completed. > So it would seem to me that a hardware error in the course > of a deterministic primality test which (absent error) proves > primality is a possibility. I've heard of certificates > of primality. I'm more interested in the chances of > an undetected hardware error giving a corrupt primality > certificate than arguments about choosing probabilistic > over non-probabilistic tests. In order to create a false positive for a 42 million bit number the error has to get all 42 million bits just right. In order for it to create a false negative from an actual prime, it only has to flip 1 bit. The two are incomparable in likelyhood. 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: Jean-Claude Arbaut on 30 Aug 2008 21:15 Boon wrote: > Meh. Given that there are infinitely many primes numbers and only one > even prime number, then, if I remember the terminology correctly, we can > say the a random pri�e number is odd "almost surely" (i.e. with > probability 1). > > http://en.wikipedia.org/wiki/Almost_everywhere Wow wow wow. Almost everywhere with discrete probabilities... random primes with no distribution given... Looks like there is some lack of basic knowledge here. >> If you want a different question, are primes greater than 2 with >> probability 1? > > As a matter of fact, yes :-) > > The set of primes not greater than 2 is a null set. > > http://en.wikipedia.org/wiki/Null_set
From: Unruh on 31 Aug 2008 12:12
Dave Seaman <dseaman(a)no.such.host> writes: >On Sat, 30 Aug 2008 20:28:08 +0200, Boon wrote: >> Phil Carmody wrote: >>> Boon wrote: >>> >>>> Phil Carmody wrote: >>>> >>>>> 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'? >> Meh. Given that there are infinitely many primes numbers and only one >> even prime number, then, if I remember the terminology correctly, we can >> say the a random pri�e number is odd "almost surely" (i.e. with >> probability 1). >> http://en.wikipedia.org/wiki/Almost_everywhere >You didn't specify a probability distribution on the primes. There is no such >thing as a uniform probability distribution on a countably infinite set, and >therefore you must have in mind some nonuniform probability distribution. >Which one is it? >>> If you want a different question, are primes greater than 2 with >>> probability 1? >> As a matter of fact, yes :-) >> The set of primes not greater than 2 is a null set. >> http://en.wikipedia.org/wiki/Null_set >Same objection applies. It cannot be the case that each prime has probability >zero, since probability is countably additive and the sum over all primes is >required to be 1. Sure it can. The infinite sum of zeros can be whatever you want. If you want formal limits. given a cutoff N, the number of primes is something like N/ln(N), so the probability of any particular prime is ln(N)/N. As N goes to infinity, this goes to zero. Ie the limiting probability is 0. But the limit of th esum is 1. |