Expand Messages
• ... If the binary input number is 101 then you can prove primality without reading the middle bit, since 101 (decimal 5) and 111 (decimal 7) are both prime.
Message 1 of 7 , Feb 26, 2008
Phil Carmody wrote:
> my comment above about wanting a "test" to be a deterministic
> binary predicate still stands.

If the binary input number is 101 then you can prove primality
without reading the middle bit, since 101 (decimal 5) and
111 (decimal 7) are both prime. You don't know the exact
value of the input number but you can still prove it must be a prime.

Consider base 10. If the input number is 17 then you cannot
say whether it's prime if you only know the digits are x7,
or if you only know they are 1x. But suppose the digits are
binary coded and you are only missing one bit from one of the
digits. If you know the number is either 17 or 37 then you
can prove primality without knowing the precise value of each
digit. But if the number is 294001 or another weakly prime in
http://www.research.att.com/~njas/sequences/A050249 then
you must know the precise value of each digit to prove
primality, because any change to any digit will make it composite.

Tao shows that for all bases, there are infinitely many primes
for which you cannot prove primality without knowing the
precise value of each digit.

--
Jens Kruse Andersen
Your message has been successfully submitted and would be delivered to recipients shortly.