Reference Database (references for the Prime Pages)

Home
Search Site

Largest
Finding
How Many?
Mersenne

Glossary

Prime Curios!
e-mail list

FAQ
Prime Lists
Titans

Submit primes
This is the Prime Pages' interface to our BibTeX database.  Rather than being an exhaustive database, it just lists the references we cite on these pages.  Please let me know of any errors you notice.
References: [ Home | Author index | Key index | Search ]

#### Item(s) in original BibTeX format

```@article{SW2000,
author={A. Stein and H. C. Williams},
title={Explicit primality criteria for \$(p-1) p^n-1\$},
abstract={Deterministic polynomial time primality criteria for \$2^n-1\$ have been known
since the work of Lucas in 1876--1878. Little is known, however, about
the existence of deterministic polynomial time primality tests for numbers
of the more general form \$N_n=(p-1) p^n-1\$, where \$p\$ is any fixed prime.
When \$n>(p-1)/2\$ we show that it is always possible to produce a Lucas-like
deterministic test for the primality of \$N_n\$ which requires that only
\$O(q (p+\log q)+p^3+\log N_n)\$ modular multiplications be performed modulo
\$N_n\$, as long as we can find a prime \$q\$ of the form \$1+k p\$ such that
\$N_n^{k}-1\$ is not divisible by \$q\$. We also show that for all \$p\$ with
\$3<p<10^7\$ such a \$q\$ can be found very readily, and that the most difficult
case in which to find a \$q\$ appears, somewhat surprisingly, to be that
for \$p=3\$. Some explanation is provided as to why this case is so difficult.
},
journal= mc,
volume= 69,
year= 2000,
pages={1721--1734},
mrnumber={2001j:11124}
}

```
 Another prime page by Chris K. Caldwell