# Optimal implementation of cryptographic function of exponentiation by modulus

I try to use the num-bigint module to implement such a formula ( ( a ^ b ) % c ), where a, b and c are integers of an arbitrary length and `^` the operation of exponentiation, and `%` the operation of finding the reminder. But I faced two problems.

1. seems num-bigint does not have single function implementing `( ( a ^ b ) % c )` optimally
2. num-bigint is not zero-copy. To make an instance of `BigUint` you need to make a copy of the original data `Vec <u8>`, and then copy the result again from `BigUint` to `Vec <u8>`.

Is it possible to solve these problems within this module? If not, please advise another module?

Please check out the `modpow` method.

2 Likes

Thank you, Alice. Seems there is no way to do it zero-copy with `num`. That's pity.

Try ibig::modular.

The `Modulo::pow` method uses not zero allocations, but a small, constant number of allocations.

1 Like

Is it possible to reuse vector of bytes?

Not directly. You have to convert using `UBig::from_le_bytes` or `UBig::from_be_bytes`, and then to `Modulo` in an appropriate `ModuloRing`.

If your goal is to do this completely without using any additional memory then it's going to be very hard or impossible. Modular exponentiation requires some scratch memory space.

For large exponents, the performance cost of these conversions is going to be negligible compared to the actual modular exponentiation. `ibig::modular` does the actual exponentiaion in place once all the memory is allocated. I think `num-bigint` will perform a lot of additional allocations as part of the exponentiation algorithm.

1 Like

I see. Thank you On practice it might. In theory not that hard. If data is little-ended then and it is aligned with usize then it's enough to reinterpret original buffer without copying it. Anyway `num` currently does not comply Rust's: "Fast, Reliable, Productive . Pick Three ".

Even if you wrote an exponentiation function that could reuse `Vec`'s memory for the input and output numbers, it would still have to allocate some scratch memory for intermediate values while calculating.

Also, exponentiation is a pretty expensive operation. Copying the input is a very cheap operation compared to this.

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.