Created
February 26, 2024 13:55
-
-
Save casweeney/1dcbbea879b30346920fcf88465c7df0 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
use std::collections::HashSet; | |
use rand::Rng; | |
fn power_set(set: &Vec<i32>) -> Vec<Vec<i32>> { | |
let mut result = Vec::new(); | |
let size = set.len(); | |
let no_of_subsets = 1 << size; | |
for i in 0..no_of_subsets { | |
let mut subset = Vec::new(); | |
for j in 0..size { | |
if (i & (1 << j)) != 0 { | |
subset.push(set[j]); | |
} | |
} | |
result.push(subset); | |
} | |
result | |
} | |
fn power_modulo(mut base: u64, mut exponent: u64, modulus: u64) -> u64 { | |
let mut result = 1; | |
base %= modulus; | |
while exponent > 0 { | |
if exponent % 2 == 1 { | |
result = (result * base) % modulus; | |
} | |
exponent >>= 1; | |
base = (base * base) % modulus; | |
} | |
result | |
} | |
fn miller_rabin_test(n: u64, k: u64) -> bool { | |
if n == 2 || n == 3 { | |
return true; | |
} | |
if n % 2 == 0 { | |
return false; | |
} | |
let mut d = n - 1; | |
while d % 2 == 0 { | |
d >>= 1; | |
} | |
let mut range = rand::thread_rng(); | |
for _ in 0..k { | |
let a = range.gen_range(2..n - 2); | |
let mut x = power_modulo(a, d, n); | |
if x == 1 || x == n - 1 { | |
continue; | |
} | |
let mut prime = false; | |
for _ in 0..((n as f64).log2() as u64 - 1) { | |
x = (x * x) % n; | |
if x == n - 1 { | |
prime = true; | |
break; | |
} | |
} | |
if !prime { | |
return false; | |
} | |
} | |
true | |
} | |
fn main() { | |
let set = vec![1, 2, 3]; | |
let result = power_set(&set); | |
println!("Input set: {:?}", set); | |
println!("Power set: {:?}", result); | |
//Miller Rabin | |
let test_num = 53; | |
let num_iterations = 5; | |
if miller_rabin_test(test_num, num_iterations) { | |
println!("{} is probably prime.", test_num); | |
} else { | |
println!("{} is composite.", test_num); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment