Hacking Primes
Prime numbers are the cornerstone of current computer security techniques. Faster ways of factoring the products of two large numbers are essential in breaking into encrypted documents. Out of purely academic curiosity I wondered what prime numbers look like. To that end I have included some crude visualization of prime numbers. The resultant patterns, while far from helpful, are mildly interesting. Further, the way the images were generated are also of interest.
Prime numbers are used in encryption algorithms. The product of two large prime numbers is used to create a decryption key. There are three main types of attacks on the encryption algorithm. The first is trying to factor the product. The second is trying to reverse engineer the prime number generator. And the third is to discover a new mathematical principal that reveals a flaw in the algorithm. 1.
Perhaps a visualization of prime numbers, when compared to composite numbers, will reveal something of use towards the first or second type of attack. A prime number is "a number that cannot be evenly divided by any numbers other than itself and the number one. For example, the number seven is prime." 2.
Given that special attribute I assumed that they would be rare, particularly with large numbers. I was wrong.
I set up a program to generate an ordered list of numbers and record when a number was likely a prime numbers. The program then generates a visual output to a Persistence of Vision Raytracer file type. 3. The Java programming language "isProbablePrime "function was used to test if a number was prime. 4. And a certainty value of 100 was used. The range of integers from 1 to 500 were generated and recorded in this way. They were then displayed on a checkered board for perspective. Red spheres are prime numbers. White spheres are composite numbers. Apologies to the color blind. I suspect the red spheres will be appear to be the dark (and less frequent) of the two. Lower numbers are always in the lowest part of the image. Thus the farther "away" the colored sphere in the image, the larger the represented number.
This somewhat fuzzy overhead shot in Figure 1 reveals a surprising (to me at least) frequency of prime numbers. I would have expected much less.
Figure 1 – Overhead View. Top of image is highest number (here about 125).
A closer examination of the generated numbers confirms what is suspected from the overhead view. Apparent "clusters" of prime numbers. Take a look at a zoomed in view of the first few numbers in Figure 2.
Figure 2. Zoom in. Highest numbers occur in top right corner of image. 
A look at the end of the generate sequence or ordered numbers, 450 to 500, in figure 3 reveal the same pattern. An apparent cluster of prime numbers. It seems to be even more pronounced at these higher numbers.
Figure 3. Zoom in. Highest number (500) occurs in the top right corner of image.
This clustering of primes "revealed" in the imagery has at least four major questionable attributes. One is that the clustering may only occur in lower value integers. Perhaps the pattern goes away in larger numbers. However, a generation of much larger (in millions) via a similar program shows a surprising (again, to me) number of primes that seem to cluster. 5.
For example, the prime 16811 is the last prime until 16823 (12 numbers away) which is followed closely by 16829 and 16831 (2 additional primes in less than a 10 number progression).Another issue is whether or not the nature of the pattern is it representable in some computational way? Third and related, does it even exist? Perhaps our brains, hardwired to recognize patterns, are seeing something that isn’t there. This is a distinct possibility.
And fourthly, the entire progression could very well by flawed. The function "isProbablePrime" indicates an uncertainty by it’s very name. I have, hopefully safely, assumed that if most of the primes were represented a pattern would appear.
This visualization of prime numbers was a unique exploration for me. I hope you found some satisfaction in the discussion as well. There may indeed be a predictable pattern in the occurrence of prime numbers in an ordered sequence. And it may or may not be of use in better understanding and further safeguarding encryption techniques. The first order of business is to see if someone has been able to mathematically describe (or disprove) these patterns. After that someone could perhaps explore the implications on encryption algorithms. I leave that to enterprising readers and more capable minds than mine.
ã Patrick Amato, 2002.