Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Different div_mod implementations #1381

Closed
Juan-M-V opened this issue Aug 16, 2023 · 0 comments
Closed

Different div_mod implementations #1381

Juan-M-V opened this issue Aug 16, 2023 · 0 comments
Assignees
Labels
bug Something isn't working

Comments

@Juan-M-V
Copy link
Contributor

Juan-M-V commented Aug 16, 2023

Describe the bug
div_mod implementation differs from python's implementation.

def div_mod(n, m, p):
    """
    Finds a nonnegative integer x < p such that (m * x) % p == n.
    """
    a, b, c = igcdex(m, p)
    assert c == 1
    return (n * a) % p
///Finds a nonnegative integer x < p such that (m * x) % p == n.
pub fn div_mod(n: &BigInt, m: &BigInt, p: &BigInt) -> BigInt {
    let a = mul_inv(m, p);
    (n * a).mod_floor(p)
}

Python's assert makes it so that m != p

To Reproduce
Create any program with a hint that uses the div_mod function, here is an example:

struct MyStruct0 {
	high: felt,
    low: felt,
}
​
func main() {
	let a = MyStruct0(high=1, low=340282366920938463463374607431768211456);
	let b = MyStruct0(high=1, low=1);
	let p = MyStruct0(high=1, low=1);
	let (a, b, p, b_inverse_mod_p) = hint_func(a, b, p);
​
	return();
}
​
func hint_func(a: MyStruct0, b: MyStruct0, p: MyStruct0) -> (MyStruct0, MyStruct0, MyStruct0, MyStruct0) {
	alloc_locals;
	local b_inverse_mod_p: MyStruct0;
    %{
        from starkware.python.math_utils import div_mod
​
        def split(a: int):
            return (a & ((1 << 128) - 1), a >> 128)
​
        def pack(z, num_bits_shift: int) -> int:
            limbs = (z.low, z.high)
            return sum(limb << (num_bits_shift * i) for i, limb in enumerate(limbs))
​
        a = pack(ids.a, 128)
        b = pack(ids.b, 128)
        p = pack(ids.p, 128)
        # For python3.8 and above the modular inverse can be computed as follows:
        # b_inverse_mod_p = pow(b, -1, p)
        # Instead we use the python3.7-friendly function div_mod from starkware.python.math_utils
        b_inverse_mod_p = div_mod(1, b, p)
​
        b_inverse_mod_p_split = split(b_inverse_mod_p)
​
        ids.b_inverse_mod_p.low = b_inverse_mod_p_split[0]
        ids.b_inverse_mod_p.high = b_inverse_mod_p_split[1]
    %}
	return(a, b, p, b_inverse_mod_p);
}

Expected behavior
Why does python check that condition?

What version/commit are you on?
v0.8.6

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working
Projects
None yet
Development

No branches or pull requests

2 participants