It is easy to determine whether a given integer is prime
It is easy to determine whether a given integer is prime
复制标题
很容易判断给定的整数是否是素数
DOI：
10.1090/s0273-0979-04-01037-7
复制
发表时间：
2004
影响因子：
1.3
通讯作者：
A. Granville
中科院分区：
文献类型：
--
作者：
A. Granville
区分质数与合数以及将合数分解为质因数的问题，在算术领域是众所周知的最为重要和有用的问题之一。古代和现代的几何学家们为此付出了大量的精力和智慧，以至于对这个问题进行冗长的讨论是多余的。然而我们必须承认，到目前为止所提出的所有方法，要么局限于非常特殊的情形，要么是如此费力和困难，以至于即使对于不超过杰出人士所编制的数表范围的数，它们也会考验即使是熟练的计算者的耐心。而且这些方法对于更大的数根本不适用……经常出现的情况是，熟练的计算者通过将大数分解为因数会得到足够的回报，从而补偿所花费的时间。此外，科学本身的尊严似乎要求探索每一种可能的方法来解决这样一个优雅且著名的问题……这个问题的性质决定了任何方法都会随着数的增大而变得更加复杂。然而，在下面的方法中，困难增加得相当缓慢……以前已知的技术，即使对于最不知疲倦的计算者来说，也需要难以忍受的劳动。——摘自C. F. 高斯的《算术研究》第329条（1801年）
在纯数学中，很少有比快速确定一个给定的整数是否为质数这个问题更知名或更容易理解的问题了。正如我们上面所读到的，年轻的高斯在他的第一本书《算术研究》中认为这是一个为了我们学科的“尊严”而需要探索的问题。然而，直到现代，当关于素性测试和因数分解的问题成为应用数学的核心部分时，才有一大批研究人员努力解决这些问题。正如我们将会看到的，近期工作中的大多数关键思想都可以追溯到高斯、费马和其他很久以前的数学家，然而也有现代的特色：随着计算机科学的发展以及理解计算的真正难度的需要，高斯模糊的评估“难以忍受的劳动”直到最近才被确定。
2000年数学学科分类。主要11A51，11Y11；次要11A07，11A41，11B50，11N25，11T06。作者部分得到加拿大自然科学与工程研究理事会的资助。因为它们在公钥密码方案所采用的数据加密中的应用；
“The problem of distinguishing prime numbers from composite numbers, and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. It has engaged the industry and wisdom of ancient and modern geometers to such an extent that it would be superfluous to discuss the problem at length. Nevertheless we must confess that all methods that have been proposed thus far are either restricted to very special cases or are so laborious and difficult that even for numbers that do not exceed the limits of tables constructed by estimable men, they try the patience of even the practiced calculator. And these methods do not apply at all to larger numbers ... It frequently happens that the trained calculator will be sufficiently rewarded by reducing large numbers to their factors so that it will compensate for the time spent. Further, the dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated ... It is in the nature of the problem that any method will become more complicated as the numbers get larger. Nevertheless, in the following methods the difficulties increase rather slowly ... The techniques that were previously known would require intolerable labor even for the most indefatigable calculator.” —from article 329 of Disquisitiones Arithmeticae (1801) by C. F. Gauss There are few better known or more easily understood problems in pure mathematics than the question of rapidly determining whether a given integer is prime. As we read above, the young Gauss in his first book Disquisitiones Arithmeticae regarded this as a problem that needs to be explored for “the dignity” of our subject. However it was not until the modern era, when questions about primality testing and factoring became a central part of applied mathematics, that there was a large group of researchers endeavoring to solve these questions. As we shall see, most of the key ideas in recent work can be traced back to Gauss, Fermat and other mathematicians from times long gone by, and yet there is also a modern spin: With the growth of computer science and a need to understand the true difficulty of a computation, Gauss’s vague assessment “intolerable labor” was only recently Received by the editors January 27, 2004, and, in revised form, August 19, 2004. 2000 Mathematics Subject Classification. Primary 11A51, 11Y11; Secondary 11A07, 11A41, 11B50, 11N25, 11T06. L’auteur est partiellement soutenu par une bourse du Conseil de recherches en sciences naturelles et en genie du Canada. Because of their use in the data encryption employed by public key cryptographic schemes;