摘要
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.
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.
基金
supported by the National Natural Science Foundation of China under Grant Nos.11601202,11401312,11701284
the High-Level Talent Scientific Research Foundation of Jinling Institute of Technology under Grant Nos.jit-b-201526,RCYJ201408
the Natural Science Foundation of the Jiangsu Higher Education Institutions under Grant No.17KJB110004
National Key R.and D.Program “Cyberspace Security” Key Special Project under Grant No.2017YFB0802800
