## cubic pseudoprimes

Expand Messages
• Hi I have run: http://groups.yahoo.com/group/primeform/files/Probable% 20Primes/cubic_mr.c on a 1GHz Athlon for about ten days; for x = 2 upto 10,000,000,001
Message 1 of 2 , Sep 20, 2002
Hi

I have run:
http://groups.yahoo.com/group/primeform/files/Probable%
20Primes/cubic_mr.c

on a 1GHz Athlon for about ten days; for x = 2 upto 10,000,000,001
and found 527,345,506 probable primes and no "counterexample".

The program tests "f|x^f-x=>5 times Miller-Rabin probable prime where
f=x^3-x-1 and x>1". The probability of a composite f:f|x^f-x getting
through 5 Miller Rabin rounds is less than 4^-5.

Some statistics:-

341 is the smallest base 2 Fermat pseudoprime.

561 is the smallest Carmichael number.

705 is the smallest pseudoprime n for the test "the sum of the nth
powers of the roots of x^2-x-1 is congruent to 1 modulo n".

124 is the smallest x for which the test "f|x^f-x where f=x^2-x-1"
produces a pseudoprime f.

19802 is the smallest x for which the test "f|x^f-x where f=x^2-x-1"
produces a Carmichael number f.

271441 is the smallest Perrin pseudoprime. (The nth term in the
Perrin Sequence is equal to the sum of the nth powers of the roots of
x^3-x-1.)

27664033 is the smallest symmetric pseudoprime relative to the
elementary symmetric functions of the roots of x^3-x-1.

7045248121 is the smallest Perrin pseudoprime that is also a
Carmichael number.

What is the smallest composite f:f|x^f-x where f=x^3-x-1? David
Broadhurst reckons Erdos' Carmichael conjecture implies x ~ 10^13 for
a Carmichael number ;-)

Paul