LABORATORY 23 · COMPUTER SCIENCE

Public-Key Cryptography & Modular Arithmetic: RSA Key Generation, Square-and-Multiply Exponentiation, Extended Euclidean Algorithm, and Miller-Rabin Primality

To investigate the algorithmic principles of public-key asymmetric cryptography, evaluate the mathematical foundations of the RSA cryptosystem, analyze Euler's Totient Theorem (M^(ed) ≡ M mod n), execute the Extended Euclidean Algorithm to compute modular multiplicative inverses d = e^(-1) mod φ(n), assess strong pseudo-prime generation via the Miller-Rabin test, verify the linear arithmetic scaling law M(B) = k_mod · B + M_0 = 1.5000 · B + 0.0000 operations across exponent bit lengths B ∈ [64, 4096] in Square-and-Multiply modular exponentiation, and evaluate integer factorization complexity under the General Number Field Sieve (GNFS). Explore interactive search algorithms, compare operation counts and analyse complexity scaling.

COMPUTE · BENCHMARK · ANALYSE

Your virtual algorithm laboratory.

MODULAR OPERATIONS M(B)—

EXECUTION STATUS

Ready to execute B benchmark.

Exponent Bit Length B512 bitsSet B (bits)

Modular arithmetic: Multi-precision big integer arithmetic modulo composite n = p · q.

Adjust B n, then execute benchmark.

Operation counts are generated deterministically by the exact algorithmic execution model. Modern hardware benchmarks additionally reflect cache line prefetching and branch misprediction penalties.

Algorithmic assumptions and limits

The simulated benchmark environment models idealized big-integer modular arithmetic where Square-and-Multiply modular operations scale deterministically (M(B) = 1.5B operations). In physical hardware cryptographic security modules (HSMs) and software libraries (OpenSSL), wall-clock latency is heavily modulated by multi-precision word sizes (e.g. 64-bit limbs vs. AVX-512 vector arithmetic), Montgomery residue space reduction overhead, cache line access patterns during sliding-window exponentiation, and constant-time side-channel countermeasure padding. In the Square-and-Multiply modular exponentiation benchmark across private key exponent bit lengths B in [64, 4096] bits (where the exponent d is an IEEE large integer with uniform Hamming weight W ≈ 0.5 · B, representing realistic cryptographic keys), exponentiation proceeds via binary scanning from the most significant bit to the least significant bit. At each bit position i ∈ [0..B-1], the algorithm unconditionally executes exactly 1 modular squaring operation (acc = acc² mod n) to double the binary weight. Additionally, whenever the current bit b_i = 1, the algorithm executes exactly 1 modular multiplication (acc = acc · base mod n). Across an exponent of bit length B, the cumulative arithmetic operation count is strictly governed by the exact deterministic linear invariant M(B) = B + 0.5 · B = 1.5000 · B + 0.0000 modular operations. Plotting modular operations against exponent bit length B yields an ordinary least-squares regression slope k_mod = 1.5000 operations/bit and baseline intercept M_0 = 0.0000 operations with an ideal coefficient of determination R² = 1.000000.

Computational tools & environment.

Square-and-Multiply Binary Exponentiation Unit

Evaluates multi-precision modular powers C = M^e mod n and M = C^d mod n in O(log e) operations via bitwise squarings and conditional multiplications.

Extended Euclidean Modular Inverter

Solves Bézout's identity e · d + φ(n) · y = 1 to compute the modular multiplicative inverse private key exponent d = e^(-1) mod φ(n).

Miller-Rabin Probabilistic Primality Tester

Verifies cryptographic strong pseudo-prime candidates using witness bases and quadratic congruence checks with composite error probability < 2^(-80).

Euler Totient & Key Synthesis Engine

Computes composite modulus n = p · q, Euler's totient φ(n) = (p-1)(q-1), and verifies that public exponent e is coprime to φ(n).

