Bn254Fr modulo multiplication and division errors

[porco-rosso-j]

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
0x2c441177496e0648260def25a86a4346f60a6df06d09a9032ecf3c751823a89b

Bug

Can't pinpoint what's the bug, but the following are the behaviors of the mul and div methods depending on different inputs, which might help find solutions.

1: when the numerator is not divisible in the normal division

As for division, the division outputs a wrong value if the numerator isn't divisible by the denominator in normal division. The size of numbers doesn't matter.

example A:

num: 10
num2: 3
output: 0x197dbf520715ca2d81b9d9872626a193320ef1d13d7e58f6df04c9ee2ffffd75 // wrong
expected: 0x2042def740cbc01bd03583cf0100e59370229adafbd0f5b62d414e62a0000004 // correct

example B:

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

but below passes

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

2: when 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

Compiled from source

Nargo Version

nargo version = 0.27.0 noirc version = 0.27.0+073563568e53f81d8ad0ca71e9e34e03174239ec

NoirJS Version

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response