search

AaronKutch / awint

Arbitrary width integers
Other
10 stars 0 forks source link

Modular exponentiation #38

Open maurges opened 2 weeks ago

maurges commented 2 weeks ago

Does it not exist in these crates or could I not find it? If it doesn't exist, it would be really nice to have.

Same for modular inverse, and for generating random numbers (and random numbers modulo some other number), and generating primes.

Thanks!

AaronKutch commented 2 weeks ago

Generating random strings of bits is currently supported under "rand_support", but I don't have a function for random modulo an arbitrary number. I have not implemented modular exponentiation or inverse before. I'm pretty busy right now but might find the time this weekend to implement it, how interested are you in seeing it implemented? Is this for constrained systems, or for high performance, or what purposes do you need it for? I see a possible way to make pow_mod no-alloc for instance (you would pass in an array of scratchpads with a length equal to the bitwidth of the exponent), but the modular inverse I would have to study more. Currently it looks like the allocated signatures would look like

/// All unsigned, arbitrary bitwidths
pow_mod(&self, exp: &Bits, umod: &Bits) -> Option<Awi or ExtAwi>

/// All unsigned, arbitrary bitwidths
inv(&self, umod: &Bits) -> Option<Awi or ExtAwi>
maurges commented 2 weeks ago

Don't feel pressured to implement this because of me, if I really needed it I'd make a patch myself. (-: My own use case is high performance multi-party protocols, not constrained systems.

You can do exponentiation by squaring without additional memory with something like pow_mod(base: Bits, exp: Bits, umod: &Bits, result: &mut Bits) - base and exp are modified in place in the algorithm.

For modular inverse I don't know of any algorithms without allocations, for a simple extended euclid you would need to destroy both arguments and have two additional numbers allocated.