Biquadratic reciprocity and a Lucasian primality test期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Biquadratic reciprocity and a Lucasian primality test

Authors:	Pedro Berrizbeitia T G Berry

Institution:	Departamento de Matemáticas Puras y Aplicadas, Universidad Simón Bolívar, Caracas, Venezuela ; Departamento de Matemáticas Puras y Aplicadas, Universidad Simón Bolívar, Caracas, Venezuela

Abstract:	Let $\{s_k,k\geq 0\}$ be the sequence defined from a given initial value, the seed, , by the recurrence $s_{k+1}=s_k^2-2,k\geq 0$ . Then, for a suitable seed , the number $M_{h,n}=h\cdot2^n-1$ (where is odd) is prime iff $s_{n-2} \equiv 0 \bmod M_{h,n}$ . In general depends both on and on . We describe a slight modification of this test which determines primality of numbers $h\cdot2^n\pm 1$ with a seed which depends only on , provided $h \not \equiv 0 \bmod 5$ . In particular, when , odd, we have a test with a single seed depending only on , in contrast with the unmodified test, which, as proved by W. Bosma in Explicit primality criteria for $h\cdot 2^k\pm 1$ , Math. Comp. 61 (1993), 97-109, needs infinitely many seeds. The proof of validity uses biquadratic reciprocity.

Keywords:

	点击此处可从《Mathematics of Computation》浏览原始摘要信息
	点击此处可从《Mathematics of Computation》下载免费的PDF全文