高次互反律和数h2n±1的素性判定

Higher Reciprocity Law and Primality Tests for Numbers h2~n±1

大素数在数据传输的安全性方面越来越重要,此外,现代密码学中许多密码协议的构造都依赖于大素数,例如,RSA公钥密码体制的生成就用到了大素数。主要给出了一类特殊形式整数h2n±1(其中h不被17整除)的素性判定算法,该算法对固定的h只需两个递推序列,并且序列的首项只依赖于h,而与n无关,算法的时间复杂性为确定性拟二次多项式时间。在算法的构造过程中主要利用了高次互反律,即八次和十六次互反律。

Large prime numbers are becoming increasingly important in the security of digital transmission.In modern cryptography,many construction of cryptographic protocols are also based on large prime numbers.For instance,the generation of RSA public-key cryptosystem uses large primes.In this paper,we mainly described primality tests for numbers of the form h2 n±1,where his not divided by 17,by means of two recursive sequences with the first items depending only on h,not on n.Our test is deterministic and also runs in quasi-quadratic time.The techniques which we used are the higher reciprocity laws,especially of orders octic and bioctic.