フェルマーテスト

fermat.rs

use rug::{ops::Pow, Assign, Integer};

fn fermat_test(target: u32, base: u32) -> bool {
    let n = target;

    let mut a = Integer::new();
    a.assign(base);

    // 合成数であることを正とする
    if a.pow(n - 1) % n != 1 {
        return true;
    }
    return false;
}

fn gcd(a: u32, b: u32) -> u32 {
    if a == 0 {
        return b;
    } else {
        return gcd(b % a, a);
    }
}

fn main() {
    let args: Vec<String> = std::env::args().collect();

    let target_str = &args[1];
    let target = target_str.parse().unwrap();
    let base_str = &args[2];
    let base = base_str.parse().unwrap();

    // 引数同士が互いに素であることをチェック
    if gcd(target, base) != 1 {
        println!("[a = {}] and [n = {}] must be coprime", base, target);
        return;
    }

    if fermat_test(target, base) {
        println!("[a = {}] {} is composite number", base, target);
    } else {
        println!("[a = {}] {} is probably prime number", base, target);
    }
}

#[test]
fn fermat_test_test() {
    assert_eq!(fermat_test(11, 2), false);
    assert_eq!(fermat_test(423, 2), true);
    assert_eq!(fermat_test(763, 2), true);
    assert_eq!(fermat_test(1993, 3), false);
}