Factorization and Primality Testing"About binomial theorems I'm teeming with a lot of news, With many cheerful facts about the square on the hypotenuse. " - William S. Gilbert (The Pirates of Penzance, Act I) The question of divisibility is arguably the oldest problem in mathematics. Ancient peoples observed the cycles of nature: the day, the lunar month, and the year, and assumed that each divided evenly into the next. Civilizations as separate as the Egyptians of ten thousand years ago and the Central American Mayans adopted a month of thirty days and a year of twelve months. Even when the inaccuracy of a 360-day year became apparent, they preferred to retain it and add five intercalary days. The number 360 retains its psychological appeal today because it is divisible by many small integers. The technical term for such a number reflects this appeal. It is called a "smooth" number. At the other extreme are those integers with no smaller divisors other than 1, integers which might be called the indivisibles. The mystic qualities of numbers such as 7 and 13 derive in no small part from the fact that they are indivisibles. The ancient Greeks realized that every integer could be written uniquely as a product of indivisibles larger than 1, what we appropriately call prime numbers. To know the decomposition of an integer into a product of primes is to have a complete description of all of its divisors. |
Contents
| 1 | |
Primes and Perfect Numbers | 17 |
Fermat Euler and Pseudoprimes | 30 |
The RSA Public Key CryptoSystem | 43 |
Other editions - View all
Common terms and phrases
Ai+1 Algorithm 10.5 Bháscara-Brouncker Algorithm Bi+1 CFRAC Chapter Ci+1 complex integers composite number compute congruent continued fraction Corollary cubic integers D. H. Lehmer define Definition digits distinct primes elements Elliptic Curves equal Euclidean Algorithm example Exercise extended integers factor base factorization and primality Fermat given greatest common divisor group modulo inverse Jacobi symbol large prime larger largest prime least Legendre symbol Lemma Lucas sequences Mathematics Mersenne primes odd prime pair perfect numbers perfect square positive integers less positive odd integers primality test prime dividing prime divisor prime factors primes less primitive root modulo problem prove primality Q.E.D. Theorem quadratic form quadratic residue modulo Quadratic Sieve rank relatively prime right-hand side satisfying Show solution of Equation sqrt square root strong pseudoprime test TERMINATE Theorem 1.1 trial division values Write a program