Skip to content

Instantly share code, notes, and snippets.

@casweeney
Created February 26, 2024 13:55
Show Gist options
  • Save casweeney/1dcbbea879b30346920fcf88465c7df0 to your computer and use it in GitHub Desktop.
Save casweeney/1dcbbea879b30346920fcf88465c7df0 to your computer and use it in GitHub Desktop.
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