bug: inverse_mod returns invalid value

[nils-mathieu]

Bug Report

stark-felt version: 0.0.3
commit: ea52b64

Behavior:

The inverse_mod functions returns an invalid value: 3.inverse_mod(5) returns 4 instead of 2.

Indeed 3 * 4 == 12 and 12 % 5 == 2 != 1.

Other information:

I found this writing documentation (see #10). If you download that PR and run cargo test, you'll get the error.

Currently, the only test for inverse_mod is this one:

#[test]
fn inverse_mod_in_range(x in nonzero_felt(), p in nonzero_felt()) {
    let nzp = NonZeroFelt(p.0);
    prop_assert!(x.inverse_mod(&nzp) <= Some(Felt::MAX));
    prop_assert!(x.inverse_mod(&nzp) < Some(p));
}

Which only checks whether the resulting inverse is less than p. It should probably check something like x.inverse_mod(&nzp).mul_mod(x, &nzp) == 1.

[nils-mathieu]

Update: this test do not pass.

#[test]
fn inverse_mod_in_range(x in nonzero_felt(), p in nonzero_felt()) {
    let nzp = NonZeroFelt(p.0);

    let Some(ret) = x.inverse_mod(&nzp) else { return Ok(()) };

    prop_assert!(ret <= Felt::MAX);
    prop_assert!(ret < p);
    prop_assert!(ret.mul_mod(&x, &nzp) == Felt::ONE);
}

[pefontana]

Thanks for the report @nils-mathieu
I am currently checking it!

[pefontana]

Hi @nils-mathieu !
I just reviewed it, and the documentation of the methods are not clear.
The inverse_mod method first calculates the multiplicative inverse and then it calculates the mod. We don't calculate the inverse of the number changing the Prime field. The same happens with the mul_mod method, we first calculate the multiplication and then apply the mod. So, the condition ret.mul_mod(&x, &nzp) == Felt::ONE don't have to be true

I just checked and we don't use this operation in the cairo-vm, I am not really sure if other projects need them.
I can make a PR adding more documentation to the methods, or just delete them if they generate confusion

Tell me what you think!

@xJonathanLEI @abdelhamidbakhta. Do you require these operations in your projects?

[nils-mathieu]

@pefontana Oooh, I see. It's more a metter of naming in that case imo.
I don't have any strong feelings about this.

[pefontana]

Great @nils-mathieu !
I made a PR #14, modifying the Fellt::mul_mod method documentation and removing the Fellt::inverse_mod method

[xJonathanLEI]

Do you require these operations in your projects?

I use mod_inverse in starknet-rs which calculates the inverse under the new prime.

https://github.com/xJonathanLEI/starknet-rs/blob/cfa3c43e4c12ca3a45c471b233fe3eb5a2f31e0c/starknet-crypto/src/fe_utils.rs#L46-L67

[pefontana]

Thanks @xJonathanLEI
I will implement it!