Posted on by John Reid

Primes and Codes

(Image source: https://www.quantamagazine.org/mathematicians-will-never-stop-proving-the-prime-number-theorem-20200722/)

A prime number is a positive integer which is only divisible by itself and one, e.g. : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,  etc. These have long fascinated mathematicians and are the subject of a branch of mathematics called Number Theory.

As a young aspiring physicist I was  skeptical about their relevance, their “reality”. After all, I thought, they don’t occur in nature. These days I am not so sure so I asked ChatGPT:

Yes, prime numbers do occur in nature! While they might not be as visually obvious as, say, the Fibonacci sequence, they appear in various biological and physical systems. Here are some interesting examples:

1. Cicada Life Cycles

Certain species of cicadas, such as Magicicada, emerge from the ground in cycles of 13 or 17 years, both of which are prime numbers. Scientists believe this helps them avoid predators with shorter, more predictable life cycles.

2. Crystal Structures and Quasicrystals

Quasicrystals, a unique type of solid with non-repeating patterns, often exhibit symmetries related to prime numbers. For example, the diffraction patterns of quasicrystals sometimes include sequences based on prime distributions.

3. Signal Processing in Animal Communication

Some animals, like birds and crickets, space their calls or chirps in intervals that align with prime numbers. This may help reduce overlapping signals and make communication more efficient.

4. Prime Number Spirals in Plants?

While Fibonacci numbers are more famous in plant growth (e.g., sunflower spirals), some research suggests prime-numbered arrangements in certain plants’ seed dispersal strategies, minimizing competition.

5. The Physics of Prime Numbers

Some studies in quantum mechanics and chaos theory have found connections between prime numbers and energy levels in certain physical systems, such as the distribution of energy levels in heavy atomic nuclei.

So, while prime numbers may not be immediately visible like other mathematical patterns in nature, they do play a role in biological and physical processes!

Is there an algorithm for factoring any integer?

Yes, there are multiple algorithms for factoring any integer, but the efficiency of these algorithms varies depending on the size of the number. Factoring small numbers is easy, but factoring very large numbers (especially those used in cryptography) is extremely difficult.

Common Factoring Algorithms

  1. Trial Division (Simple but slow)

    • Divide the number by 2, then by 3, then by 5, etc., up to its square root.

    • Example: To factor 100, test divisibility by 2 (yes, 100 ÷ 2 = 50), then again (50 ÷ 2 = 25), then 5 (25 ÷ 5 = 5), and another 5 (5 ÷ 5 = 1).

    • Best for small numbers (e.g., under 10⁶).

  2. Pollard’s Rho Algorithm (Faster for mid-sized numbers)

    • Uses a pseudorandom function to find nontrivial factors.

    • Works well for numbers with small factors.

  3. Fermat’s Factorization Method (Works well for numbers close to a square)

    • Based on expressing a number as the difference of two squares:

    • Efficient for numbers with factors close together.

  4. Quadratic Sieve (QS) (Fast for numbers up to ~100 digits)

    • Uses advanced number theory to find factors efficiently.

    • One of the fastest methods for numbers under 10¹⁰⁰.

  5. General Number Field Sieve (GNFS) (Best for very large numbers)

    • The most efficient algorithm for factoring extremely large numbers (~200+ digits).

    • Used in breaking RSA encryption (which relies on the difficulty of factoring).

Factoring Large Numbers and Cryptography

  • RSA encryption relies on the fact that factoring a product of two large primes is computationally hard.

  • No known efficient (polynomial-time) algorithm can factor very large numbers (>300 digits) quickly on classical computers.

  • Quantum computers (Shor’s algorithm) could break RSA encryption in the future.

6 Replies to “Primes and Codes”

  1. This is probably proof of something very, very different to how most people think of reality.

  2. Invention is the mother of all complexities. It has been alleged that maths is an invention. That would be mathematically disputed by, ah, mathematicians, I am guessing. To reduce complexity, if need be, one needs to unpick the concatenations in man-made chains of inventions. This may be deemed a sexist assertion, but the few women who have invented complex items and systems have been few, I gather, and are important, but not statistically significant. Women employ a different logic, because they are from Venus.
    Now to prime numbers found in nature. Is this statistically significant, and if it is, can it be just pure chance? If, say, there are a dozen universes, is it not reasonable to find that one of them at least has a smattering of things or beings which are built up with prime numbers?
    Just reading “Feeding the Machine”, by James Muldoon, Mark Graham and Callum Cant. Q: Is Amazon a natural phenomenon? More questions:
    Is the Universe a giant machine made up of quantum-sized time-space-matter blips? How can mathematics help us deal with tyrants? Well, a fascinating article, thanks.

    2. I too have checked this title out Jacob and it looks like something I need to read. I am a fan of and I think a pioneer in AI. The grander scale of AI, not just the current craze of LLM chatbots, which I have little time for. I acknowledge their ingenuity and impressive results. To me though they are only sophisticated search engines with a talented human interface of good grammar. I am no mor fascinated with them than I am with the equally impressive results of other search engines. But i do not think of them as intelligent.

      Not sure of your comment “women employ a different logic.” I think the dearth of female invention has all to do with the domination of men over women for all of time, still not completely fixed. For instance banning them from education. That would stymie invention me thinks.

      1. There are reasons for the male of the species having been, by and large, much more inventive in many ways, Of course there are. I elaborated the point more than I could have, but it is remarkable for several important points. It bears elaboration. In our culture, let’s call it civilisation, as that is much bigger and ,hopefully, more enduring, mathematics is king, not queen. That is, it’s been an almost exclusive male preserve. Women had other important things to attend to. However, since Europe started discovering and dominating the rest of the world, there has been an acceleration in development. Due to the fact that women played a different role in society, they have lagged behind in this development in many ways.
        The rest is familiar to almost all of us; female emancipation, feminism, etc. Some day, I expect mathematics to take a lesser role in society. That means some other specialisation(s) will come to the fore. It stands to reason that after, say, 5 thousand years of male-led and dominated homo-sapient development, the feminine side will come to have increased dominance to balance the equation (whatever one takes the equation to be in a global sense). This ought to be a matter for women to mostly contribute to in an active way, initially, with men taking a supporting role. So far, it looks as if women want to take about 5 thousand years to imitate, or replicate, the long reign of male dominance before giving humanity a chance to become balanced in these energies and capabilities. Imo, as the Left has wasted their time and effort fighting capitalism instead of seeking to improve on or moderate its excesses, women emancipists have used and re-enforced the system they hated to get even, instead of being inventive sociopolitically, alas.
        Mathematics are of the utmost importance in our society, yet if it continues to dominate through science and technology, and political control and wherever else it will gain and maintain unchallenged dominance, it must be clear to any reasonable and right-thinking person that, society will self-destruct. Hence, though maths and the essentials needed to maintain human society may be irreconcilable opposites or co-actors in the survival of humanity, the wheel turns and mathematicians will some day take a step back.

  3. Hi John,

    Numbers fascinate everyone for one of two reasons. One they love them, or two they hate them, as in those who struggled with maths at school. That hatred is a sort of fascination.

    Numbers fascinate me as they do you., but I am not a mathematician. Nevertheless I understand them and play with them from time to time within my ability. For instance we are so attuned to base 10 systems that we rarely realise that that is itself a random choice. Humans have had base 5, base 2, base 12 and base 20 systems at times, which each have differing pros and cons. I used to love the shillings with base 12 and pounds with the base 20. When the daily numbering system is different it becomes difficult to get ones head around, like using base 10 to deal with base 60 (time, circumferences).

    So primes, to get to the point, are fabulous. Many number phenomena for instance have been uncovered by playing around with numbers. scientific method plays with numbers resulting from experiments until a relationship or pattern is found. If the pattern were to be the sequence of prime numbers it would take a significant thought to realise what it was rather than the apparent randomness they represent.

    While I know that factoring large prime numbers is the basis of the hardest codes to decrypt, I am not sure I know exactly how it is used. Do you know John?

Comments are closed.