Native BigInt division doesn't yield the correct result

[madztheo]

Aim

I'm currently working with the newly released native BigInt and when I divide two BigInts the result is incorrect. I've tried with Secpk1Fq and Bn254Fr, and also directly with the BigInt struct (by implementing the different traits myself).

Expected Behavior

The division between two BigInts should yield the correct result.

Side note, there should be a clearer separation between BigField and BigInt, with the first doing field division and the latter actual euclidean division.

Bug

For example, the test below fails, while it shouldn't since 10 / 5 = 2

#[test]
fn test_div() {
    let a = Secpk1Fq::from_le_bytes([10]);
    let b = Secpk1Fq::from_le_bytes([5]);
    let res = a / b;
    assert(res == Secpk1Fq::from_le_bytes([2]));
}

But the test below succeeds, while it shouldn't

#[test]
fn test_div() {
    let a = Secpk1Fq::from_le_bytes([10]);
    let b = Secpk1Fq::from_le_bytes([5]);
    let res = a / b;
    assert(res == Secpk1Fq::from_le_bytes([10]));
}

In general, the result of the division of two BigInts is equal to the dividend of the division, so in this case a. Swapping Secpk1Fq with Bn254Fr leads to the same behavior.

I also created a custom implementation of the BigInt struct with my own modulo (2^256) and implemented the necessary traits similarly to Secpk1Fq and Bn254Fr. In this case, the behavior when dividing two instances of the struct is different but still yields incorrect results. For example, the following test passes just fine as expected:

#[test]
fn test_div() {
    let a = BigInt256::from_le_bytes([10]);
    let b = BigInt256::from_le_bytes([5]);
    let res = a / b;
    assert(res == BigInt256::from_le_bytes([2]));
}

However, for some other numbers, the result is incorrect as the division just yields 0 as in this case:

#[test]
fn test_div() {
    let a = BigInt256::from_le_bytes([128]);
    let b = BigInt256::from_le_bytes([2]);
    let res = a / b;
    assert(res == BigInt256::from_le_bytes([64]));
}

To Reproduce

1. Initiate two instances of Secpk1Fq
2. Divide them
3. Check if the result is the one you would expect

Project Impact

Blocker

Impact Context

No response

Workaround

None

Workaround Description

No response

Additional Context

No response

Installation Method

Binary (noirup default)

Nargo Version

nargo version = 0.25.0 noirc version = 0.25.0+6a9ea35c4f1578058179aa08eedf44eb18bad4a1

NoirJS Version

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response