Residue has improper behavior with even moduli

[kayabaNerve]

        const limbs: usize = 256 / Limb::BITS;
        let params: DynResidueParams<limbs> = DynResidueParams::new(&U256::from_u8(10u8));
        for i in 0..10 {
            let x = DynResidue::new(&U256::from_u8(i as u8), params);
            println!("{:?}", x.retrieve());
        }

This should print 0 ..= 9. Instead,

Uint(0x0000000000000000000000000000000000000000000000000000000000000000)
Uint(0x0000000000000000000000000000000000000000000000000000000000000004)
Uint(0x0000000000000000000000000000000000000000000000000000000000000000)
Uint(0x0000000000000000000000000000000000000000000000000000000000000007)
Uint(0x0000000000000000000000000000000000000000000000000000000000000003)
Uint(0x0000000000000000000000000000000000000000000000000000000000000000)
Uint(0x0000000000000000000000000000000000000000000000000000000000000006)
Uint(0x0000000000000000000000000000000000000000000000000000000000000002)
Uint(0x0000000000000000000000000000000000000000000000000000000000000009)
Uint(0x0000000000000000000000000000000000000000000000000000000000000000)

This behavior also exists with the non-dyn form.

https://docs.rs/crypto-bigint/latest/crypto_bigint/macro.impl_modulus.html does not document any bounds on the modulus.
https://docs.rs/crypto-bigint/latest/crypto_bigint/modular/constant_mod/struct.Residue.html does not either.
https://docs.rs/crypto-bigint/latest/crypto_bigint/modular/constant_mod/trait.ResidueParams.html does.
https://docs.rs/crypto-bigint/latest/crypto_bigint/modular/runtime_mod/struct.DynResidue.html does.
https://docs.rs/crypto-bigint/latest/crypto_bigint/modular/runtime_mod/struct.DynResidueParams.html doesn't.

All of these should document all bounds on the moduli. Additionally, DynResidueParams::new should return a Result, or at least panic on an invalid moduli to prevent the above behavior.

[ycscaly]

I also get similarly weird behaviors with DynResidue:

        let n = U4096::from_be_hex("484C557A55331349175DAE95C21B1A5BA199FD4F77B7CCC4F6831805E39A5108268A17D3FACDA968385A69F13F721DBACDE9ACEF613BDDCEBE61E7D6B2DCB3BE6E3CFCA3A7C2FD2C1B6D95965625BADB17225A4C3B5332E3616343F3A781E8ACA832D18B487626BAE4C5CDFF4AE3CD70139D83515CAE7E9C4BEEBA11282B1FB980CCDEBA894F4599F60A19B7D9263B8447802E75C838D3F344E9926003606ACAC7B4F4E988EEC2C8FA59B52EF86E09AE5A30E1B888C863A208787AA217F9B10F0471A0F036C828F623C91E8173926A715792DB1DCDDA55FE1E7D42F0E5EF3D9D0098C60BA170F402AC801DD10CBF020F080E2C2D39FF2245302B830363B35001F2CC4AF614BC696E590CD6754F0D0614E812EEF53CD71AB36C526B38E983597FB5F3BFEB41E165F99951BFFFA0ADAB5665DD47DEA86745F629A703D13096D1E7FE53C6910E0284CFD15DF3F48EB3EC9223518383E24DBC55B4C50D403548FBA9C1390054FF641485F45E3AA783525F55970AEA8B6AEDCD4A3DDA4904D7006AD2A3366354AAB66C16B060A6C93C61290B84990631075439B9FCF8D2ACFAABA66F94B81C376D88672D75FB886BE153AB08348EB33D469FEF931ECB9A4E6D88964452ED4C65EDCB11A38E5DAFFC6618BC534E97B5521A51490F364CF355D61DCD2A459EA5B154AFFF3B2F3A312DFDDE3BDC18EECE81747914DDA668C68463CAF53E");
        let x = U4096::from_be_hex("19BB1B2E0015AA04BEE4F8321819448A2C809DF799C6627668DAA936E3A367CF87BEC43C47551221E40724FE115FF8A4E72D5D46A0E98A934C45CD6904DA0F07499D798EE611497C9493354A9A48C35ECB6318CA55B8322E4295E67F8BC0BE1E0923685E1727B7925920D4F0E9CC30C2A10135DB447EDAD3BCE87C3416252C8B4DF32C24029E0269E7103E80D02DD5A42A99B69A613C6274255DF0599B0DED35A8969463636C6D56D67A05AE11F347A5D5B81896DF5F8A52E6EA7F05359A9FEFC90297BDD298DD77714D3557325DF1C52F42470606ECBFA5E964C0A782AE19CED2E20C73F0438EB597CAE4159B5E5333C97272D8EFEDB49CEB98078E92D990076E6E4101FD97588E4BBAA9DD5D19C671424108EE7FA5F2D74F9F3DEAB4A0AC89CF9833FD9BA1F66719978D7BD13DD2ECDE2BDC9628B1AC1E0A0C44B1408E8869A8B2245DF2A877E01730500AD15466A808E6D9636EEA7A7A0A06568413408E588C52451D189774D84547FBB4171255D6E0BFC9B63C56D582E02FA0F110EEAA2B728E51BC85F529805EBA5E1D6B7323597F1647B0A3DC6D61448C1C062CADE9831DB9E3029322D79D04BB3287B7C5D857AE11802B68921FBC403E390ED693DEAD66E1A728B7F7432408EB2ED9EB9BC3B2BCD8EB2CD44D41A5EBFB32F55BAF47D3AC048F5D1F60B2CB61C0F4E3C178DC7723B8298E9D52771DCF1DABA4088EF74B");
        let x = x % NonZero::new(n).unwrap();

        let ring_params = DynResidueParams::new(&n);
        let x_mod = DynResidue::new(&x, ring_params);
        assert_eq!(x_mod.retrieve(), x);

