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.
- seems num-bigint does not have single function implementing
( ( a ^ b ) % c ) optimally
- 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
Is it possible to solve these problems within this module? If not, please advise another module?
Please check out the
Thank you, Alice. Seems there is no way to do it zero-copy with
num. That's pity.
Modulo::pow method uses not zero allocations, but a small, constant number of allocations.
Is it possible to reuse vector of bytes?
Not directly. You have to convert using
UBig::from_be_bytes, and then to
Modulo in an appropriate
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.
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.
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.