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: Mensanator on 29 Aug 2008 20:17 On Aug 29, 5:04 pm, Thomas Pornin <por...(a)bolet.org> wrote: > According to Mensanator <mensana...(a)aol.com>: > > > Well, you can add some bits to the probability calculation. > > > Help on built-in function is_prime in module gmpy: > > > is_prime(...) > > is_prime(x,n=25): returns 2 if x is _certainly_ prime, 1 if x is > > _probably_ prime (probability > 1 - 1/2**n), 0 if x is composite. > > If x<0, GMP considers x 'prime' iff -x is prime; gmpy reflects > > this > > GMP design choice. x must be an mpz, or else gets coerced to one. > > Note that there is no such thing as a "probably prime integer". The > integer is prime, or not. What we want to express is that we do not know > with 100% certainty the actual status of that integer. However, 100% > certainty is quite moot. What we need, for the purpose of communicating > through Usenet messages, is a risk of failure no greater than the risk > of a message being modified by a freak transmission error. Consider, for > instance, the probability that a message which shows on your screen as > "this integer is prime" becomes, when sent on the wire, "this integer is > not prime". That probability is small but not zero. Random bit flips and > their consequences are rare but they do occur (I have seen several > myself). What this amounts to is that if is_prime(x, 100) returns a > non-zero result, then the integer is known to be prime with quite enough > certainty and it makes no sense to elaborate more on the subject. > > Or, in other words: if stating that an integer is prime, whereas it has > only been tested up to a certainty of 1-(1/2)^100, is a painfull thing, > then stating _anything_ mathematical in a Usenet message must hurt quite > a bit. And, if not, then surely somebody is getting his priorities > wrong. > > The documentation above, however, seems to imply that the default value > for n is 25, which means that a composite number may have a probability > of up to 1 in about 30 millions to be declared prime. This is a bit high > for my comfort. print gmpy.is_prime(n,100) 1 > > --Thomas Pornin
From: Thomas Pornin on 29 Aug 2008 21:10 According to Jean-Claude Arbaut <jeanclaudearbaut(a)orange.fr>: > It's not a _prime_. Oh yeah ? Prove it. Prove the integer to be composite. When an integer has successfully passed a probabilistic primality test, then it may have a very small probability of not being a prime. However, considering the number as a prime is a quite safe bet. On the other hand, stating positively and strongly as you do that the number is _not_ a prime is very risky. My assertion that the number is prime might be mathematically shaky (but no more preposterous than the very idea of using a computer to write that statement); your assertion that the number is composite is mystical faith exaggerated to the point of madness, and beyond. No, really, if you want to be safe, you should say: "the primality status of that integer is _not_ known". Which is not at all the same as what you just said. Please be precise. > For me, even the slightest risk should not be acceptable from the > mathematical point of vue. And you still use a computer ? You are talking about not accepting any slightest risk about an integer which you know only through a message which has gone through a TCP/IP connection, protected from alteration by the pure power of a couple of 16-bit linear checksums ? Wow ! --Thomas Pornin
From: Unruh on 29 Aug 2008 23:08 Thomas Pornin <pornin(a)bolet.org> writes: >According to Jean-Claude Arbaut <jeanclaudearbaut(a)orange.fr>: >> It's not a _prime_. >Oh yeah ? Prove it. Prove the integer to be composite. >When an integer has successfully passed a probabilistic primality test, >then it may have a very small probability of not being a prime. However, >considering the number as a prime is a quite safe bet. On the other >hand, stating positively and strongly as you do that the number is _not_ >a prime is very risky. My assertion that the number is prime might be >mathematically shaky (but no more preposterous than the very idea of >using a computer to write that statement); your assertion that the >number is composite is mystical faith exaggerated to the point of >madness, and beyond. There are deterministic primality tests.-- ie if it is prime it will say so and if not it will say not. >No, really, if you want to be safe, you should say: "the primality >status of that integer is _not_ known". Which is not at all the same >as what you just said. Please be precise. >> For me, even the slightest risk should not be acceptable from the >> mathematical point of vue. >And you still use a computer ? You are talking about not accepting any >slightest risk about an integer which you know only through a message >which has gone through a TCP/IP connection, protected from alteration >by the pure power of a couple of 16-bit linear checksums ? Wow ! > --Thomas Pornin
From: Kristian Gj�steen on 30 Aug 2008 03:18 Thomas Pornin <pornin(a)bolet.org> wrote: >According to Mensanator <mensanator(a)aol.com>: >> is_prime(...) >> is_prime(x,n=25): returns 2 if x is _certainly_ prime, 1 if x is >> _probably_ prime (probability > 1 - 1/2**n), 0 if x is composite. >> If x<0, GMP considers x 'prime' iff -x is prime; gmpy reflects >> this >> GMP design choice. x must be an mpz, or else gets coerced to one. > >[...] > >The documentation above, however, seems to imply that the default value >for n is 25, which means that a composite number may have a probability >of up to 1 in about 30 millions to be declared prime. This is a bit high >for my comfort. The documentation may be inaccurate, n rounds of Miller-Rabin has an error bound of at most 2^{-2n). This error bound is the one usually proved in number theory texts, but as far as I understand, it is far from exact. What's the real likelihood of n rounds Miller-Rabin making a mistake? I tried five rounds of Miller-Rabin for about a million random 100-bit numbers, and it didn't make a mistake. Then I did the same for one round Miller-Rabin. No mistakes. If the error rate was anywhere near 2^{-2n}, I'd have seen a few mistakes. (Note, this only applies when the prime candidates are chosen at random. If the can be maliciously chosen, the analysis changes.) -- Kristian Gj�steen
From: James Dow Allen on 30 Aug 2008 04:08
On Aug 30, 5:04 am, Thomas Pornin <por...(a)bolet.org> wrote: > > Note that there is no such thing as a "probably prime integer". > The integer is prime, or not. A similar statement could be made about many probability statements (especially if you believe in determinism!) The fact that you *could* run a stringent primality test doesn't affect the notion: one could argue that a hidden poker hand can't "probably" have a pair, since you *could* pay to find out! James Hussein Allen |