This code fails... @tarcieri

[ycscaly]

@tarcieri please help here, DynResidue is buggy and we cannot proceed with the development because of that.

[tarcieri]

I'll look at this when I have some time. In the meantime perhaps you could help debug it?

[tarcieri]

cc @fjarri @jellevos

[ycscaly]

I'll look at this when I have some time. In the meantime perhaps you could help debug it?

Of course, what would you like to have me do? I believe the above example is a very minimal reconstruction of this bug. Diving into the montgomery code seems a challenge.

[fjarri]

Technically not a bug in the residues, since they use the Montgomery representation and therefore can only handle odd moduli. But you are right that it should be documented clearly and, possibly, asserted in Params::new().

If that helps, I had a situation where I needed to do some operations with an even moduli, and I RNS-split the numbers into modulo k (odd) and modulo 2^n. The first part was handled by Residues, the second by regular wrapping ops.

[tarcieri]

It seems like DynResidueParams should perhaps have a fallible constructor and return an error or None if the modulus is even, as @kayabaNerve suggested.

Unfortunately that's a breaking change, as it presently has an infallible constructor.

Re: Residue perhaps impl_modulus! could perform the checks at compile-time.

[ycscaly]

Technically not a bug in the residues, since they use the Montgomery representation and therefore can only handle odd moduli. But you are right that it should be documented clearly and, possibly, asserted in Params::new().

If that helps, I had a situation where I needed to do some operations with an even moduli, and I RNS-split the numbers into modulo k (odd) and modulo 2^n. The first part was handled by Residues, the second by regular wrapping ops.

Well those are unfortunate news. But at least it explains this result. I guess I'll have to manage with odd moduli. Thanks.

[jellevos]

By the way, in the special case that the modulus is a power of two (or even better, a power of the limb size), then modular reduction is nothing more than a masking operation. If necessary, we can accommodate those using e.g. a PowerOfTwoResidue (or hopefully something with a better name).

[AaronFeickert]

Perhaps a good starting point is just updating the documentation to make it clear that modulus parity is not checked, and that using an even modulus will quietly result in incorrect arithmetic.

Agreed that macros and constructors should fail somehow on an invalid modulus, as the current behavior (bad arithmetic) is... bad.

I assume that it would be considered a breaking change to have the relevant macros and constructors panic on an invalid modulus, even if the API stays the same?

[tarcieri]

I assume that it would be considered a breaking change to have the relevant macros and constructors panic on an invalid modulus, even if the API stays the same?

I think it would be fine to make impl_modulus! error on an even modulus. That's a bugfix that won't break working code.

To avoid a breaking change on the current DynResidueParams, we could introduce a new fallible method, e.g. new_checked, deprecate the current new in favor of new_checked, and also make new panic if given an even modulus.

Then, in the next breaking release, we can rename new_checked back to new.

[AaronFeickert]

There's now an update in #240 that enforces modulus validity on DynResidueParams in a non-breaking way.

I'm not sure the best way to handle the macros in a way that only uses const functionality, so that's left untouched for now.

[AaronFeickert]

The compile-time case is now handled in #243.