Prime numbers : a computational perspective / Richard Crandall and Carl Pomerance
Prime numbers : a computational perspective / Richard Crandall and Carl Pomerance
复制标题
素数：计算视角 / Richard Crandall 和 Carl Pomerance
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
R. Crandall
中科院分区：
文献类型：
--
作者：
R. Crandall
数论被称为数学皇后，素数是她美丽的积木，它的出现非常不规则，但“可预测“，正如最著名的数学突破之一所阐述的那样，PNT（素数定理），它给了我们一个大区间上素数总体分布的渐近估计！随着公钥密码学（如RSA）和基于离散日志的密码系统的发明，素数不仅在数学上很有趣，而且在密码学和电子商务的现实世界应用中也很有趣。这本书告诉我们许多关于素数的事实，如何有效地识别一个数是素数，以及如何快速地将一个数分解成素数。它不仅涵盖了理论数论，但计算方面，这是缺乏大多数数论书籍。很难找到一个更好的二人组来写这样一本书：卡尔·波默兰斯和理查德·克兰德尔。Pomerance是二次筛选因子分解算法的发现者，他在MAA的论文写作中获得了许多奖项。克兰德尔（现已去世）是前首席密码学家，苹果的杰出科学家，NeXT的首席科学家，他拥有数学和物理学博士学位！这本书写得好极了（只要看看他们如何解释计算数论中最深层次的数学就足够了，这是最快的因子分解算法，又名数域筛），以及沿着在适当的地方给出有趣的权威评论的方式（例如，见第37页，他们在那里陈述了PNT的等价性和Mertens函数的增长;引用：“这是一个多么令人信服的概念，人们可能会把默滕斯函数想象成一个类似于随机财富的东西，莫比乌斯μ以类似于随机抛硬币的方式对M的求和做出贡献，竟然和大素数定理、大猜想（黎曼猜想）有如此密切的关系！“学术界必须真正感谢他们从科学研究中抽出宝贵的时间来教育我们，写了这部关于数论的巨著。在这本600页的书中有9个章节，其中有许多子章节：这本书以82页的故事开始，其次是数论工具（34页），识别素数和复合（56页），素数证明（52页），指数......
1 What the book is about Number theory is known as the queen of math, and prime numbers are her beautiful building blocks, which occurs highly irregularly and yet " predictably " , as spelt out by one of the most famous math breakthroughs, the PNT (Prime Number Theorem), which gives us an asymptotic estimate to the overall distribution of primes over a large interval! With the invention of public key cryptography like RSA and discrete log based cryptosystems, prime numbers are not just interesting in math but in cryptography and the reaal world applications of e-comerce. This book tells us many facts about prime numbers, how to recognise a number is prime efficiently, and how to factorise a number into primes quickly. It covers not just theoretical number theory but the computational aspects which is lacking in most number theory books. One can hardly find a better duo to write such a book: Carl Pomerance and Richard Crandall. Pomerance was the discoverer of the quadratic sieve factoring algorithm, and he has won many awards on expository writing from MAA. Crandall (now deceased) was former chief cryptographer, Distinguished Scientist of Apple, Chief Scientist at NeXT and he had PhD in both math and physics! The book is painstakingly well written (it is enough just to take a look at how they explain the deepest math in computational number theory, which is the fastest factoring algorithm, aka Number Field Sieve) , and along the way interesting authoritative remarks are given at the appropriate places (see for example, page 37, where they stated the equivalence of PNT and the growth of Mertens Function; quote: " What a compelling notion, that the Mertens Function, which one might envision as something like a random wealk, with the Mobius mu contributing to the summation for M in something like the style of a random coin flip, should be so closely related to the Great Prime Number Theorem, and the Great Conjecture (Riemann Hypothesis) in this way! " The academic community has to really thank them for taking their precious time off their scientific research to educate us by writing this magnificent opus on number theory. There are 9 chapters in this 600 page book with many subchapters: The book starts with a 82 page story on Primes, followed by Number Theoretical tools (34 pp), Recognising primes and composites (56 pp), primality proving (52 pp), Exponential …