main.rs

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);
    }
}