Metadata-Version: 2.4
Name: number-theory-primes
Version: 0.1.2
Summary: Advanced primality testing algorithms including AKS
Home-page: https://github.com/VaidhyaMegha/primes
Author: Madhulatha Mandarapu, Sandeep Kunkunuru
Author-email: madhulatha@vaidhyamegha.com, sandeep.kunkunuru@gmail.com
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Developers
Classifier: Intended Audience :: Science/Research
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.8
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Topic :: Scientific/Engineering :: Mathematics
Classifier: Topic :: Software Development :: Libraries :: Python Modules
Requires-Python: >=3.8
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy>=1.20.0
Requires-Dist: sympy>=1.8
Provides-Extra: dev
Requires-Dist: pytest>=6.0; extra == "dev"
Requires-Dist: pytest-cov>=2.0; extra == "dev"
Requires-Dist: black>=21.0; extra == "dev"
Requires-Dist: flake8>=3.8; extra == "dev"
Requires-Dist: mypy>=0.800; extra == "dev"
Provides-Extra: docs
Requires-Dist: sphinx>=4.0; extra == "docs"
Requires-Dist: sphinx-rtd-theme>=0.5; extra == "docs"
Provides-Extra: benchmarks
Requires-Dist: matplotlib>=3.3; extra == "benchmarks"
Requires-Dist: seaborn>=0.11; extra == "benchmarks"
Requires-Dist: pandas>=1.3; extra == "benchmarks"
Dynamic: author
Dynamic: author-email
Dynamic: classifier
Dynamic: description
Dynamic: description-content-type
Dynamic: home-page
Dynamic: license-file
Dynamic: provides-extra
Dynamic: requires-dist
Dynamic: requires-python
Dynamic: summary

# Primes - Advanced Primality Testing Algorithms

A Python library implementing state-of-the-art primality testing algorithms, starting with the AKS (Agrawal-Kayal-Saxena) primality test.

## Overview

This repository contains implementations of various primality testing algorithms with a focus on theoretical significance and practical applications. The AKS primality test is the first deterministic polynomial-time algorithm for testing primality.

## Features

- **AKS Primality Test**: First deterministic polynomial-time primality test
- **Comprehensive Documentation**: Detailed explanations of algorithms and mathematical foundations
- **Performance Analysis**: Benchmarking and complexity analysis
- **Examples and Tutorials**: Step-by-step examples demonstrating algorithm usage

## Installation

```bash
pip install -e .
```

## Quick Start

```python
from primes.aks import AKSPrimalityTest

# Create an instance of the AKS test
aks = AKSPrimalityTest()

# Test if a number is prime
result = aks.is_prime(31)
print(f"31 is prime: {result}")  # True

# Get detailed step-by-step execution
result_detailed = aks.is_prime_detailed(31)
print(result_detailed)
```

## Algorithms Implemented

### AKS Primality Test
- **Time Complexity**: O(log^6 n) (theoretical), optimized versions available
- **Space Complexity**: O(log^3 n)
- **Deterministic**: Yes
- **Paper**: [PRIMES is in P](https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf)

## Project Structure

```
primes/
├── src/
│   └── primes/
│       ├── __init__.py
│       ├── aks/
│       │   ├── __init__.py
│       │   ├── core.py
│       │   └── optimizations.py
│       └── utils/
│           ├── __init__.py
│           ├── math_utils.py
│           └── polynomial.py
├── tests/
│   ├── __init__.py
│   ├── test_aks.py
│   └── test_utils.py
├── examples/
│   ├── basic_usage.py
│   ├── performance_comparison.py
│   └── step_by_step_aks.py
├── docs/
│   ├── algorithms/
│   │   └── aks.md
│   └── mathematical_foundations.md
├── benchmarks/
│   └── aks_benchmark.py
├── requirements.txt
├── setup.py
└── README.md
```

## Contributing

Please read [CONTRIBUTING.md](CONTRIBUTING.md) for details on our code of conduct and the process for submitting pull requests.

## License

This project is licensed under the MIT License - see the [LICENSE](LICENSE) file for details.

## References

1. Agrawal, M., Kayal, N., & Saxena, N. (2004). PRIMES is in P. Annals of Mathematics, 160(2), 781-793.
2. [AKS Primality Test - Wikipedia](https://en.wikipedia.org/wiki/AKS_primality_test)

## Acknowledgments

- Inspired by the VaidhyaMegha/optimization_algorithms repository structure
- Mathematical foundations based on the original AKS paper
