TheAlgorithms/Rust · error

Failed to compute modular inverse

Error message

Failed to compute modular inverse

What it means

generate_keypair(p, q) panics with this .expect() message when mod_inverse(e, phi) returns None (src/ciphers/rsa_cipher.rs:162). The e-selection loop looks for e in [2, phi) with gcd(e, phi) == 1; if none exists the loop exits with e == phi, whose inverse mod phi cannot exist (gcd(phi, phi) = phi > 1), mod_inverse signals None, and expect aborts. In practice this means (p-1)*(q-1) came out as 0 or 2 — e.g. one 'prime' is 1, or the pair is (2,3)/(3,2) — or phi overflowed u64 for huge primes, which also breaks the `phi as i64` cast inside mod_inverse.

Source

Thrown at src/ciphers/rsa_cipher.rs:162

///
/// # Panics
///
/// Panics if the modular inverse cannot be computed
pub fn generate_keypair(p: u64, q: u64) -> (PublicKey, PrivateKey) {
    let n = p * q;
    let phi = (p - 1) * (q - 1);

    // Choose e such that 1 < e < phi and gcd(e, phi) = 1
    let mut e = 2;
    while e < phi {
        if gcd(e, phi) == 1 {
            break;
        }
        e += 1;
    }

    // Compute d, the modular multiplicative inverse of e mod phi
    let d = mod_inverse(e as i64, phi as i64).expect("Failed to compute modular inverse");

    let public_key = PublicKey { n, e };
    let private_key = PrivateKey { n, d };

    (public_key, private_key)
}

/// Encrypts a message using the RSA public key
///
/// # Arguments
///
/// * `message` - The plaintext message (must be less than n)
/// * `public_key` - The public key to use for encryption
///
/// # Returns
///
/// The encrypted ciphertext
///

View on GitHub (pinned to 2c53ddfa4b)

Solutions

1. Call generate_keypair with two distinct odd primes of reasonable size, e.g. generate_keypair(61, 53) as in the module docs — phi = 3120, e = 7 is found, d = 1783, no panic.
2. Validate primes before calling: reject 1, non-primes, and p == q; require phi = (p-1)*(q-1) >= 3 so an e below phi exists.
3. Keep each prime below ~3.03e9 so (p-1)*(q-1) and p*q fit in u64 and phi survives the `as i64` cast in mod_inverse; use checked_mul when computing them.
4. If you maintain the code, replace .expect with a Result carrying p, q, and phi, and make the e-search loop assert it found e < phi instead of silently exiting at e == phi.
5. For anything real, switch to a maintained crate (rsa, ring) — this module is explicitly educational.

Example fix

// before
let (public_key, private_key) = generate_keypair(2, 3);
// phi = (2-1)*(3-1) = 2 → no e in [2, 2) is coprime to phi → panic:
// 'Failed to compute modular inverse'

// after
let (public_key, private_key) = generate_keypair(61, 53);
// phi = 3120, e = 7, d = 1783 — keypair builds fine

fn is_prime(n: u64) -> bool {
    if n < 2 {
        return false;
    }
    let mut i = 2u64;
    while i.saturating_mul(i) <= n {
        if n % i == 0 {
            return false;
        }
        i += 1;
    }
    true
}

fn valid_rsa_primes(p: u64, q: u64) -> bool {
    if p == q || !is_prime(p) || !is_prime(q) {
        return false;
    }
    // phi must be >= 3 (an e below phi exists) and fit i64; n must not wrap
    matches!((p - 1).checked_mul(q - 1), Some(phi) if phi >= 3 && phi < (1u64 << 63))
        && p.checked_mul(q).is_some()
}

if valid_rsa_primes(p, q) {
    let keys = generate_keypair(p, q); // cannot hit the expect()
}

// generate_keypair panics rather than returning Err; if inputs are untrusted,
// isolate the panic (validation above is the real fix):
let keys = match std::panic::catch_unwind(|| generate_keypair(p, q)) {
    Ok(keys) => keys,
    Err(_) => {
        // p/q unusable (phi = 0 or 2, or overflow): log and pick new primes
        generate_keypair(61, 53)
    }
};

When it happens

Trigger: generate_keypair(2, 3) or generate_keypair(3, 2): phi = 2, the loop body never runs (2 < 2 is false), e stays 2, gcd(2,2) = 2 → None → panic. generate_keypair(1, q) or any argument equal to 1: phi = 0, mod_inverse(2, 0) sees old_r = 2 > 1 → None → panic. Primes so large that (p-1)*(q-1) wraps u64 (each above ~3.03e9 = sqrt(2^63)): the wrapped phi makes the signed cast in mod_inverse negative-valued and the keypair silently breaks or panics.

Common situations: Following RSA walkthroughs with toy primes and picking the smallest ones (2 and 3); degenerate or fuzzed test inputs where a 'prime' is 1; user- or config-supplied primes without validation; porting examples that used 61/53 to randomly generated big primes that overflow the u64 arithmetic; expecting a Result and getting a process-aborting panic instead.

Related errors

• InvalidData
• Encountered NaN

AI-assisted analysis of TheAlgorithms/Rust@2c53ddfa4b (2026-08-16). Data as JSON: /api/errors/b7466913edf6aa8f. Report an issue: GitHub.