Syncopated Systems
^{™}Seriously Sound Science
^{™} |

Home | About | Library | Contact |

## On Prime NumbersOn August 6, 2002, a trio of authors at the Indian Institute of Technology, Kanpur released for review an impressive paper titled Primes is in P, in which they present a (potential) relatively-fast algorithm for testing a given number for primality, now known as the Agrawal–Kayal–Saxena primality test, often abbreviated as the AKS primality test and also known as the cyclotomic AKS test. (One of my outstanding mathematics professors from Saint Edward's University, Dr. Michael Engquist, brought this paper to my attention hardly more than a week after its publication.) The AKS primality test renewed my interest in prime numbers, and is particularly exciting because it is "the first primality-proving algorithm to be simultaneously I had written a brief essay on prime numbers in 2006, the same year that Agrawal, Kayal, and Saxena received the Gödel Prize and the Fulkerson Prize. In 2019, I had occasion to revisit the topic of prime numbers, especially in the context of computer science. (I should note that I experiment largely for my own edification, and that my studies have been informal at best.) ## What Are Prime Numbers?A prime number is a natural number (ℕ) greater than 1 that cannot be formed by multiplying two smaller natural numbers. (Although the number 1 is excluded from being called a prime number, I find it useful to include it in the set of numbers used for visualizations.) So, for any given prime number p,
## Why Are Prime Numbers Interesting and Important?In computer science, prime numbers have notable applications in areas including cryptography, which is the science of encoding and decoding messages to create relative security in communication. Modern cryptographic practices—such as RSA (Rivest–Shamir–Adleman) encryption—rely upon the selection of relatively unknown (and usually very large) prime numbers. Using these cryptographic methods, those able to identify larger prime numbers should, in theory, be better able to securely encode their own messages and to decode their adversaries' messages. Cryptography also provides a foundation for blockchain-based systems such as Bitcoin that emerged around 2008-2009. Number theorist and my childhood mentor LaFarr Stuart introduced me to the work of another number theorist named Derrick Henry Lehmer (1905-1991), whose interesting work with early electronic computing and prime numbers includes the Lucas-Lehmer test (LLT) for primality and a 1926 bicycle-chain sieve (an electromechanical device designed to select numbers to test for primality), which LaFarr suggested reproducing using modern electronics. ## How Many Prime Numbers Are There?As there are infinitely many numbers, there are infinitely many prime numbers. However, the number of prime numbers in a finite interval is also finite, and the proportion of prime numbers in an interval quickly becomes smaller as the interval becomes larger. As an example, I created (programatically) the following table of prime numbers in the interval [1,1000], of which there are 168 (169 if counting 1). In the table, composite (non-prime) numbers appear in silver with strikethrough and the numbers along the right side keep a running total of the number of prime numbers within the interval through the end of each line.
## Methods For Approximating Numbers of PrimesThe number of primes in any closed interval [1, ## The Prime-Counting FunctionThe prime-counting function is used to approximate the number of prime numbers on a given interval is Π(
After generating a table of several thousand prime numbers with my Apple iMac, I found that this doesn't provide a very good approximation. (My old iMac with only a 600 MHz PowerPC G3 processor running my quick-and-dirty C++ program tests for primality and prints only about 4000 numbers a minute, using Euclid's algorithm to find the greatest common denominator of the number under test.) Running my little program for about 10 minutes, I found that:
## Refining Methods for Approximating the Number of PrimesIn 2006, I had suggested that the prime-counting function Π(
For relatively small intervals, this method's results compare favorably to those obtained via the methods discussed previously, as indicated via the table below.
## My ExperimentsIn my 2006 essay, I described using my Apple iMac (with a PowerPC processor running at 600 MHz) and to process about 4000 numbers per second. In 2019, my calculations on my Panasonic Toughbook CF-30 (with a 2-core Intel Total processor resources available in 2019 are about 5.33 times what I had in 2006. But, as of this writing, I am experimenting only with a single thread that uses only a single processor core, so the improvement in hardware should speed up my experiments by only about 2.67 times. Accounting for differences between RISC and CISC processor architectures, the throughput of the newer processor core might actually be about 8 times faster. So what would make my software run about 20 times faster? The differences in processing speeds between my experiments in 2006 and 2019 are likely best explained by differences in the algorithms I used. ## AlgorithmsIn the field of computer science, we often describe computational time complexity in terms of big O notation, which is more formally known as Bachmann–Landau notation or asymptotic notation. In my 2006 essay, I noted that I had used Euclid's algorithm, which dates back to nearly 300 BCE. In 2019, I initially used a very slow method of brute force computation called trial division (first described in 1202 by Fibonacci in his book Liber Abaci), which has a complexity of O( Afterward, my early experiments with wheel factorization using the relatively small basis { 2, 3, 5 } were computed at about the same speed. Using a larger basis improved speed, but yielded solution sets that were incomplete. One of the things that's really fun and exciting is that I saw all of these gains in performance before even implementing the AKS primality test. ## SummaryAlthough multiplying Π( Interestingly, multiplying Π( I expect to continue occasional experiments with electronics, computers, and prime numbers, and I welcome input via my contact page. |

Syncopated attempts to present a model Web site that meets or exceeds all applicable technical and legal requirements, including those of the A.D.A., COPPA, GDPR, ICANN, and W3C. | Syntax validated |
Style sheet validated |
Highest accessibility |

“Syncopated Systems” and “Syncopated Software” are registered trademarks, the interlaced tuning forks device and the “seriously sound science” and “recreate reality” slogans are trademarks, and all contents (except as otherwise noted) are copyright ©2004-2020 Syncopated Systems. ALL RIGHTS RESERVED. Any reproduction without written permission or other infringement is prohibited by United States and international laws. | |||