Offensive Security Researcher & Quantum Cryptography Analyst

Number Theory Algorithm: Working, Explanation, and Mathematical Foundations

Abdul Wahab Junaid
number theory algorithm and working of this algorithm.

number theory algorithm and working of this algorithm.

I think of number theory as the mathematical bedrock underneath nearly everything else in this series of files — the knapsack cryptosystem, discrete logarithms, prime generation, and factoring all lean on number-theoretic tools I want to isolate and explain properly here: the Euclidean algorithm, modular exponentiation, the Extended Euclidean algorithm, Euler’s theorem and totient function, and the Chinese Remainder Theorem. When I first started learning cryptography, I found that once these five or six core algorithms clicked for me, entire cryptosystems that had seemed like magic suddenly made complete algebraic sense. That’s what I want to recreate here: a focused walkthrough of the number-theoretic toolbox itself.

History and Background

I trace nearly all of these tools back over two thousand years. The Euclidean algorithm for computing the greatest common divisor appears in Euclid’s Elements (circa 300 BC) and is often cited as the oldest algorithm still in common use today. Fermat’s Little Theorem dates to the 17th century. Euler generalized it in the 18th century into what we now call Euler’s theorem, along with defining the Euler totient function that bears his name. The Chinese Remainder Theorem traces back even further, to the Chinese mathematician Sun Tzu (the mathematician, not the military strategist) in the 3rd to 5th century AD, originally posed as a puzzle about counting soldiers. What I find remarkable is that these tools sat as “pure” mathematics — elegant but without obvious practical urgency — for centuries, until the 1970s public-key cryptography revolution (RSA, Diffie-Hellman) suddenly made them absolutely central to real-world computer security.

Problem Statement

The number-theoretic algorithms I cover here solve a cluster of closely related problems: finding the greatest common divisor of two integers efficiently; finding modular inverses (the “division” operation in modular arithmetic); computing large modular exponentiations efficiently (essential for RSA and Diffie-Hellman); counting integers coprime to a given number (Euler’s totient function, essential for RSA key generation); and solving systems of simultaneous modular congruences (the Chinese Remainder Theorem, used both to speed up RSA decryption and in some cryptanalytic attacks). Each of these, on its own, would be a minor curiosity; together, they form the operational core of modern public-key cryptography.

Core Concepts

How It Works

I’ll walk through each core algorithm’s mechanics briefly:

Euclidean algorithm (GCD):

  1. Given integers $a$ and $b$ (with $a \ge b > 0$), I repeatedly replace $(a, b)$ with $(b, a \bmod b)$.
  2. I continue until $b = 0$; at that point, $a$ is the GCD.

Extended Euclidean algorithm:

  1. I run the same division steps as the standard Euclidean algorithm, but I additionally track coefficients that express each remainder as a linear combination of the original $a$ and $b$.
  2. By the time I reach the final nonzero remainder (the GCD), I’ve also computed $x$ and $y$ such that $ax + by = \gcd(a,b)$.
  3. If $\gcd(a,m) = 1$, the coefficient $x$ (reduced modulo $m$) is exactly the modular inverse $a^{-1} \bmod m$.

Modular exponentiation (square-and-multiply):

  1. I write the exponent $b$ in binary.
  2. I process the bits from most significant to least significant, squaring a running result at each step, and multiplying in the base whenever the current bit is 1.
  3. This computes $a^b \bmod m$ using only $O(\log b)$ modular multiplications instead of $b – 1$.

Chinese Remainder Theorem:

  1. Given congruences $x \equiv a_1 \pmod{m_1}$, $x \equiv a_2 \pmod{m_2}$, …, with pairwise coprime moduli, I compute $M = m_1 m_2 \cdots m_k$.
  2. For each $i$, I compute $M_i = M / m_i$ and its modular inverse $y_i = M_i^{-1} \bmod m_i$ (via the Extended Euclidean algorithm).
  3. The unique solution modulo $M$ is $x \equiv \sum_i a_i M_i y_i \pmod M$.

Working Principle

I think the deep unifying idea behind all of these algorithms is that modular arithmetic behaves like ordinary arithmetic in most respects (it forms a ring, and when the modulus is prime, a field), but with the crucial difference that “division” only works for numbers coprime to the modulus, and that inverse must be constructed rather than computed directly — this is exactly what the Extended Euclidean algorithm provides. Euler’s theorem tells me that exponentiation “wraps around” with a period related to $\varphi(n)$, which is what lets RSA’s encryption/decryption exponents be chosen as multiplicative inverses of each other modulo $\varphi(n)$ rather than modulo $n$ itself — a subtle but essential distinction. The Chinese Remainder Theorem, meanwhile, exploits the fact that working modulo a composite number with coprime factors is mathematically equivalent to working independently modulo each factor and recombining — this isomorphism (formally, $\mathbb{Z}{m_1 m_2} \cong \mathbb{Z}{m_1} \times \mathbb{Z}_{m_2}$) both accelerates RSA decryption (by doing smaller computations modulo $p$ and $q$ separately instead of one large computation modulo $n$) and, when implemented carelessly, opens the door to certain fault-injection cryptanalytic attacks.