Montgomery Modular Multiplication Accelerator

Transforms large-integer operands into Montgomery residue space to replace multi-precision division with fast bitwise shifts and additions.

Cryptographic Telemetry & Operation Logger

Tracks modular squarings, multiplications, calculates Effective Memory Access Time (EMAT), and validates linear regression against M(B) = 1.5B.

FOLLOW THE METHOD

A reason behind every step.

To investigate the algorithmic principles of public-key asymmetric cryptography, evaluate the mathematical foundations of the RSA cryptosystem, analyze Euler's Totient Theorem (M^(ed) ≡ M mod n), execute the Extended Euclidean Algorithm to compute modular multiplicative inverses d = e^(-1) mod φ(n), assess strong pseudo-prime generation via the Miller-Rabin test, verify the linear arithmetic scaling law M(B) = k_mod · B + M_0 = 1.5000 · B + 0.0000 operations across exponent bit lengths B ∈ [64, 4096] in Square-and-Multiply modular exponentiation, and evaluate integer factorization complexity under the General Number Field Sieve (GNFS). Suggested independent settings: 64, 128, 256, 512, 1024, 2048, 4096 bits.

Prime Candidate Generation & Primality Verification

Generate large random odd integers p and q across benchmark bit lengths B ∈ [64, 128, 256, 512, 1024, 2048, 4096]. Execute 40 rounds of Miller-Rabin primality testing per candidate to guarantee composite error probability < 2^(-80).

Modulus & Euler Totient Synthesis

Multiply prime factors to compute the composite public modulus n = p · q. Calculate Euler's totient function φ(n) = (p - 1)(q - 1).

Public Exponent Validation & Modular Inversion

Select the standard Fermat prime public exponent e = 65537, verifying that gcd(e, φ(n)) = 1. Execute the Extended Euclidean Algorithm to calculate the private decryption exponent d satisfying e · d ≡ 1 (mod φ(n)).

Binary Exponent Scanning & Square-and-Multiply Execution

Decompose the private key exponent d into its binary representation (b_{B-1} ... b_0)_2. Initialize accumulator acc = 1. For each bit from most significant to least significant, execute a modular squaring acc = acc² mod n (incrementing operation counter by 1); if the bit is 1, execute a modular multiplication acc = (acc · base) mod n (incrementing counter by 1).

Decryption Verification via Euler's Totient Theorem

Encrypt a test plaintext integer M < n into ciphertext C = M^e mod n. Decrypt using C^d mod n and verify that M' matches original message M exactly, confirming Euler's theorem M^(ed) ≡ M mod n.

Linear Regression & Complexity Model Validation

Plot recorded modular operations M(B) against exponent bit length B. Perform ordinary least-squares regression to verify the theoretical slope k_mod = 1.5000 operations/bit, intercept M_0 = 0.0000, and correlation coefficient R² = 1.00000.

YOUR NOTEBOOK · 0 OBSERVATIONS

Turn measurements into asymptotic insight.

See a complete example report ↗

Points are your recorded benchmark observations. The regression line validates RSA & Modular Arithmetic complexity scaling.

LINEAR ASYMPTOTIC FIT · y = mx + b

M(B) = k_mod · B + M_0 = 1.5000 · B + 0.0000 operations

#	Exponent Bit Length B (bits)	Modular Operations M(B) (operations)	Exponent bit length B (bits)	Modular operations M(B) = 1.5000 · B + 0.0000 (operations)	Remove

No readings yet. Execute a B benchmark and record it.

Calculate it yourself.

Your estimate of k_mod (operations/bit)

CHECK YOUR UNDERSTANDING

Explain what the operation counts mean.

In the RSA cryptosystem, why is the public exponent e commonly chosen as the Fermat prime 65537 (2^16 + 1)?

For an exponent of bit length B with equal distribution of 0s and 1s, how many total modular multiplications (including squarings) are executed by the Square-and-Multiply algorithm?