特殊形式的自然数,例如形式为Mh,n=h.2n±1的数(h奇数,n正整数)常是人们感兴趣的研究对象。Berrizbeitia和Berry提出一个Lucass型素性测定测试,即当h mod 5时测试Mh,n的素性所用的种子仅依赖于h。本文推广了Berrizbeitia和Berry关于...特殊形式的自然数,例如形式为Mh,n=h.2n±1的数(h奇数,n正整数)常是人们感兴趣的研究对象。Berrizbeitia和Berry提出一个Lucass型素性测定测试,即当h mod 5时测试Mh,n的素性所用的种子仅依赖于h。本文推广了Berrizbeitia和Berry关于Mh,n=h.2n±1的素性测定,即将h不能被5整除推广到h不能被形如4m+1的素数q整除时的情形(特别当h能被15整除时)。展开更多
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 i...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.展开更多
文摘特殊形式的自然数,例如形式为Mh,n=h.2n±1的数(h奇数,n正整数)常是人们感兴趣的研究对象。Berrizbeitia和Berry提出一个Lucass型素性测定测试,即当h mod 5时测试Mh,n的素性所用的种子仅依赖于h。本文推广了Berrizbeitia和Berry关于Mh,n=h.2n±1的素性测定,即将h不能被5整除推广到h不能被形如4m+1的素数q整除时的情形(特别当h能被15整除时)。
基金supported by the National Natural Science Foundation of China under Grant Nos.11601202,11401312,11701284the High-Level Talent Scientific Research Foundation of Jinling Institute of Technology under Grant Nos.jit-b-201526,RCYJ201408+1 种基金the Natural Science Foundation of the Jiangsu Higher Education Institutions under Grant No.17KJB110004National Key R.and D.Program “Cyberspace Security” Key Special Project under Grant No.2017YFB0802800
文摘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.
