Classical Algorithms for Factorization

This repository contains implementations of classical algorithms for primality testing and integer factorization. It provides Python and C code for various techniques, ranging from basic methods to advanced approaches like the Quadratic Sieve and the General Number Field Sieve (GNFS).

Table of Contents

• Introduction
• Algorithms Implemented
• Code Structure
• References

Introduction

This project provides a comprehensive toolkit for primality testing and integer factorization. Designed for both educational and research purposes, these algorithms showcase various mathematical techniques and optimizations.

Project Overview

This repository was initially created as part of a term paper for the course PHY631: Quantum Computing and Quantum Information, taught by Prof. Arvind at IISER Mohali. It provides a comprehensive collection of classical algorithms for primality testing and integer factorization, including advanced techniques like the Quadratic Sieve and the General Number Field Sieve.

The repository is designed for students, researchers, and enthusiasts in computational mathematics, cryptography, and quantum computing who are interested in understanding and implementing these fundamental algorithms.

Algorithms Implemented

Primality Testing

• Miller-Rabin Primality Test

Factorization Methods

• Trial Division
• Wheel Factorization
• Fermat's Primality Test
• Pollard's Rho Algorithm
• Quadratic Sieve (Python implementation)
• General Number Field Sieve (C implementation)

Code Structure

Classical-Algorithm-for-Factorization/  
├── Continued_Fraction_Algorithm.ipynb        # Implementation of the Continued Fraction Algorithm  
├── Classical_Algorithm_for_Factorization.pdf # PDF of Term Paper 
├──FermatFactorization.ipynb                  # Implementation of Fermat's Factorization  
├── trial_division.ipynb                      # Implementation of Trial Division Algorithm  
├── pollards_rho.ipynb                        # Implementation of Pollard's Rho Algorithm  
├── MillerRabinPrimality.py                   # Miller-Rabin Primality Test Implementation
├──wheel_factorization.py                     # Implementation of Wheel Factorization Algorithm  
├── prime.json                                # JSON file containing precomputed primes for optimization  
├── Manage_Primes.py                          # Utility script for managing prime numbers  
└── __pycache__/                              # Python bytecode cache directory

References

1. Wheel Factorization - Wikipedia Article:
   https://en.m.wikipedia.org/wiki/Wheel_factorization

2. Pollard's Rho Algorithm - Wikipedia Article:
   https://en.m.wikipedia.org/wiki/Pollard%27s_rho_algorithm

3. Quadratic Sieve Algorithm Implementation - GitHub Repository by NachiketUN:
   https://github.com/NachiketUN/Quadratic-Sieve-Algorithm

4. General Number Field Sieve Implementation - GitHub Repository by MathSquared:
   https://github.com/MathSquared/general-number-field-sieve

5. Primality Testing & Factorization - YouTube Playlist:
   https://youtube.com/playlist?list=PLLtQL9wSL16gTZ-OjCJNHe8E6GWPWpvRi