Mathematical Foundation

Euclidean algorithm identity:

$$\gcd(a, b) = \gcd(b, a \bmod b), \qquad \gcd(a, 0) = a$$

Bézout’s identity (from the Extended Euclidean algorithm):

$$ax + by = \gcd(a, b) \text{ for some integers } x, y$$

Modular inverse (when $\gcd(a,m)=1$):

$$a \cdot a^{-1} \equiv 1 \pmod{m}$$

Fast modular exponentiation, writing $b$ in binary as $b = \sum_i b_i 2^i$:

$$a^b = \prod_{i : b_i = 1} a^{2^i} \pmod m$$

computed via repeated squaring in $O(\log b)$ steps.

Euler’s totient function, for $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$:

$$\varphi(n) = n \prod_{i=1}^{k} \left(1 – \frac{1}{p_i}\right)$$

For $n = pq$ with $p, q$ distinct primes:

$$\varphi(n) = (p-1)(q-1)$$

Euler’s theorem:

$$a^{\varphi(n)} \equiv 1 \pmod n \quad \text{for } \gcd(a,n)=1$$

Chinese Remainder Theorem reconstruction, given $x \equiv a_i \pmod{m_i}$ for pairwise coprime $m_i$, with $M = \prod m_i$, $M_i = M/m_i$, and $y_i = M_i^{-1} \bmod m_i$:

$$x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod M$$

RSA’s use of these tools together: choosing primes $p, q$, computing $n = pq$ and $\varphi(n) = (p-1)(q-1)$, choosing public exponent $e$ coprime to $\varphi(n)$, and computing private exponent $d = e^{-1} \bmod \varphi(n)$ via the Extended Euclidean algorithm — encryption is $c = m^e \bmod n$ (fast modular exponentiation), and decryption is $m = c^d \bmod n$, which works precisely because of Euler’s theorem: $c^d = m^{ed} = m^{1 + k\varphi(n)} = m \cdot (m^{\varphi(n)})^k \equiv m \cdot 1^k = m \pmod n$.

Diagrams

flowchart TD
    A[Choose primes p, q] --> B[Compute n = p*q]
    B --> C[Compute phi_n = p-1 * q-1]
    C --> D[Choose e coprime to phi_n]
    D --> E[Extended Euclidean: compute d = e^-1 mod phi_n]
    E --> F[Public key: n, e   Private key: d]
    F --> G[Encrypt: c = m^e mod n via fast exponentiation]
    G --> H[Decrypt: m = c^d mod n via Euler theorem]

Pseudocode

// Extended Euclidean Algorithm: returns (gcd, x, y) such that a*x + b*y = gcd
function extended_gcd(a, b):
    if b == 0:
        return (a, 1, 0)
    gcd, x1, y1 = extended_gcd(b, a mod b)
    x = y1
    y = x1 - (a div b) * y1
    return (gcd, x, y)

function mod_inverse(a, m):
    gcd, x, _ = extended_gcd(a, m)
    if gcd != 1:
        error("no inverse exists")
    return ((x mod m) + m) mod m

// Fast modular exponentiation (square-and-multiply)
function pow_mod(base, exp, mod):
    result = 1
    base = base mod mod
    while exp > 0:
        if exp is odd:
            result = (result * base) mod mod
        base = (base * base) mod mod
        exp = exp div 2
    return result

// Euler's totient for n = p*q
function totient_of_semiprime(p, q):
    return (p - 1) * (q - 1)

// Chinese Remainder Theorem
function crt(remainders[], moduli[]):
    M = product(moduli)
    x = 0
    for i in 0..len(moduli)-1:
        Mi = M / moduli[i]
        yi = mod_inverse(Mi, moduli[i])
        x = x + remainders[i] * Mi * yi
    return x mod M

Step-by-Step Example

I’ll build a small full RSA-style example using all these tools together.

  1. I choose primes p = 61 and q = 53.
  2. n = p*q = 61*53 = 3233.
  3. phi(n) = (p-1)(q-1) = 60*52 = 3120.
  4. I choose public exponent e = 17 (I check gcd(17, 3120) = 1, which holds since 17 is prime and doesn’t divide 3120).
  5. I compute d = e^-1 mod 3120 using the Extended Euclidean algorithm. Running the algorithm: 3120 = 183*17 + 9, 17 = 1*9 + 8, 9 = 1*8 + 1, 8 = 8*1 + 0. Back-substituting: 1 = 9 - 1*8 = 9 - 1*(17-1*9) = 2*9 - 1*17 = 2*(3120-183*17) - 1*17 = 2*3120 - 367*17. So x = -367 for the 17 coefficient. Reducing modulo 3120: -367 mod 3120 = 2753. So d = 2753.
  6. Verification: 17 * 2753 = 46801. 46801 / 3120 = 15.0003..., 15*3120=46800, remainder 1. Confirmed: 17*2753 ≡ 1 (mod 3120).
  7. Public key: (n=3233, e=17). Private key: d=2753.
  8. To encrypt message m = 65: c = 65^17 mod 3233. Using fast modular exponentiation (square-and-multiply), this evaluates to c = 2790.
  9. To decrypt: m = 2790^2753 mod 3233. Using fast modular exponentiation again, this evaluates back to m = 65, matching the original plaintext exactly — demonstrating Euler’s theorem in action.

