BoxedResidue square error

[xuganyu96]

BoxedResidue::square() sometimes produces BoxedResidue whose montgomery_form is greater than its modulus, which will break BoxedResidue::add and BoxedResidue::sub.

Here is some code to reproduce the error:

use crypto_bigint::{
    modular::{BoxedResidue, BoxedResidueParams, DynResidue, DynResidueParams},
    BoxedUint, U128
};

fn main() {
    let residue = 0x20u128;
    let modulus = 0xB44677037A7DBDE04814256570DCBD8Du128;

    let boxed_modulus = BoxedUint::from(modulus);
    let boxed_params = BoxedResidueParams::new(boxed_modulus).unwrap();
    let boxed_residue = BoxedResidue::new(BoxedUint::from(residue), boxed_params);
    let boxed_square = boxed_residue.square();


    let dyn_modulus = U128::from_u128(modulus);
    let dyn_params = DynResidueParams::new(&dyn_modulus).unwrap();
    let dyn_residue = DynResidue::new(&U128::from_u128(residue), dyn_params);
    let dyn_square = dyn_residue.square();
    
    assert!(boxed_residue.as_montgomery().as_limbs() == dyn_residue.as_montgomery().as_limbs());
    assert!(boxed_square.as_montgomery() > boxed_square.params().modulus()); // this should not happen
    assert!(dyn_square.as_montgomery() <= dyn_square.params().modulus());
}

[fjarri]

Looks like boxed_square.as_montgomery() == dyn_square.as_montgomery() + modulus, that is the Boxed algorithm produces a correct, but non-reduced result. I think that is intentional, since it uses the almost-Montgomery-multiplication algorithm. It'll have an advantage during exponentiation, but the value has to be normalized when returned to the user. So basically we need to have "unnormalized" and "normalized" methods of MontgomeryMultiplier.

I looked through the paper, and it claims that (in Section 4):

Remark 1. If we assume 2^(n-1) < m < 2^n, then the output (X) of AMM can be fully reduced modulo m by a single (conditional) subtraction of m

I ran some tests and it seems that it is true for any modulus. @tarcieri, any comments? Also, should we use the same algorithm for Uint, so that it could make use of the same exponentiation speedup?

[tarcieri]

Yeah, I've been worried about this. num-bigint unconditionally applies an extra reduction here when computing modpow:

https://github.com/rust-num/num-bigint/blob/2cea7f4/src/biguint/monty.rs#L207-L221

It also mentions golang/go#13907 which notes AMM reduces to the bit length but not the modulus.

For the general purpose BoxedResidue API (outside of modpow use cases) we'll need to check if adding this additional reduction harms performance enough that we should just use standard Montgomery multiplication, especially if we can land Karatsuba for the actual multiplication part. Modpow can defer that final reduction since everything is happening inside a function implemented in crypto-bigint itself, but since we provide direct access to Montgomery form in the public API we can't do that for the *Residue types which precludes deferring the final reduction to when the result is translated out of Montgomery form.

(Also for squarings in particular I need to revisit #383)

Also, should we use the same algorithm for Uint, so that it could make use of the same exponentiation speedup?

Possibly for modpow, though we'll need to investigate whether AMM actually makes sense for multiply/square in the public API performance-wise.

It's something I haven't prioritized for a few reasons, namely we'd like to investigate ASM optimizations for it which would clash with the const fn implementation in the non-boxed *Residue types (we'll still need a pure Rust fallback, but it's hard to share code without const_mut_refs), and the other residues implement multi-exponentiation which makes porting the implementation over a little less straightforward.

[tarcieri]

#442 fixes this by using full Montgomery reductions for BoxedResidue::{mul, square}, and only using AMM internally to implement modpow.

Additionally modpow needs to add a final modular reduction similar to num-bigint, but I have left that for a followup PR.

[tarcieri]

#443 is the fix for modpow