Prime Numbers and Prime Number Generation

tags: math, cryptography

Important properties of prime numbers

1. Prime numbers are odd, there is no even prime number except 2, we can conclude from what we said that $p-1=2^{k}q$, I can prove it from my discrete math course.
2. Second property is that id $(amodp{)}^2=1$ then either $amodp=1$ or $p-1$ there is no other answer We can use these properties to apply Miller-Rabin’s test

Instead of generating a prime number randomly and if it didn’t work randomly generate again, just generate a random odd number and test it if it didn’t work add twos $0.5ln(n)$ times where n is the number according to the distribution of primes theorem.

Distribution of primes

The distance between two prime numbers is approximately $ln(n)$ and since we are only adding twos (because it can never be an odd) we can find the next prime number in the worst case after $0.5ln(n)$ iterations.

We want to generate $p$ and $q$ and multiply them to get $n$, our public key.

Miller Rabin’s test

By using this algorithm, we can be 75% sure that the number is prime, we only check if the first one is 1 because if the first one was not one, then according to second property above it is impossible that after squaring this number it can give 1 it can only give -1 mod p. The for loop checks if it gives -1 mod p and if that happens any squaring again will definitely give 1.

Questions to think about

The first one is that there is no need to try up to k, because if anything before gives 1 or -1 mod p then $a^{2^{k}q}$ will definitely give 1. We also can’t check j = k directly due to Carmichael numbers, look the last 4 answers here.

The miller-rabin is more used to make sure if a number is not prime when it fails the test, instead of confirming if a number is prime when it passes the test.

References

1. https://chatgpt.com/share/675205b3-9018-800f-a05e-29e67671e4b5 - proof that squaring any number can give p - 1 but never 1