A Really Fast Primality Test Date: 10 Nov 2006 17:45:36 -0000 From: Walter Nissen To: primenumbers@yahoogroups.com Subject: A Really Fast Primality Test 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

2000 Mathematics Subject Classification : Primary 11Y11 ; Secondary 11A41 , 11A51 , 11Y05

Walter Nissen

posted 2008-06-08