## new test for primes

Expand Messages
• A beautifull day, i have elaborated a test for primes. It is sufficent at least for all numbers
Message 1 of 3 , May 26, 2010
A beautifull day,

i have elaborated a test for primes. It is sufficent at least for all numbers < 10^13

An implementation and explication can be found under
http://beablue.selfip.net/devalco/suf_prime.html

Perhaps someone has a good explication or proof for this test.
If someone finds a counterexample, it would be also nice to give me a feedback.

Nice greetings from the primes
Bernhard Helmes

http://devalco.de
• ... Here is rough-and-ready Pari-GP code for Bernhard s test: {bh(n)=local(a=2,t=0);if(n%2&&!issquare(n), while(kronecker(a,n)!=-1,a++);
Message 2 of 3 , May 26, 2010
"bhelmes_1" <bhelmes@...> wrote:

> An implementation and explication can be found under
> http://beablue.selfip.net/devalco/suf_prime.html

Here is rough-and-ready Pari-GP code for Bernhard's test:

{bh(n)=local(a=2,t=0);if(n%2&&!issquare(n),
while(kronecker(a,n)!=-1,a++);
t=Mod(a,n)^((n-1)/2)+1==0;if(t,
t=lift(Mod(Mod(1,n)*(1+x),a-x^2)^n)==1-x));t;}

It detects a lot of odd impostors.

David
• ... Bernhard follows BPSW in combining a Fermat and Lucas test. His strong Fermat test has base a, where BPSW have base 2. His strong Lucas test has parameters
Message 3 of 3 , May 26, 2010

> Here is rough-and-ready Pari-GP code for Bernhard's test:
>
> {bh(n)=local(a=2,t=0);if(n%2&&!issquare(n),
> while(kronecker(a,n)!=-1,a++);
> t=Mod(a,n)^((n-1)/2)+1==0;if(t,
> t=lift(Mod(Mod(1,n)*(1+x),a-x^2)^n)==1-x));t;}

Bernhard follows BPSW in combining a Fermat and Lucas test.
His strong Fermat test has base a, where BPSW have base 2.
His strong Lucas test has parameters (P,Q) = (2,1-a),
where Selfridge suggested (P,Q) = (1,(1-a)/4) with
a the first integer in the sequence
5, -7, 9, -11, 13, -15 ... for which kronecker(a,n) = -1.

I cannot see any reason why Bernhard's test should be
any better or any worse than the BPSW test. Heuristically,
we expect both to have an infinite number of pseudoprimes.
Heuristically, we expect both to require a huge effort
to find a single pseudoprime.

David
Your message has been successfully submitted and would be delivered to recipients shortly.