Primality Testing for Numbers of the Form h · 2n ± 1

HUANG Dandan · KANG Yunling

Journal of Systems Science & Complexity ›› 2019, Vol. 32 ›› Issue (5) : 1473-1478.

PDF(165 KB)
PDF(165 KB)
Journal of Systems Science & Complexity ›› 2019, Vol. 32 ›› Issue (5) : 1473-1478. DOI: 10.1007/s11424-019-7361-7

Primality Testing for Numbers of the Form h · 2n ± 1

  • HUANG Dandan · KANG Yunling
Author information +
History +

Abstract

This paper studies the problem of primality testing for numbers of the form h · 2n ± 1, where h < 2n is odd, and n is a positive integer. The authors describe a Lucasian primality test for these numbers in certain cases, which runs in deterministic quasi-quadratic time. In particular, the authors construct a Lucasian primality test for numbers of the form 3 · 5 · 17 · 2n ± 1, where n is a positive integer, in half of the cases among the congruences of n modulo 12, by means of a Lucasian sequence with a suitable seed not depending on n. The methods of Bosma (1993), Berrizbeitia and Berry (2004), Deng and Huang (2016) can not test the primality of these numbers.

Cite this article

Download Citations
HUANG Dandan · KANG Yunling. Primality Testing for Numbers of the Form h · 2n ± 1. Journal of Systems Science and Complexity, 2019, 32(5): 1473-1478 https://doi.org/10.1007/s11424-019-7361-7
PDF(165 KB)

99

Accesses

0

Citation

Detail

Sections
Recommended

/