LOGGING IT OUT RAW (4) ❤️

01/10/2025

NB:I will walk through the ideas in simple terms and bring in math notation only when it's unavoidable / adds value

This kind of numbers : From primes to protocols

For me primes are one of the most intresting numbers. Though has a pattern but unpredictable. Mathematians over the years have tried to investigate it's properties and structure . Many cryptographic primitives leverage on it's uniqueness e.g factorization of semiprimes and discrete log over primes

What are primes


Prime numbers are numbers that cannot be divided by any other number except one and it's self
NB: prime numbers are odd, obviously even numbers are seived out of this except 2. All numbers apart from primes are ( or can be ) categorized as composite numbers

My journey to study primes


Firstly : with novelty i sought patterns and characteristics on primes( personal experiments). I was pondering on " large semiprimes are hard to factor"
My main aim was to see gaps in primes and range of primes with a particular gap but big failure! and question followed why don't research about studies on primes?
Secondly : realised how difficult it is and the fact i have reached my limit based on the criteria (standard ) i set for my research mission "Intuition first before fall back on resources ".
In the journey of primes i countered conjecturesssssss and theoremssssss 😊 Before i proceed to the conjectures and theorems, how do we test primes?
Testing primes: primes can be tested using either deterministic or probabilistic algorithms . Probabilistic algorithms are usually used in cryptography applications.
Some primality testing algorithms / techniques :

conjectures here, theorems there

Based on my intuition i try to categorize the conjectures and theorems based on some criteria

Primes are components of other numbers

Canonical decomposition : Every positive integer > 1 can be written as a unique product of prime numbers raised to power
Chen's theorem : states that every sufficiently large even integer can be written as a sum of two prime or semiprime
Goldbach's conjecture : Every integer greater than 2 can be expressed as the sum of two prime numbers
Lemoines conjecture : Every odd number greater than 5 can be expressed as the sum of a prime and twice a prime
n = p + 2q where p and q are prime numbers
Vinogradov's theorem : Every sufficiently large odd number is a sum of three primes

Primes in a form ( structure)

It is established that every prime > 3 has the form \( 6k \pm 1 \)
Fermat's prime : Fermat's prime are primes of the form \( 2^{2n} + 1 \) where n is a positive integer
Mersenne primes : Mersenne prime has the form \( 2^p + 1 \)
Blum prime : Blum prime are prime number such that \( p \equiv 3 \pmod{4} \)

In between

I categorize this ones as "in between " beacuse in my perspective they can be categorized as primes in a form ( structure) and also as in the category of distribution of primes
Twin prime : twin prime conjecture states there are definetely many primes of the form p + 2 where p is also prime
polignac's conjecture : For every even number K there are infinitely many consecutive primes that differ by k ( kinda generalization of twin prime conjecture )
Sophie gemain primes : There are definetely many primes of the form p and 2p + 1 where p is prime
Dirichlet's theorem : For any two positive co-prime integers a and b there are definitely many primes of the form a + nd

Distribution or occurence of primes

Legendres conjecture : There ia always atleast one prime between \( n^2 \) and \( (n + 1)^2 \)
Prime number theorem : The function pi(X ) counts the number of primes less than or equal to X, where we have the approximation
\( \pi(X) \approx \frac{X}{\log X} \)
The prime theorem allows us to estimate of the probabilty of a random choosen number to be prime = \( \frac{1}{\log p} \)
Green Tao theorem : There exist abitarily a long arithemetic progression made up entirely of primes (Green-Tao showed that despite primes having density of zero have abitarily long AP's)
Opperman's conjecture : For every natural number n > 1 there is atleast n^2 and n(n+1) and n(n+1) and ( n+1)^2
Betrande's postulate : For every integer integer greater than 1 there exist atleast on eprime between k and 2k

Prime gaps / gaps between primes

Gaps between is one of the intresting ones for me. Apart from the gap between 2 and 3 which is 1 , other prime gaps are even ( Firstly i would enjoin you to look @ the research paper : GAPS BETWEEN PRIMES BY JAMES MARYNARD. it looks very sweet but pls finish it unlike me 😂)
Andrica's conjecture : If pn be the nth prime number and gn be the gap between two consecutive prime numbers. Andrica's conjecture states \( g_n < 2\sqrt{p_n} + 1 \) or more precisely the original form of the conjecture \( \sqrt{p_n + 1} - \sqrt{p_n} < 1 \)
Cramer's conjecture : Predicts the gap between consecutive primes grows like \( O((\log p_n)^2) \) so for a large prime is pn the next prime is roughly within \( (\log p_n)^2 \) steps
Wolf's conjecture : States the maximum gap between consecutive primes less than n Also note from the prime gap theorem it can be deduce that the gap between primes on an average is In(X) where X is a number.
Now whats the implication of the gap and distribution in cryptography? prime gaps and distribution plays important roles in the feild of cryptography

Computational cost modelling

I would try to dipict this using prime number theory
From Prime number theorem \( \pi(X) \approx \frac{X}{\log X} \) that means density is \( \frac{1}{\log X} \) this means we need an average of log(X) trials before we hit a prime for a number \( \leq X \)
seiving out even numbers we have ( 0.5 (\log X) \) (obviously even numbers cant be prime )
So kinda for prime generation the system latency = \( \text{number of trials} \times \text{number of CPU cycles} \)
cpu cycles = number of clock or processsor cycle or the time it takes to compute a task by a system
So if one can say cycle = frequency
so therefore cpu cycle time = 1/ cpu cycle E.g for cpu with 2.5GHz cycle time = \( \frac{1}{2.5 \times 10^9} = 0.4 \text{ nanoseconds} \)
Take T as the average number of trials , take T = 50000 System latency = \( 0.4 \times 5000 = 2000 \, \text{ns} = 2 \, \mu\text{s} \)
why is this important?

Benchmaarking security assumptions : prime gaps & bias

Let \( g_n = p_{n+1} - p_n \) be the prime gap. Cramér's conjecture states that \( g_n = O((\log p_n)^2) \).
Assume random number generator ( RNG ) picks a number uniformly in [ N, 2N] and prime gaps are small, the chance of hitting prime is
\( P_{\text{hit}} = \sum_{k=N}^{2N} \frac{1}{N} P_{\text{hit}} \approx \frac{1}{\log N} \)
NB: Giving weight 1 to Phit and 0 if it's not prime. So if prime gaps increase abnormally Phit decreases causing longer key generation time and biased output distribution

Modelling failure probabilty : RNG coollision

Suppose RNG only selects from M different bitstrings
P(M) be the probabilty two output yeild the same output, if there are \( \pi(N) \) primes below N and RNG picks uniformly from M possible values \( P_{\text{collision}} = 1 - \exp\left(-\frac{M^2}{2\pi N}\right) \)
This is the prime bound for prime numbers. If M is too small or primes are reused system could be vulnerable to In a nutshell : Prime gaps matters because if large gaps appear in target range prime generation takes longer. E.g In low battery or constrained this slows encryption, delays messages or leaks timing patterns which are exploitable for traffic analysis

My references

A Computational Introduction to number theory and Algebra by Victor Shoup
New Formulas for semi-Primes. testing, counting and identification of the nth and next semi-Primes by Issam Kaddouraa, Samih Abdul-Nabib, Khadija Al-Akhrassa
Gaps between primes by James Maynard
Discrete mathematics with applications by SUSANNA S. EPP
Mathworld
← Back