Incorrect params for modulus of bitsize multiple of 120 bits

[ewynx]

Aim

When generating params for a modulus which has bitsize x*120 for some x, the double_modulus and redc_param won't fit into the desired format and turn out incorrect. This is because the expectation is that they both fit into the same size bignum as the modulus (see the struct), but for a modulus that fits so perfectly that is not the case.

For example running the tool on 2^240-1, which has 240 bits
./target/release/paramgen instance 1766847064778384329583297500742918515827483896875618958121606201292619775 Test1 > out1.txt
gives as a result:

struct Test1_Params {}
impl RuntimeBigNumParamsTrait<2> for Test1_Params {
    pub fn modulus_bits() -> u64 {
        240
    }
}
impl BigNumParamsTrait<2> for Test1_Params {
    pub fn get_instance() -> BigNumInstance<2, Self> {
        Test1_Instance
    }
    pub fn modulus_bits() -> u64 {
        240
    }
}
global Test1_Instance: BigNumInstance<2, Test1_Params> = BigNumInstance {
        modulus: [
            0xffffffffffffffffffffffffffffff, 0xffffffffffffffffffffffffffffff
        ],
        double_modulus: [
            0x01fffffffffffffffffffffffffffffe, 0xfffffffffffffffffffffffffffffe
        ],
        modulus_u60: U60Repr { limbs: ArrayX { segments: [[
            0x0fffffffffffffff, 0x0fffffffffffffff], [0x0fffffffffffffff, 0x0fffffffffffffff]] } },
        modulus_u60_x4: U60Repr { limbs: ArrayX { segments: [[
            0x0fffffffffffffff, 0x0fffffffffffffff], [0x0fffffffffffffff, 0x0fffffffffffffff], [0x00, 0x00], [0x00, 0x00]] } },
        redc_param: [
            0x01, 0x00
        ]
};

Here, double_modulus has 121 bits limbs and redc_param has 120 bits limbs but the actual value didn't fit into 2 limbs.

Expected Behavior

For the operations (in their current implementation) in the BigNum library it is necessary that double_modulus and redc_param have the same length as the bignum elements themselves. For example here double_modulus is expected to have length N, just as any bignum mod modulus.

Therefore, a solution is to add an additional limb when the bitsize is 120*x for some x. Of course, this is not great because it increases the number of operations for an almost always empty limb.

Another solution is to keep a few bits of space in each limb. For example, while the radix is 2^120, express a bignum in limbs of 118 bits, to have those 2 bits of space.
Or adjust the param struct and rewrite the code where redc_param or double_modulus is used.

Not sure what kind of solution you would want to go for, these are just some ideas.

Bug

See above!

To Reproduce

Workaround

None

Workaround Description

No response

Additional Context

No response

Project Impact

None

Blocker Context

No response

Nargo Version

No response

NoirJS Version

No response

Proving Backend Tooling & Version

No response

Would you like to submit a PR for this Issue?

Maybe

Support Needs

No response