A Pythagorean Introduction to Number Theory by Ramin Takloo-Bighash

Author:Ramin Takloo-Bighash
Language: eng
Format: epub, pdf
ISBN: 9783030026042
Publisher: Springer International Publishing

Primality testing

The first primality test is due to Eratosthenes (276–194 BCE) who observed that a number n is prime if and only if it is not divisible by any primes up to ; see Exercise 2.​18. For n reasonably small this provides a quick way of determining the primality of a number n, but as n gets large this method becomes impractical fairly quickly. Ideally one would like to be able to find a way to tell the primality of a number n in a number of steps that grows like a polynomial in the number of digits of n, and Eratosthenes’ algorithm fails this expectation fairly miserably. Such an algorithm was not available until 2004 when the now-famous paper by M. Agrawal, N. Kayal, and N. Saxena [58] came out.

The algorithm presented in this paper is known as the AKS algorithm. Before AKS what was available in literature was an array of probabilistic algorithms, and some of these work quite well. A favorite example is the Miller–Rabin test [53, §6.3] which is based on Fermat’s Little Theorem in elementary number theory. The Miller–Rabin test is extremely quick, but the trouble is that it gives false positives, in that some composite numbers are marked as primes.

A closely related problem we currently do not know how to solve, which is mentioned in the Notes of Chapter 2, is to factorize a large number as a product of its prime factors with reasonable efficiency. The solution of this problem would have far reaching consequences in terms of cryptography and internet security.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.