Introduction
Working with prime numbers, modular arithmetic, or cryptographic algorithms? Number theory tools provide the mathematical foundations for modern cryptography and computer science. These include prime number generators, GCD/LCM calculators, modular arithmetic tools, and primality testers. Number theory underpins RSA encryption, Diffie-Hellman key exchange, and many other security protocols. All processing happens in your browser—no data leaves your device.
What this category includes
- Prime number generators and primality testers (Miller-Rabin, Sieve of Eratosthenes)
- GCD (Greatest Common Divisor) and LCM (Least Common Multiple) calculators
- Modular arithmetic tools for computing a^b mod n efficiently
- Euler's totient function φ(n) calculator for RSA key generation
- Chinese Remainder Theorem solver for modular equation systems
How these tools work
Prime number generation uses algorithms like the Sieve of Eratosthenes for small numbers and probabilistic tests like Miller-Rabin for large numbers. The Sieve iteratively marks multiples of each prime as composite, leaving only primes unmarked. Miller-Rabin tests whether a number is a probable prime by checking if it satisfies Fermat's little theorem for random bases—it's probabilistic but extremely accurate with enough iterations.
GCD calculation uses the Euclidean algorithm: gcd(a, b) = gcd(b, a mod b) until b = 0. This runs in O(log min(a,b)) time. LCM is derived from GCD: lcm(a, b) = |a·b| / gcd(a, b). These are fundamental for reducing fractions and finding periodic patterns.
Modular exponentiation (a^b mod n) uses the square-and-multiply algorithm to compute large powers efficiently. Instead of multiplying a by itself b times (O(b)), it uses binary representation of b to compute in O(log b) time. This is essential for RSA encryption where exponents can be 2048 bits or larger.
How the underlying systems work
Number theory dates to ancient Greek mathematics. Euclid's Elements (300 BCE) proved the infinitude of primes and described the Euclidean algorithm for GCD. Fermat's little theorem (1640) states that if p is prime and a is not divisible by p, then a^(p-1) ≡ 1 mod p. This is the foundation of primality testing and RSA encryption.
Euler's totient function φ(n) counts integers from 1 to n that are coprime to n. For a prime p, φ(p) = p-1. For distinct primes p and q, φ(p·q) = (p-1)(q-1). This property is crucial for RSA: the public exponent e and private exponent d satisfy e·d ≡ 1 mod φ(n). Knowing φ(n) allows factoring n, which is why RSA uses large primes (2048+ bits) to make φ(n) computationally infeasible to recover.
The Chinese Remainder Theorem (CRT) states that if n₁, n₂, ..., n_k are pairwise coprime, then the system of congruences x ≡ a_i mod n_i has a unique solution modulo N = n₁·n₂·...·n_k. CRT is used to speed up RSA decryption by computing modulo p and q separately, then combining results.
How to use these tools
- Select the number theory operation based on your need (prime generation, GCD, modular arithmetic)
- Enter your input numbers—for large numbers, the tools support arbitrary precision using BigInt
- For primality testing, choose the algorithm (deterministic for small numbers, Miller-Rabin for large)
- For modular exponentiation, enter base, exponent, and modulus
- View the results with step-by-step explanations where applicable
Real-world examples
RSA Key Generation
A developer generates RSA keys. They use the prime generator to find two large primes p and q (e.g., 1024 bits each). The tool computes n = p·q and φ(n) = (p-1)(q-1). They choose e = 65537 (standard RSA exponent) and use the modular inverse tool to find d such that e·d ≡ 1 mod φ(n). The public key is (n, e), private key is (n, d).
Diffie-Hellman Key Exchange
Two parties establish a shared secret. They agree on a large prime p and generator g. Party A chooses private key a, computes A = g^a mod p using the modular exponentiation tool. Party B chooses private key b, computes B = g^b mod p. They exchange A and B. Party A computes s = B^a mod p, Party B computes s = A^b mod p. Both get the same s = g^(ab) mod p without transmitting it.
Fraction Simplification
A student needs to simplify 24/36. The GCD tool computes gcd(24, 36) = 6. Dividing numerator and denominator by 6 gives 4/6. Running GCD again on 4 and 6 gives 2, yielding 2/3. The LCM tool helps find common denominators: lcm(4, 6) = 12, so 1/4 = 3/12 and 1/6 = 2/12.
Comparison of methods
| Method | Complexity | Typical use |
|---|---|---|
| Sieve of Eratosthenes | O(n log log n) | Small prime generation |
| Miller-Rabin | O(k·log³n) | Large primality testing |
| Euclidean Algorithm | O(log n) | GCD calculation |
| Square-and-Multiply | O(log n) | Modular exponentiation |
| CRT Solver | O(k·log n) | Modular systems |
Limitations
Number theory tools use JavaScript's BigInt for arbitrary precision, but very large numbers (10,000+ digits) may be slow. Miller-Rabin is probabilistic—extremely unlikely to fail with enough iterations, but not deterministic for all numbers. For cryptographic security, use established libraries (OpenSSL, libsodium) rather than implementing algorithms yourself. These tools are for education and small-scale use, not production security systems.
Frequently asked questions
Related categories
Conclusion
Number theory provides the mathematical foundation for modern cryptography. Use these tools to understand prime generation, modular arithmetic, and the algorithms behind RSA and Diffie-Hellman. Remember that these are educational tools—production cryptographic systems require careful implementation, secure random number generation, and adherence to standards like FIPS and NIST guidelines.