PollardsRho_Algorithm.py

from math import gcd, sqrt
from statistics import variance
import random
import pandas as pd


def miller_rabin(n, k = 40):
    """
    Miller-Rabin primality test implementation as taught in class.
    If n is prime, it will always return True. If n is composite, it will return False with a probability 
    of at least 1 - (1/4)^k, where k is the number of iterations.
    """
    a = random.randint(2, n - 1)

    if pow(a, n - 1, n) != 1:
        return False
    
    else:
        pwr = (n - 1)//2
        while k > 0:
            if pow(a, pwr, n) != 1 and pow(a, pwr, n) != n - 1:
                return False
            elif pow(a, pwr, n) == n - 1 or pwr % 2 == 1:
                return True
            else:
                pwr //= 2
                k -= 1


def get_prime():
    """
    Generate a random prime number between 10^9 and 10^10 using the Miller-Rabin primality test.
    """
    n = random.randint(pow(10, 9), pow(10, 10))
    while not miller_rabin(n):
        n = random.randint(pow(10, 9), pow(10, 10))
    return n

def get_p_q():
    """
    Generate two distinct prime numbers p and q.
    """
    p = get_prime()
    q = get_prime()
    while p == q:
        q = get_prime()
    return p, q

def f(x, i, n):
    """
    Pseudo-random function f(x) = (x^2 + i) mod n as specified in the assignment.
    """
    return (x**2 + i) % n

def traverse(x, y, n, val):
    """
    Traverse the sequence using the function f(x) and return the new values of x and y.
    """
    x = f(x, val, n)
    y = f(f(y, val, n), val, n)
    return x, y

def is_partial_collision(g, n):
    """
    Check if the factor g is a partial collision (not 1 or n).
    """
    return g != 1 and g != n

def is_full_collision(g, n):
    """
    Check if the factor g is a full collision (equals n).
    """
    return g == n
    

def algo(n, val):
    """
    The main algorithm that detects collisions using the function f(x) and the GCD.
    It returns a dictionary with the outcome, number of iterations, and the factor found (if any).
    """

    # Initialize x and y to the same random starting value in the range [1, n]
    x = y = random.randint(1, n)
    i = 0
    # Calculate Np - the expectency of the number of iterations needed to find a collision, which is n^(1/4)
    n_p = pow(n, 0.25)

    # Main loop to traverse the sequence
    while i < 100*n_p:
        x, y = traverse(x, y, n, val)
        g = gcd(abs(y - x), n)
        i += 1

        if is_partial_collision(g, n):
            return {"outcome": "partial", "iterations": i, "factor": g}
        
        elif is_full_collision(g, n):
            return {"outcome": "full", "iterations": i, "factor": None}

    return {"outcome": "none", "iterations": i, "factor": None}



def run_algorithm(n, p, q, test_num):
    """
    Run the collision detection algorithm for 50 random values of val in the range [1, n-1].
    It returns a list of dictionaries containing the results for each run.
    """

    # Keep track of used values to avoid duplicates
    used_vals = set()
    # List to store the results of each run
    rows = []

    for _ in range(50):
        val = random.randint(1, n-1)
        while val in used_vals:
            val = random.randint(1, n-1)

        used_vals.add(val)
        res = algo(n, val)

        rows.append({
            "test": test_num,
            "n": n,
            "p": p,
            "q": q,
            "val": val,
            **res,
        })

    return rows


def summarize(df, label):
    """
    Summarize the results of the collision detection algorithm.
    It prints the counts of partial, full, and no collisions, as well as 
    the variance of iterations for partial collisions.
    """
    counts = df["outcome"].value_counts()
    partial = counts.get("partial", 0)
    full = counts.get("full", 0)
    none = counts.get("none", 0)
 
    partial_iters = df.loc[df["outcome"] == "partial", "iterations"]
    var = partial_iters.var() if len(partial_iters) > 1 else 0.0
 
    print(f"{label}\n"
          f"    * Partial collisions: {partial}\n"
          f"    * Full collisions: {full}\n"
          f"    * No collisions: {none}\n"
          f"    * Iteration variance for partial collisions: {var:.3f}\n"
          f"{'-' * 50}")


def main():
    """
    Main function to run the collision detection algorithm for 10 tests with random prime numbers p and q.
    It summarizes the results after each test and saves the overall results to a CSV file.
    """
    # List to store all results across tests
    all_rows = []

    for test_num in range(1, 11):
        p, q = get_p_q()
        n = p * q
        print(f"{"-"*50}\n\n"
              f"Test {test_num} - Testing with n = {n} (p = {p}, q = {q}):\n")

        rows = run_algorithm(n, p, q, test_num)
        all_rows.extend(rows)
        summarize(pd.DataFrame(rows), f"\nTest {test_num} — n = {n} (p = {p}, q = {q}):")
 
    df = pd.DataFrame(all_rows)
    summarize(df, "\nTotal results after 10 tests:")
 
    # שמירה לקובץ לשימוש מאוחר יותר (גרפים וכו')
    df.to_csv("results.csv", index=False)
 
    return df

if __name__ == "__main__":
    df = main()