Prev: Adi Shamir's Cube Attacks
Next: Merry Christmas 7
From: Jean-Claude Arbaut on 30 Aug 2008 04:38
Thomas Pornin wrote:
> According to Jean-Claude Arbaut <jeanclaudearbaut(a)orange.fr>:
>> It's not a _prime_.
>
> Oh yeah ? Prove it. Prove the integer to be composite.

Im eant it's not guaranteed to be one. It has not the same value.

> 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.

I don't state it's composite, I state I don't know. You can't call it a
prime then.

From: Jean-Claude Arbaut on 30 Aug 2008 04:39
James Dow Allen wrote:
> 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!

Absolutely. But it's two different things, to know, and to assume.
From: Jean-Claude Arbaut on 30 Aug 2008 05:20
Thomas Pornin wrote:

> 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.

I agree. Primality status not know, which means you can't
call a number a prime in that case.


>> 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 !

That's for such reasons that I wouldn't trust a computer without
validating computations by a different approach. That's what is
done for computations of large numbers of digits of pi, btw.
That doesn't eliminate completely the risk, that's (maybe) why
some mathematicians don't like to use a computer for
mathematical proofs.

>>> 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.

There is no proof that strong witnesses are random. I mean obviously
they are not, they are only deterministic integers, but I have not
seen a proof that these deterministic numbers can be found with a
deterministic pseudo random number generator, in a maner that
permits to call the risk a probability. I'm not sure it's a
probability, or just something that looks like, but should
not be expected to act the same way. Any idea ?
From: Boon on 30 Aug 2008 07:18
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.
From: Phil Carmody on 30 Aug 2008 08:53
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
--
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
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6 7 8 9 10 11
Prev: Adi Shamir's Cube Attacks
Next: Merry Christmas 7