Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] Little result about primes (Tao)

Expand Messages
  • Jens Kruse Andersen
    ... 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
    • 0 Attachment
      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.