高次互反律在特殊数素性判定问题中的应用

In modern cryptography, many construction of cryptographic protocols are based on large prime numbers. For instance, the generation of RSA public-key cryptosystem uses large primes. Large prime numbers are also becoming increasingly important in the security of digital transmission. These show that efficient tests for primality testing problem have theoretical significance and practical value. This project will focus on the study of primality tests for numbers of special forms, which are: (1)to solve the Bosma problem which concerns primality testing by using the higher reciprocity law, and to obtain explicit primality tests, which are in deterministic and quadratic polynomial time, for certain types of numbers, (2)to study the problem of primality testing for generalized Fermat numbers (2p)^{2^n}+1 with prime p greater than 19, and to give an efficient primality test for (2p)^{2^n}+1 depending not on n, (3)to study the problem of primality testing for Cullen numbers and Woodall numbers, and to obtain primality tests for these numbers, which run in deterministic and quadratic polynomial time.

在现代密码学中许多密码协议的构造都依赖于大素数，例如，RSA公钥密码体制的生成就用到了大素数。此外大素数在数据传输的安全性方面也显得越来越重要。这些表明研究素数判定问题的快速算法具有重要的理论意义和应用价值。本项目集中研究了几类特殊形式整数的素性判定问题，主要是：(1)利用高次互反律预期解决更多情形下素数判定的Bosma问题，从而给出某一大类特殊形式数的素性判定的确定性二次多项式时间算法；(2)研究广义费马数(2p)^{2^n}+1在素数p大于19时的素数判定，预期得到关于广义费马数的与n无关的快速判定算法；(3)研究Cullen数以及Woodall数的素数判定问题，项目预期给出关于这两类特殊数素数判定的二次时间的确定性算法。

素数判定问题一直以来都是密码学中的重要研究问题之一，而且近些年来在信息的安全传输和数据安全中也有重要的应用价值。现代密码学中许多密码协议的构造都依赖大素数，例如，RSA公钥密码体制的生成就用到了大素数。这些表明研究素数判定问题的快速算法具有重要的理论意义和应用价值。本项目集中研究了几类特殊形式整数的素性判定问题，主要研究成果为：（1）利用互反律给出某些特殊数的素数判定的二次时间的确定性算法；（2）通过理论和实验研究大素数的生成算法，找到了一些超过512比特的大素数；（3）给出了广义费马数6^{2^n}+1的明确型Lucasian素性序列算法；（4）研究了素数判定问题在环上的推广——素理想判别问题。