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}
}