Chinese Remainder Theorem — RSA CRT Overflow Traps

from math import gcd
from functools import reduce

def extended_gcd(a, b):
    if b == 0: return a, 1, 0
    g, x1, y1 = extended_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

def crt(remainders: list[int], moduli: list[int]) -> int:
    """
    Solve x ≡ remainders[i] (mod moduli[i]) for all i.
    Moduli must be pairwise coprime.
    Returns x mod M where M = product of all moduli.
    """
    M = 1
    for m in moduli:
        M *= m
    x = 0
    for ai, mi in zip(remainders, moduli):
        Mi = M // mi
        _, yi, _ = extended_gcd(Mi, mi)  # Mi * yi ≡ 1 (mod mi)
        x += ai * Mi * yi
    return x % M

# x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
print(crt([2, 3, 2], [3, 5, 7]))  # 23
# Verify
print(23 % 3, 23 % 5, 23 % 7)    # 2 3 2 ✓

def crt_two(a1, m1, a2, m2):
    """Solve x ≡ a1 (mod m1) and x ≡ a2 (mod m2).
    Works even if gcd(m1,m2) != 1 (if solution exists).
    Returns (x, lcm) or None if no solution.
    """
    g = gcd(m1, m2)
    if (a2 - a1) % g != 0:
        return None  # no solution
    lcm = m1 * m2 // g
    _, p, _ = extended_gcd(m1 // g, m2 // g)
    x = (a1 + m1 * ((a2 - a1) // g * p % (m2 // g))) % lcm
    return x, lcm

print(crt_two(0, 3, 3, 4))  # (3, 12) → x≡3 (mod 12)
print(crt_two(1, 6, 3, 4))  # None — no solution (1 is odd but 3 is odd too... let's check)
print(crt_two(2, 6, 3, 4))  # None — no solution

import java.math.BigInteger;
import java.util.*;

public class GarnerCRT {
    public static BigInteger garnersAlgorithm(
            int[] remainders, int[] moduli) {
        int k = moduli.length;
        BigInteger[] mod = new BigInteger[k];
        BigInteger[] rem = new BigInteger[k];
        for (int i = 0; i < k; i++) {
            mod[i] = BigInteger.valueOf(moduli[i]);
            rem[i] = BigInteger.valueOf(remainders[i]);
        }
        BigInteger x = BigInteger.ZERO;
        BigInteger product = BigInteger.ONE;
        for (int i = 0; i < k; i++) {
            // Compute coefficient c_i
            BigInteger ci = rem[i].subtract(x).mod(mod[i]);
            // Divide by product modulo mod[i]
            BigInteger inv = product.modInverse(mod[i]);
            ci = ci.multiply(inv).mod(mod[i]);
            // If ci is negative, adjust
            if (ci.signum() < 0) ci = ci.add(mod[i]);
            x = x.add(product.multiply(ci));
            product = product.multiply(mod[i]);
        }
        return x;
    }

    public static void main(String[] args) {
        int[] r = {2, 3, 2};
        int[] m = {3, 5, 7};
        System.out.println(garnersAlgorithm(r, m)); // 23
    }
}

import java.math.BigInteger;
import java.security.SecureRandom;

public class RSACRTDecryption {
    // Assume p, q, d are precomuted primes and exponent
    // qInv = q.modInverse(p)
    public static BigInteger crtDecrypt(
            BigInteger c, BigInteger p, BigInteger q,
            BigInteger d, BigInteger qInv) {
        BigInteger dp = d.mod(p.subtract(BigInteger.ONE));
        BigInteger dq = d.mod(q.subtract(BigInteger.ONE));
        BigInteger m1 = c.modPow(dp, p);
        BigInteger m2 = c.modPow(dq, q);
        // h = qInv * (m1 - m2) mod p
        BigInteger h = qInv.multiply(m1.subtract(m2)).mod(p);
        if (h.signum() < 0) h = h.add(p);
        return m2.add(h.multiply(q));
    }

    public static void main(String[] args) {
        // Example (small primes for demonstration)
        BigInteger p = BigInteger.valueOf(61);
        BigInteger q = BigInteger.valueOf(53);
        BigInteger n = p.multiply(q); // 3233
        BigInteger e = BigInteger.valueOf(17);
        BigInteger d = e.modInverse(p.subtract(BigInteger.ONE)
                .multiply(q.subtract(BigInteger.ONE))); // 2753
        BigInteger qInv = q.modInverse(p); // 38
        BigInteger c = BigInteger.valueOf(855); // ciphertext
        BigInteger m = crtDecrypt(c, p, q, d, qInv);
        System.out.println(m); // 123? Actually original message
        // For RSA, m must be < n
    }
}

from math import gcd

def generalized_crt(remainders, moduli):
    # Merge all congruences incrementally
    x, lcm = remainders[0], moduli[0]
    for i in range(1, len(moduli)):
        r = remainders[i]
        m = moduli[i]
        g = gcd(lcm, m)
        if (r - x) % g != 0:
            return None  # no solution
        # Merge: solve x ≡ x (mod lcm) and x ≡ r (mod m)
        lcm_new = lcm * m // g
        # Compute new solution modulo lcm_new
        # Using extended gcd: p*lcm + q*m = g
        _, p, _ = extended_gcd(lcm // g, m // g)
        x = (x + lcm * ((r - x) // g * p % (m // g))) % lcm_new
        lcm = lcm_new
    return x, lcm

# Example where moduli not coprime
print(generalized_crt([2, 2], [6, 8]))  # expects solution mod LCM=24
print(generalized_crt([2, 3], [6, 8]))  # None because 2 ≠ 3 mod 2