Rustで巨大な整数を扱う

0. はじめに

この記事は, Rustその2 Advent Calendar 2019の21日目の記事です。
最近CTFにハマっていて, 巨大な整数を扱う機会がありました。そこで, Rustで用いることができるnum-bigintクレートの中にある「BigInt」の使い方（基本的なところ）をまとめたいと思います。

1. 実行環境

• OS : Windows10 Home
• rustc 1.39.0 (4560ea788 2019-11-04)
• num-bigint = "0.2.3"

2. ディレクトリ構成

今回の実行環境は, 「cargo new bigint --bin」で生成し, 以下のようなディレクトリ構成となります。

bigint/
　┠ src/
　┃  ┗ main.rs
　┗ Cargo.toml

3. 事前準備

3-1. Cargo.tomlの設定

Cargo.toml の[dependencies]に以下を追記します。今回は執筆時の最新バージョンである"0.2.3"を設定していますが, 使用したいバージョンがある場合は適宜変えてください。

Cargo.toml

num-bigint = "0.2.3"

3-2. main.rsの設定

ソースコードに以下を追記します。

main.rs

use num_bigint::BigInt;

4. 基本的な使い方

ここから本題です。

4-1. 定義

基本的に, BigIntは, ある変数に数値の文字列（例："3248238549023850492380"）を入れ, その文字列をパースすることで定義することができます。

main.rs

use num_bigint::BigInt;

fn main() {
    let s = "3248238549023850492380";
    let n: BigInt = s.parse().unwrap();

    println!("{}", n);    // 3248238549023850492380
}

4-2. 四則演算と剰余

BigIntは普通の数値（int32やusizeなど）と同じ感覚で四則演算ができます。また, %を用いて余りを出すこともできます。ただ, BigIntはCopyトレイトを実装していないため, sum = n + n2 のようにやってしまうと, nとn2がmoveしてしまいます。よって, &をつけて計算します。

main.rs

use num_bigint::BigInt;

fn main() {
    let s = "3248238549023850492380";
    let s2 = "3248238549023850492379";
    let n: BigInt = s.parse().unwrap();
    let n2: BigInt = s2.parse().unwrap();

    let add = &n + &n2;
    let suv = &n - &n2;
    let mul = &n * &n2;
    let div = &n / &n2;
    let rem = &n % &n2;

    println!("add: {}", add);  // 6496477098047700984759
    println!("sub: {}", sub);  // 1
    println!("mul: {}", mul);  // 10551053671364569578520014120677744587572020
    println!("div: {}", div);  // 1
    println!("rem: {}", rem);  // 1
}

4-3. 比較

比較も普通の数値と同じ感覚で可能となっています。s1とs2を変えて挙動を確認してみてください。

main.rs

use num_bigint::BigInt;

fn main() {
    let s1 = "100000000000000000000";
    let s2 = "-100000000000000000000";

    let n1: BigInt = s1.parse().unwrap();
    let n2: BigInt = s2.parse().unwrap();

    // n1 > n2 と表示される
    if n1 > n2 {
        println!("n1 > n2");
    } else if n1 < n2 {
        println!("n1 < n2");
    } else if n1 == n2 {
        println!("n1 == n2");
    }
}

5. 使えそうなメソッド

使えそうなメソッドを紹介します。

5.1 sqrt

sqrt()で, 平方根を求めることができます。

main.rs

use num_bigint::BigInt;

fn main() {
    let s = "100000000000000000000";
    let n: BigInt = s.parse().unwrap();

    let n_sqrt = n.sqrt();
    println!("n_sqrt: {}", n_sqrt);  // 10000000000
}

5.2 sign

sign()で, その数値の正負の符号を得ることができます。

main.rs

use num_bigint::BigInt;

fn main() {
    let s1 = "100000000000000000000";
    let s2 = "-100000000000000000000";
    let s3 = "0";

    let n1: BigInt = s1.parse().unwrap();
    let n2: BigInt = s2.parse().unwrap();
    let n3: BigInt = s3.parse().unwrap();

    let n1_sign = n1.sign();
    let n2_sign = n2.sign();
    let n3_sign = n3.sign();

    println!("n1_sign: {:?}", n1_sign);  // Plus
    println!("n2_sign: {:?}", n2_sign);  // Minus
    println!("n3_sign: {:?}", n3_sign);  // NoSign
}