bug: inv_mod_p_uint512 returns incorrect inverse for primes > CAIRO_PRIME (Felt252 truncation not addressed by #2262)

[martin-ochoa]

Describe the bug

inv_mod_p_uint512 converts its result through a Felt252 intermediate before splitting it into a Uint256. Felt252 reduces values modulo CAIRO_PRIME (ca. 2^251), so for any prime p > CAIRO_PRIME, inverse results that fall in the range [CAIRO_PRIME, p) are silently reduced, producing a value that is no longer a valid modular inverse.

This is the same class of bug that was fixed for inv_mod_p_uint256 and uint384_div in #2262, but the 512-bit variant was not included in that fix.

The buggy conversion path at vm/src/hint_processor/builtin_hint_processor/vrf/inv_mod_p_uint512.rs lines 41-47:

let x_inverse_mod_p = Felt252::from(&div_mod(  // BigInt -> Felt252: reduces mod CAIRO_PRIME
    &BigInt::one(),
    &BigInt::from(x),
    &BigInt::from(p),
)?);
let x_inverse_mod_p = Uint256::from(x_inverse_mod_p);  // already truncated

The correct pattern (used in fq.rs lines 105-107 after #2262):

let b_inverse_mod_p = div_mod_unsigned(&BigUint::one(), &b, &p)?;
let res = Uint256::from(&b_inverse_mod_p);  // BigUint -> Uint256 directly, no Felt252

The existing test (run_inv_mod_p_uint512_ok) and the Cairo program (cairo_programs/inv_mod_p_uint512.cairo) both use the BN254 prime (254 bits, larger than CAIRO_PRIME), but with a specific x = (101, 2, 15, 61) whose inverse happens to be < CAIRO_PRIME. For about 84% of inputs with this prime, the inverse exceeds CAIRO_PRIME and the hint returns an incorrect result.

To Reproduce

Add this test to vm/src/hint_processor/builtin_hint_processor/vrf/inv_mod_p_uint512.rs inside the tests module:

#[test]
fn run_inv_mod_p_uint512_truncation_poc() {
    // Uses the SAME BN254 prime as the existing test and Cairo program,
    // but with x = 2, whose inverse is >= CAIRO_PRIME.
    let mut vm = vm_with_range_check!();
    add_segments!(vm, 3);
    vm.run_context.fp = 25;

    let ids_data = non_continuous_ids_data![("x", -5), ("p", -10), ("x_inverse_mod_p", -20)];

    // x = 2, same p as the existing test (BN254)
    vm.segments = segments![
        ((1, 20), 2), // x.d0
        ((1, 21), 0), // x.d1
        ((1, 22), 0), // x.d2
        ((1, 23), 0), // x.d3
    ];
    vm.insert_value(Relocatable::from((1, 15)),
        felt_str!("201385395114098847380338600778089168199")).unwrap(); // p.low (BN254)
    vm.insert_value(Relocatable::from((1, 16)),
        felt_str!("64323764613183177041862057485226039389")).unwrap();  // p.high (BN254)

    let mut exec_scopes = ExecutionScopes::new();
    assert!(run_hint!(vm, ids_data, INV_MOD_P_UINT512, &mut exec_scopes).is_ok());

    // Reconstruct p and the returned result as BigUints
    let p = BigUint::from_str_radix(
        "201385395114098847380338600778089168199", 10).unwrap()
        + (BigUint::from_str_radix(
            "64323764613183177041862057485226039389", 10).unwrap() << 128);
    let result = vm.get_integer(Relocatable::from((1, 5))).unwrap().to_biguint()
        + (vm.get_integer(Relocatable::from((1, 6))).unwrap().to_biguint() << 128);

    // A correct inverse of 2 must satisfy (2 * result) % p == 1. This fails.
    assert_ne!(
        (BigUint::from(2u32) * &result) % &p,
        BigUint::from(1u32),
    );
}

Then run:

make deps
source cairo-vm-env/bin/activate
make cairo_test_programs cairo_proof_programs
cargo test -p cairo-vm run_inv_mod_p_uint512_truncation_poc -- --nocapture

Result: test result: ok. 1 passed (confirming the returned value is not a valid modular inverse).

Expected behavior

The hint should return x_inverse_mod_p such that (x * x_inverse_mod_p) % p == 1 for all valid inputs, regardless of whether the result exceeds CAIRO_PRIME.

What version/commit are you on?

v3.1.0 (b167460)

Additional context

• This is a completeness issue, not soundness: Cairo constraints will reject the incorrect inverse, so no invalid proof can be generated, but honest provers cannot complete execution for affected inputs.
• The fix from fix(vrf): use div_mod_unsigned and remove unwrap_or_default #2262 (div_mod_unsigned + direct Uint256::from(&BigUint)) can be applied to inv_mod_p_uint512 in the same way.
• Any prime > CAIRO_PRIME is affected. With BN254 (used in the project's own test/program), ~84% of inputs trigger truncation. With Ed25519's 2^255 - 19, ~50%.