Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Documentation of modular multiplication #287

Closed
matthiasgeihs opened this issue Nov 10, 2023 · 9 comments
Closed

Documentation of modular multiplication #287

matthiasgeihs opened this issue Nov 10, 2023 · 9 comments

Comments

@matthiasgeihs
Copy link

matthiasgeihs commented Nov 10, 2023

This relates to #150 and #283.

In the discussion of #150 it is mentioned that modular multiplication is possible via Residue.

However, I did not find an example that shows how Residue is used correctly and it also wasn't immediately apparent to me.

After a bit of searching, I found the macro const_residue, which seems to allow the creation of a Residue object.

/// Creates a `Residue` with the given value for a specific modulus.
/// For example, `residue!(U256::from(105u64), MyModulus);` creates a `Residue` for 105 mod `MyModulus`.
/// The modulus _must_ be odd, or this will panic.
macro_rules! const_residue {

However, there are several issues with the example residue!(U256::from(105u64), MyModulus);:

  1. The macro is called const_residue (and not residue).
  2. Usage of U256::from(105u64) is not a valid argument to the macro. (no rules expected the token `::`)
  3. MyModulus needs to be defined before, which is not evident by the example itself.

Because of these things, it cost me a bit of time to get modular multiplication working. For reference, this is a minimal working example:

use crypto_bigint::{const_residue, impl_modulus, modular::constant_mod::ResidueParams, U256};

impl_modulus!(
    F11,
    U256,
    "000000000000000000000000000000000000000000000000000000000000000B"
);

fn mul_mod(a: U256, b: U256) -> U256 {
    let a = const_residue!(a, F11);
    let b = const_residue!(b, F11);
    a.mul(&b).retrieve()
}

fn main() {
    let a = U256::from(3u8);
    let b = U256::from(4u8);
    let c = mul_mod(a, b);
    println!("{a} * {b} % {} = {c}", F11::MODULUS);
}

I think it would be nice if a more explicit (and correct) example would be included in the documentation.

@tarcieri
Copy link
Member

#313 provides a simpler API for dynamic moduli (via the MulMod trait)

@Dustin-Ray
Copy link
Contributor

Dustin-Ray commented Jan 12, 2024

Where does this currently stand? If we were to produce docs on this, where should they live? powmod is another area that might need attention as well.

@tarcieri
Copy link
Member

We could use some more examples in the toplevel documentation of the modular module: https://docs.rs/crypto-bigint/0.6.0-pre.10/crypto_bigint/modular/index.html

@Dustin-Ray
Copy link
Contributor

Dustin-Ray commented Jan 12, 2024

is the approach taken above by @matthiasgeihs sufficient in this case for mul mod or is there something more optimal. I do see that #313 is merged but its still unclear what method remains preferred.

@tarcieri
Copy link
Member

That sort of example seems fine if you'd like to add it to the rustdoc, although the macro names will need to be updated, e.g. to const_monty_form!

@Dustin-Ray
Copy link
Contributor

See #562. Realizing that in ~v0.6, mul_mod is quite easily and naturally accessed. Accessing mod_pow-like functionality was observed to be somewhat elusive, so 562 attempts to highlight the modular module to a degree

@tarcieri
Copy link
Member

Accessing mod_pow-like functionality was observed to be somewhat elusive

How so?

@Dustin-Ray
Copy link
Contributor

Accessing mod_pow-like functionality was observed to be somewhat elusive

How so?

Had to dig around through the unit tests to see how it was being used. In the most recent version though it was really nice and seamless, very easy to use

@matthiasgeihs
Copy link
Author

Feel free to close this issue if you think it is solved. Haven’t had time to look into this recently.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants