modulo multiplication and division errors

porco-rosso-j commented 6 months ago

Aim

div method error for the new Bn254Fr in BigInt lib has recently been found and fixed, but there are still cases where it doesn't return expected outputs. Also, mul has a similar upper limit issue described below, which might be related to the bug in the division.

Expected Behavior

For the following test code:

fn main() {
    // num = Fr's modulus - 1
    let num = field_to_bn254fr(21888242871839275222246405745257275088548364400416034343698204186575808495616);
    let num2 = field_to_bn254fr(3189391831712126);

    let ret = num.mul(num2);
    println(bn254fr_to_field(ret));
    // let exp = field_to_bn254fr(21888242871839275222246405745257275088548364400416034343698200997183976783491);
    // assert(ret.eq(exp));

    let ret = num.div(num2);
    println(bn254fr_to_field(ret));

    // let exp = field_to_bn254fr(17503393246338744135796705401862936143640286084087976183614677346605260623896);
    // assert(ret.eq(exp));
}

where bn254fr_to_field and field_to_bn254fr are found here

expected outputs that can be computed by mul and div Fr class in aztec.js is below.

// mul
0x30644e72e131a029b85045b68181585d2833e84879b9709143d6a0d7c8d23e83
// div
0x26b291cadf48b919fc0e28a1ff0727816d942d9bb5bdc03ea7d4d4ad5a985018

but the values i got for println are :


// mul
0x1569498e920eee22ea8c49c802b9f270b61bf490b42c2df555f62eba31994f4b
// div
0x2c4

Bug

Failure Patterns

The following are the behaviors of the mul and div methods depending on different inputs, which might help find solutions.

1: the numerator is not divisible in the normal division

As for division, even if the numbers, both numerator and denominator, are really large, the division doesn't output any wrong value as long as the numerator is divisible by the denominator in normal division.

num: 10000000000000000000000000000000000000000000000000000000000000
num2: 5000000000000000000000000000000000000000000000000000000000000
output: 0x02 // correct output

but below fails

num: 10000000000000000000000000000000000000000000000000000000000000
num2: 5000000000000000000000000000000000000000000000000000000000001 
output: 0x02a4c37133ef8527cd860d46b8a5549082c27888eddf113efba7f6243a68a7a6 // wrong
expected: 0x2f357e093e8519296d6c79abc4a30e342cf11c0ef416c9dfd665e3c18ba8f366 // correct

2: the product of inputs exceeds bn254fr modulus `0x30644e72e131...3e1f593f0000001`

mul computes the wrong value when the outcome of x * y in the normal multiplication exceeds the modulus value.

example case A: the product doesn't exceed modulus

num: 73973378440894659502865346085498129804
num2: 73973378440894659502865346085498129804
output: 0x0c19139cb84c680a6e14116da0605616e8a928124d8d0d670905019591578490 // correct value

product: 5472060717959818805561601436314318772007637687832442931792674567981633078416 // smaller than modulus

example case B: the product does exceed modulus

num: 2958935137635786380114613843419925192240
num2: 73973378440894659502865346085498129804
output: 0x2259d6b14729c0fa51e1a247090812311dbafd1f83f265537084b2072a70f60d // wrong output
expected: 0x000000000000000000000000000000022c838b6ca999c1ebd938f08e8a70f236

product: 218882428718392752222464057452572750886223377788569290031936210406105173520960 // greater than modulus

To Reproduce

Minimal reproduction repo is here

Project Impact

Blocker

Impact Context

No response

Workaround

None

Workaround Description

No response

Additional Context

No response

Installation Method

None

Nargo Version

nargo version = 0.27.0

NoirJS Version

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response

porco-rosso-j commented 6 months ago

plz close this as it's incomplete but published somehow which i didn't notice. Instead, keep #4882 🙏

Savio-Sou commented 6 months ago

Duplicate of #4882.

noir-lang / noir