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
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](https://github.com/porco-rosso-j/bn254_bigint_mul_div_errors)

### 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]

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

[Savio-Sou]

Duplicate of #4882.