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

A Really Fast Primality Test

Expand Messages
  • Walter Nissen
    Hi , all , I was looking at this output from GMP-ECM : Found probable prime factor of 1 digits: 3 focusing on the word probable , when this occurred to me .
    Message 1 of 1 , Nov 10, 2006
    • 0 Attachment
      Hi , all ,

      I was looking at this output from GMP-ECM :
      Found probable prime factor of 1 digits: 3
      focusing on the word probable , when this occurred to me .

      If a natural N splits into 2 or more prime factors , at least one of
      them is less than the square root of N .

      If a natural N has no prime factors <= c , and if p | N
      and if p < c^2 , then p is a prime factor of N .

      This leads to a limited , but really fast , primality test :
      If a natural N has no prime factors <= c , and if p | N ,
      then p < c^2 is a fully reliable primality test for p .

      An application :
      If you do trial division thru c , and then ECM , or whatever , pops out
      a divisor , then being < c^2 is a primality test for that divisor .

      As the N of interest becomes larger , the limit of trial division
      discussed by , e.g. , Silverman & Wagstaff , namely ( log N ) ^ 2 , also
      becomes larger and this test becomes more relevant .

      Perhaps these "minor" theorems are of more interest in an era of
      development of automatic proof .

      Has anyone ever bothered to write any of this down ?

      None of this says anything about divisors > c^2 .

      Cheers ,

      Walter

      ---

      Power corrupts . Absolute power corrupts absolutely . Lord Acton
    Your message has been successfully submitted and would be delivered to recipients shortly.