Home » Subject » Number Theory » Computational N.T.

Counterexamples to the Baillie-PSW primality test

Importance: Medium ✭✭
Author(s):
Subject: Number Theory
» Computational Number Theory
Keywords:
Recomm. for undergrads: yes
Prize: $620
Posted by: maxal
on: August 7th, 2007
Problem  (1)   Find a counterexample to Baillie-PSW primality test or prove that there is no one.
Problem  (2)   Find a composite $ n\equiv 3 $ or $ 7\pmod{10} $ which divides both $ 2^{n-1} - 1 $ (see Fermat pseudoprime) and the Fibonacci number $ F_{n+1} $ (see Lucas pseudoprime), or prove that there is no such $ n $.

Selfridge, Wagstaff, and Pomerance offered $500 + $100 + $20 for $ n $ satisfying Problem 2, and $20 + $100 + $500 for a proof that there is no such $ n $ (R. Guy, 1994).

Bibliography

Carl Pomerance. "Are There Counterexamples to the Baillie-PSW Primality Test?"

Thomas R. Nicely. " The Baillie-PSW primality test."

R. K. Guy. "Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes". §A12 in "Unsolved Problems in Number Theory", 2nd ed. New York: Springer-Verlag, pp. 27-30, 1994.


* indicates original appearance(s) of problem.
add new comment