Time Complexity

Space Complexity

All of these algorithms require only $O(\log n)$ space (proportional to the bit-length of the numbers involved) to store intermediate values, coefficients, and results — none of them require storage proportional to the numeric value of $n$ itself, which is what makes them practical even for the enormous numbers (hundreds of digits) used in real RSA and Diffie-Hellman implementations.

Correctness Analysis

I verify the Euclidean algorithm’s correctness via the identity $\gcd(a,b) = \gcd(b, a \bmod b)$, which follows because any common divisor of $a$ and $b$ must also divide $a \bmod b = a – qb$, and conversely; since the second argument strictly decreases each step and is bounded below by zero, the algorithm terminates, and it terminates precisely at the GCD by this invariant. The Extended Euclidean algorithm’s correctness follows by induction on the same recursive structure, tracking that at every step, the current remainder can indeed be expressed as an integer linear combination of the original $a$ and $b$ — this invariant is preserved by the back-substitution at each level of the recursion. Euler’s theorem’s correctness is a consequence of Lagrange’s theorem from group theory: the multiplicative group of integers coprime to $n$ has order $\varphi(n)$, so by Lagrange’s theorem, every element’s order divides $\varphi(n)$, meaning raising any such element to the $\varphi(n)$ power returns the identity (1). The Chinese Remainder Theorem’s correctness follows from verifying that the constructed $x = \sum a_i M_i y_i$ indeed satisfies each congruence individually (since $M_i \equiv 0 \pmod{m_j}$ for $j \ne i$, only the $i$-th term survives modulo $m_i$, and $M_i y_i \equiv 1 \pmod{m_i}$ by construction, so $x \equiv a_i \pmod{m_i}$), plus the ring isomorphism guarantee that this solution is unique modulo $M$.

Advantages

Disadvantages

Applications

These number-theoretic algorithms underlie RSA key generation, encryption, and decryption; Diffie-Hellman and ElGamal’s modular exponentiation operations; CRT-based speedups for RSA private-key operations in essentially every major cryptographic library; and various other cryptographic protocols relying on modular arithmetic, including some secret-sharing schemes (which use CRT-like reconstruction) and zero-knowledge proof systems. Beyond cryptography, these same algorithms appear throughout computer algebra systems, coding theory (error-correcting codes), and general computational number theory research.

Implementation in C

#include <stdio.h>
#include <stdint.h>

/* Extended Euclidean algorithm: computes gcd and Bezout coefficients */
int64_t extended_gcd(int64_t a, int64_t b, int64_t *x, int64_t *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }
    int64_t x1, y1;
    int64_t gcd = extended_gcd(b, a % b, &x1, &y1);
    *x = y1;
    *y = x1 - (a / b) * y1;
    return gcd;
}

int64_t mod_inverse(int64_t a, int64_t m) {
    int64_t x, y;
    int64_t g = extended_gcd(a, m, &x, &y);
    if (g != 1) {
        printf("No modular inverse exists\n");
        return -1;
    }
    return ((x % m) + m) % m;
}

/* fast modular exponentiation */
uint64_t pow_mod(uint64_t base, uint64_t exp, uint64_t mod) {
    uint64_t result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (uint64_t)(( (__uint128_t)result * base) % mod);
        base = (uint64_t)(( (__uint128_t)base * base) % mod);
        exp >>= 1;
    }
    return result;
}

int main(void) {
    /* Demonstrate a full small RSA example */
    int64_t p = 61, q = 53;
    int64_t n = p * q;
    int64_t phi = (p - 1) * (q - 1);
    int64_t e = 17;

    int64_t d = mod_inverse(e, phi);

    printf("p=%lld q=%lld n=%lld phi(n)=%lld\n", p, q, n, phi);
    printf("Public exponent e=%lld\n", e);
    printf("Private exponent d=%lld\n", d);

    uint64_t message = 65;
    uint64_t cipher = pow_mod(message, (uint64_t)e, (uint64_t)n);
    uint64_t decrypted = pow_mod(cipher, (uint64_t)d, (uint64_t)n);

    printf("Message:   %llu\n", (unsigned long long)message);
    printf("Encrypted: %llu\n", (unsigned long long)cipher);
    printf("Decrypted: %llu\n", (unsigned long long)decrypted);

    return 0;
}

Sample Input and Output

Input: the classic textbook RSA example with p=61, q=53, e=17, message m=65.

Output:

p=61 q=53 n=3233 phi(n)=3120
Public exponent e=17
Private exponent d=2753
Message:   65
Encrypted: 2790
Decrypted: 65

This matches my hand-worked example exactly, and the successful Decrypted: 65 confirms Euler’s theorem doing its job correctly.

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version