Naked Science Forum

General Science => General Science => Topic started by: Pseudoscience-is-malarkey on 19/01/2023 06:56:06

Title: Why are code makers and code breakers obsessed with prime numbers?
Post by: Pseudoscience-is-malarkey on 19/01/2023 06:56:06

This seems to be the case in both fiction and reality.

Title: Re: Why are code makers and code breakers obsessed with prime numbers?
Post by: evan_au on 19/01/2023 09:54:46

Prime numbers have many neat mathematical properties which do not apply to other "composite" numbers.

One of the simplest pseudo-random number generators is x_n+1 = (a*x_n + c) mod m
- It is important that constants a, b and c be relatively prime, otherwise the sequence will repeat long before it has generated all m values.
- Using prime numbers for m has the advantage that all bits of the generated sequence have a long period before they repeat
https://en.wikipedia.org/wiki/Linear_congruential_generator

Another application for prime numbers depends on the fact that for conventional computers, it is hard to factor large numbers
- If the number has just 2 large prime factors
- If the number has smaller factors, it is much easier to factorise (especially if there are many factors)
- In theory, a quantum computer may be able to factor large numbers much more quickly than a classical computer - but it will need a few thousand qubits.
https://en.wikipedia.org/wiki/RSA_(cryptosystem) (https://en.wikipedia.org/wiki/RSA_(cryptosystem))

Another role that prime numbers play here is that raising a number to a high power modulo a prime number generates a unique value.

Note that some of these algorithms use the weaker requirement of being relatively prime, not specifically a prime.

It is hard to prove that a number is prime, but there are practical tests for pseudoprimes, which can determine that a number is prime for all practical purposes.
- These tests are useful for generating public/private key pairs.
https://en.wikipedia.org/wiki/Pseudoprime

Title: Re: Why are code makers and code breakers obsessed with prime numbers?
Post by: alancalverd on 19/01/2023 10:18:35

A very simple code consists of writing plain language into a grid of n x m squares, adding as much irrelevant padding as you wish, then transmitting it "perpendicularly" as m strings x n bytes. It's annoying to intercept because it has an entirely natural frequency table but utterly jumbled, and it's easy to decode if you know that the message is all contained in n x m bytes, which is unequivocal if n and m are prime, but if the string is immersed in padding and significantly longer than m x n it only makes sense if you know one of the primes.