daa_1.py

# -*- coding: utf-8 -*-
"""daa (1).ipynb

Automatically generated by Colab.

Original file is located at
    https://colab.research.google.com/drive/10toQtNfntSRwGiMEoOF1URacP_98kfEY
"""

# pip install sympy matplotlib

# ==============================================
#  Cryptographic Prime Project - Member 2
#  Algorithm Comparison (Miller–Rabin vs AKS)
#  Developed by: Ayesha Siddiqui (Member 2)
# ==============================================

import random
import time
import matplotlib.pyplot as plt
from math import gcd, isqrt
from sympy import isprime

# -------------------------------------------------
# Function 1: Miller-Rabin Primality Test
# -------------------------------------------------
def miller_rabin_test(n, k=5):
    """Miller-Rabin probabilistic primality test."""
    if n <= 1 or n == 4:
        return False
    if n <= 3:
        return True

    # Step 1: Write n-1 as 2^r * d
    d = n - 1
    r = 0
    while d % 2 == 0:
        d //= 2
        r += 1

    # Step 2: Test k rounds
    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, d, n)

        if x == 1 or x == n - 1:
            continue

        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True


# -------------------------------------------------
# Function 2: AKS Algorithm (simplified deterministic version)
# -------------------------------------------------
def aks_test(n):
    """Simplified AKS primality test using sympy for deterministic checking."""
    if n <= 1:
        return False
    if n <= 3:
        return True

    # Step 1: Check if n is a perfect power
    for b in range(2, isqrt(n) + 1):
        a = round(n ** (1 / b))
        if a ** b == n:
            return False

    # Step 2: Deterministic prime check
    return isprime(n)


# -------------------------------------------------
# Function 3: Compare both algorithms (only for prime numbers)
# -------------------------------------------------
def compare_algorithms(n):
    """Compares Miller-Rabin and AKS algorithms for a given number."""
    print("\n==============================")
    print(f"🔹 Comparing Algorithms for n = {n}")
    print("==============================")

    # Check if the number is prime first
    if not isprime(n):
        print(f"\n⚠️ {n} is NOT a prime number. Comparison skipped.")
        print("Please enter a prime number for comparison.")
        return None, None

    # Miller–Rabin
    start = time.perf_counter()
    result_mr = miller_rabin_test(n)
    time_mr = time.perf_counter() - start

    # AKS
    start = time.perf_counter()
    result_aks = aks_test(n)
    time_aks = time.perf_counter() - start

    # Show Results
    print(f"\nMiller–Rabin Result : {'Prime' if result_mr else 'Composite'}")
    print(f"Miller–Rabin Time   : {time_mr:.6f} seconds")

    print(f"\nAKS Result          : {'Prime' if result_aks else 'Composite'}")
    print(f"AKS Time            : {time_aks:.6f} seconds")

    # Compare Table
    print("\n🔸 COMPARISON REPORT 🔸")
    print("------------------------------------------")
    print(f"{'Algorithm':<15}{'Result':<15}{'Time (s)':<10}")
    print("------------------------------------------")
    print(f"{'Miller–Rabin':<15}{str(result_mr):<15}{time_mr:<10.6f}")
    print(f"{'AKS':<15}{str(result_aks):<15}{time_aks:<10.6f}")
    print("------------------------------------------")

    return time_mr, time_aks


# -------------------------------------------------
# Function 4: Visualize Comparison
# -------------------------------------------------
def show_graph(n, time_mr, time_aks):
    """Displays a bar graph comparing execution times."""
    algorithms = ['Miller–Rabin', 'AKS']
    times = [time_mr, time_aks]

    plt.bar(algorithms, times, color=['skyblue', 'lightcoral'])
    plt.ylabel('Execution Time (seconds)')
    plt.title(f'Prime Test Comparison for n = {n}')
    plt.show()


# -------------------------------------------------
# Main Program Execution
# -------------------------------------------------
if __name__ == "__main__":
    print("=== Prime Testing Algorithm Comparison ===")
    print("This compares Miller–Rabin and AKS algorithms.\n")

    try:
        n = int(input("Enter a number to test (e.g., 37, 97, 221): "))

        time_mr, time_aks = compare_algorithms(n)

        # Show graph only if number was prime
        if time_mr is not None and time_aks is not None:
            show_graph(n, time_mr, time_aks)

    except ValueError:
        print("❌ Please enter a valid integer!")