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 .
Power corrupts . Absolute power corrupts absolutely . Lord Acton