Rust大整数计算库bigint的使用指南

简介

bigint是Rust中一个用于高精度大整数运算的库，它提供了超出原生整数类型范围的数值计算能力。当需要处理非常大的整数(如密码学、科学计算等领域)时，bigint是一个理想的选择。

安装

在Cargo.toml中添加依赖：

[dependencies]
num-bigint = "0.4"

基本用法

创建大整数

use num_bigint::{BigInt, BigUint};
use num_traits::{Zero, One};

fn main() {
    // 创建有符号大整数
    let a: BigInt = BigInt::from(1234567890);
    let b = "-9876543210".parse::<BigInt>().unwrap();
    
    // 创建无符号大整数
    let c: BigUint = BigUint::from(1234567890u32);
    let d = "9876543210".parse::<BigUint>().unwrap();
    
    // 使用零和一常量
    let zero = BigInt::zero();
    let one = BigInt::one();
}

基本运算

use num_bigint::BigInt;

fn main() {
    let a = BigInt::from(123456);
    let b = BigInt::from(789012);
    
    // 加法
    let sum = &a + &b;
    println!("{} + {} = {}", a, b, sum);
    
    // 减法
    let diff = &a - &b;
    println!("{} - {} = {}", a, b, diff);
    
    // 乘法
    let product = &a * &b;
    println!("{} * {} = {}", a, b, product);
    
    // 除法
    let quotient = &b / &a;
    println!("{} / {} = {}", b, a, quotient);
    
    // 取模
    let remainder = &b % &a;
    println!("{} % {} = {}", b, a, remainder);
}

幂运算

use num_bigint::BigInt;
use num_traits::pow;

fn main() {
    let base = BigInt::from(2);
    let exponent = 100;
    
    let result = pow(base, exponent);
    println!("2^100 = {}", result);
}

比较运算

use num_bigint::BigInt;

fn main() {
    let a = BigInt::from(123456789);
    let b = BigInt::from(987654321);
    
    println!("a == b: {}", a == b);
    println!("a < b: {}", a < b);
    println!("a > b: {}", a > b);
}

位运算

use num_bigint::BigInt;

fn main() {
    let a = BigInt::from(0b1100);
    let b = BigInt::from(0b1010);
    
    println!("AND: {:b}", &a & &b);  // 1000
    println!("OR: {:b}", &a | &b);   // 1110
    println!("XOR: {:b}", &a ^ &b);  // 0110
    println!("NOT a: {:b}", !&a);    // ...11111111111111111111111111110011
}

转换到原生整数

use num_bigint::BigInt;

fn main() {
    let big_num = BigInt::from(1234567890);
    
    // 尝试转换为i32
    match big_num.to_i32() {
        Some(n) => println!("转换为i32: {}", n),
        None => println!("数值太大，无法转换为i32"),
    }
}

高级用法

随机数生成

use num_bigint::{BigInt, RandBigInt};
use rand::thread_rng;

fn main() {
    let mut rng = thread_rng();
    
    // 生成0到100之间的随机大整数
    let a = rng.gen_bigint_range(&BigInt::from(0), &BigInt::from(100));
    println!("随机数: {}", a);
    
    // 生成128位随机大整数
    let b: BigInt = rng.gen_bigint(128);
    println!("128位随机数: {}", b);
}

质数测试

use num_bigint::BigInt;
use num_integer::Integer;
use num_traits::{One, Zero};

fn is_prime(n: &BigInt) -> bool {
    if n <= &BigInt::one() {
        return false;
    }
    
    let two = BigInt::from(2);
    if n.is_multiple_of(&two) {
        return n == &two;
    }
    
    let mut d = n - &BigInt::one();
    let mut s = 0;
    
    while d.is_multiple_of(&two) {
        d /= &two;
        s += 1;
    }
    
    // 这里简化了，实际应用中应该使用更可靠的测试
    for _ in 0..5 {
        let a = BigInt::from(2);
        let mut x = a.modpow(&d, n);
        
        if x == BigInt::one() || x == n - &BigInt::one() {
            continue;
        }
        
        for _ in 0..s - 1 {
            x = x.modpow(&two, n);
            if x == n - &BigInt::one() {
                break;
            }
        }
        
        if x != n - &BigInt::one() {
            return false;
        }
    }
    
    true
}

fn main() {
    let num = BigInt::from(7919);  // 一个大质数
    println!("{}是质数吗? {}", num, is_prime(&num));
}

性能提示

1. 尽量重用已分配的BigInt而不是频繁创建新实例
2. 对于循环中的操作，考虑使用+=等操作符而不是每次都创建新对象
3. 如果知道数值范围，可以先使用原生整数类型，必要时再转换为大整数

bigint库为Rust提供了强大的大整数计算能力，适用于各种需要高精度整数运算的场景。

完整示例

// 完整的大整数计算示例
use num_bigint::{BigInt, BigUint, RandBigInt};
use num_traits::{Zero, One, pow, FromPrimitive};
use rand::thread_rng;

fn main() {
    // 1. 创建大整数
    let a = BigInt::from(12345678901234567890_i64);
    let b = BigInt::from(-9876543210987654321_i64);
    let c = BigUint::from(1234567890u32);
    
    println!("创建的大整数:");
    println!("a = {}", a);
    println!("b = {}", b);
    println!("c = {}", c);
    
    // 2. 基本运算
    let sum = &a + &b;
    let diff = &a - &b;
    let product = &a * &b;
    
    println!("\n基本运算结果:");
    println!("a + b = {}", sum);
    println!("a - b = {}", diff);
    println!("a * b = {}", product);
    
    // 3. 幂运算
    let base = BigInt::from(3);
    let exponent = 50;
    let power = pow(base, exponent);
    println!("\n幂运算结果:");
    println!("3^50 = {}", power);
    
    // 4. 随机数生成
    let mut rng = thread_rng();
    let rand_num = rng.gen_bigint(256);
    println!("\n随机数生成:");
    println!("256位随机数: {}", rand_num);
    
    // 5. 质数测试
    let prime_candidate = BigInt::from(104729); // 第10000个质数
    println!("\n质数测试:");
    println!("{}是质数吗? {}", prime_candidate, is_prime(&prime_candidate));
}

// 质数测试函数
fn is_prime(n: &BigInt) -> bool {
    if n <= &BigInt::one() {
        return false;
    }
    
    let two = BigInt::from(2);
    if n.is_multiple_of(&two) {
        return n == &two;
    }
    
    let mut d = n - &BigInt::one();
    let mut s = 0;
    
    while d.is_multiple_of(&two) {
        d /= &two;
        s += 1;
    }
    
    for _ in 0..5 {
        let a = BigInt::from(2);
        let mut x = a.modpow(&d, n);
        
        if x == BigInt::one() || x == n - &BigInt::one() {
            continue;
        }
        
        for _ in 0..s - 1 {
            x = x.modpow(&two, n);
            if x == n - &BigInt::one() {
                break;
            }
        }
        
        if x != n - &BigInt::one() {
            return false;
        }
    }
    
    true
}

这个完整示例展示了bigint库的主要功能，包括：

1. 创建大整数
2. 基本算术运算
3. 幂运算
4. 随机数生成
5. 质数测试

你可以根据需要扩展这个示例，添加更多功能如位运算、与其他数值类型的转换等。