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

Question related to Proth's theorem

Expand Messages
  • Kermit Rose
    Proth s Theorem (1878): Let n = h. 2^k + 1 with 2^k h. If there is an integer a such that a^[(n-1)/2] = -1 (mod n), then n is prime. Examining small
    Message 1 of 1 , Jun 1, 2006
    • 0 Attachment
      Proth's Theorem (1878): Let n = h. 2^k + 1 with 2^k > h.

      If there is an integer a such that a^[(n-1)/2] = -1 (mod n), then n is
      prime.


      Examining small integers which satisfy the condition 2^k > h of proth's
      theorem
      n 2^k h
      3 = 2 * 1 + 1
      5 = 2^2 * 1 + 1
      9 = 2^3 * 1 + 1
      13 = 2^2 * 3 + 1
      17 = 2^4 * 1 + 1
      25 = 2^3 * 3 + 1
      33 = 2^5 * 1 + 1
      41 = 2^3 * 5 + 1


      It seems clear that the chance of n satisfying this condition, 2^k > h, of
      Proth drops very
      quickly as n becomes larger.


      How critical is this condition to primeness?


      I understand that this condition is critical to the proof of primeness.

      I am asking, what is the probability that a given n would be prime
      if n = 2^k * h + 1, where h > 2^k and

      for some a, a^[(n-1)/2] = -1 ?

      I expect that the answer could be determined only empirically in terms of
      the size of n.
    Your message has been successfully submitted and would be delivered to recipients shortly.