rust 如何计算两个BigInts/BigUint的幂?

lzfw57am  于 2023-01-09  发布在  其他
关注(0)|答案(2)|浏览(169)

标题说明了一切。我试图在Rust文档中找到一些东西,但我唯一遇到的是BigInt/Biguint结构体的这个函数。

pub fn modpow(&self, exponent: &Self, modulus: &Self) -> Self

我也在num::pow中找到了这个函数,但它对我没有帮助,因为我的exp也是BigInt/BigUint。

pub fn pow<T>(base: T, exp: usize) -> T

大家有什么想法吗,我想我应该用modpow函数,但是我应该给modulus参数发送什么呢?

t9aqgxwy

t9aqgxwy1#

您可以将指数转换为usize,然后调用BigUint::pow()。如果指数大于usize::MAX,您将无法计算幂。例如:

use num_bigint::BigUint;
use std::convert::TryInto;

fn pow(n: BigUint, exp: BigUint) -> BigUint {
    n.pow(exp.try_into().expect("exponent too large for pow()"))
}

Playground

drnojrws

drnojrws2#

试试我的big_pow函数注意:一个非常大的计算可能需要很长的时间,但是理论上它们应该有足够的时间循环执行。我还没有遇到任何内存分配失败,但是也没有进行非常彻底的测试。

use num_bigint::BigInt;
use num_traits::{cast::FromPrimitive};
fn big_pow(base: BigInt, exp: BigInt) -> BigInt
{
    if exp == BigInt::from_u32(0).unwrap()
    {
        return BigInt::from_u32(1).unwrap();
    }
    let mut answer = base.clone();
    let mut i = BigInt::from_u32(1).unwrap();
    while i < exp
    {
        i = i + BigInt::from_u32(1).unwrap();
        answer = answer * base.clone();
    }
    return answer;
}

如果需要使用模数:

use modexp::modexp;
use num_bigint::BigInt;
use num_traits::{cast::FromPrimitive};
pub fn modexp_fast_internal_copy(mut b: BigInt, mut e: BigInt, m: BigInt) -> BigInt
{
    let mut result = BigInt::from_u64(1).unwrap();
    let big1 = BigInt::from_u64(1).unwrap();
    let big2 = BigInt::from_u64(2).unwrap();
    while e > BigInt::from_u64(0).unwrap()
    {
        if e.clone() % big2.clone() == big1
        {
            result = (result.clone() * b.clone()) % m.clone();
        }
        b = (b.clone() * b.clone()) % m.clone();
        e = e.clone() / 2.clone();
    }
    result % m
}

我修改了这个原始源代码的第二个函数:https://docs.rs/crate/modexp/0.2.2/source/src/lib.rs

相关问题