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

This paper studies the problem of primality testing for numbers of the form h · 2~n± 1,where h 2~n 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 · 2~n± 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.

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

Journal of Systems Science and Complexity - This paper studies the problem of primality testing for numbers of the form h · 2n ± 1, where h &;lt; 2n is odd, and n is a positive...