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