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: Phil Carmody on 30 Aug 2008 13:41 Unruh <unruh-spam(a)physics.ubc.ca> writes: > Dave Seaman <dseaman(a)no.such.host> writes: >>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. Technically you're right. However there's an interesting (to me, at least) twist! If you are doing a formal primality proof, then /presumably/ you have already done a probable primality test on the number, and it passed. So you've got a PRP in your hands. By lucky happenstance, several of the common primality proving algorithms are able to find the factors of PSPs when they 'fail'. This is because they end up finding 2 non-associate square roots (or n-th roots) of 1 or -1, and then a simple difference of squares gives you a factor. Factoring pseudoprimes is on the whole very easy compared with factoring arbitrary numbers. Not always, though, which is what gives several of the large distributed factoring projects (Such as the ones that Bob Silverman's been working with) their raison d'�tre. 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: Boon on 30 Aug 2008 14:28 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 > 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: Boon on 30 Aug 2008 14:31 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 > 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.
From: Phil Carmody on 30 Aug 2008 15:19 Boon <root(a)localhost> writes: > 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 > >> 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 You have the right tools, now reread the thread and learn from it. 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: David Bernier on 30 Aug 2008 16:36
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"? > > Phil 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. 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. David Bernier |