PRIM ist ein hochmodernes Framework für die Implementierung, Analyse und Benchmarking verschiedener Primzahltests. Es kombiniert Python-Flexibilität mit C/C++-Performance für optimale Ergebnisse in der algorithmischen Primzahlforschung.
- Fortgeschrittene Algorithmen: Miller-Rabin, Baillie-PSW, Forisek-Jancina
- Multi-Language Performance: Python + C/C++ Hybridimplementierungen
- Umfassende Benchmarks: Detaillierte Performance-Analysen
- Modulare Architektur: Saubere Trennung verschiedener Funktionalitäten
- CI/CD Integration: Automatisierte Tests und Qualitätsprüfungen
PRIM/
├── src/prim/ # Kern-Python-Paket
│ ├── algorithms/ # Algorithmus-Implementierungen
│ ├── analysis/ # Analysewerkzeuge
│ └── core/ # Kernfunktionalitäten
├── native/ # C/C++ Performance-Module
├── benchmarks/ # Benchmark-Suites
├── tests/ # Testsuite
├── docs/ # Dokumentation
└── examples/ # Jupyter Notebooks mit Beispielen
git clone https://github.com/Waschtl904/PRIM.git
cd PRIM
python3 -m venv venv
source venv/bin/activate # Linux/macOS
venv\Scripts\activate # Windows
pip install -r requirements.txtfrom prim import miller_rabin, baillie_psw, forisek_jancina
# Miller-Rabin Test
is_prime = miller_rabin(1009, rounds=10)
print(f"1009 ist prim: {is_prime}")
# Baillie-PSW Test (deterministisch für kleine Zahlen)
is_prime = baillie_psw(1009)
print(f"1009 ist prim: {is_prime}")
# Forisek-Jancina (optimal für 32-bit)
is_prime = forisek_jancina(1009)
print(f"1009 ist prim: {is_prime}")# Primzahltest für einzelne Zahl
python -m prim test 1009
# Benchmark verschiedener Algorithmen
python -m prim benchmark --range 1000000
# Hilfe anzeigen
python -m prim --help# Forisek-Jancina C-Implementation
gcc -O3 native/forisek_jancina/_fj32_c.c -o fj32_c
./fj32_c 1000000
# Vollständiges Build-Script
./build_complete_baillie_psw.sh| Algorithmus | Typ | Komplexität | Anwendung |
|---|---|---|---|
| Miller-Rabin | Probabilistisch | O(k log³ n) | Allgemein, konfigurierbare Genauigkeit |
| Baillie-PSW | Deterministisch* | O(log³ n) | Höchste Zuverlässigkeit, keine bekannten Gegenbeispiele |
| Forisek-Jancina | Deterministisch | O(log² n) | Optimal für 32/64-bit Integer |
*praktisch deterministisch für Zahlen < 2⁶⁴
wheel_sieve/: Optimierte Sieb-Algorithmen mit Wheel-Factorizationhybrid_performance/: Performance-Vergleiche und Optimierungsstrategienprime_gap_analysis/: Statistische Analyse von Primzahlabständenquality_metrics/: Code-Qualität und Linting-Integration
# Alle Tests ausführen
pytest
# Mit Coverage-Report
pytest --cov=prim --cov-report=html
# Linting
flake8 src/
black src/
mypy src/prim/
# Pre-commit hooks
pre-commit run --all-filesDas Framework enthält umfassende Benchmark-Suites:
# Grundlegende Benchmarks
python benchmarks/comprehensive_benchmark.py
# Spezifische Algorithmus-Vergleiche
python -m prim benchmark --algorithms miller_rabin,baillie_psw --range 1000000Beispiel-Ergebnisse für Zahlen bis 10⁶:
- Forisek-Jancina: ~0.8ms durchschnittlich
- Baillie-PSW: ~1.2ms durchschnittlich
- Miller-Rabin (10 Runden): ~2.1ms durchschnittlich
Das examples/ Verzeichnis enthält interaktive Jupyter Notebooks:
01_forisek_jancina_algorithm.ipynb: Einführung in den FJ-Algorithmus02_hybrid_algorithms.ipynb: Vergleich verschiedener Ansätze03_performance_benchmarks.ipynb: Detaillierte Performance-Analysen04_prime_gap_analysis.ipynb: Primzahlabstand-Forschung05_baillie_psw_test.ipynb: Baillie-PSW Deep-Dive
pip install -r requirements-dev.txt
pre-commit install- Implementierung in
src/prim/algorithms/ - Tests in
tests/ - Benchmark-Integration in
benchmarks/ - Dokumentation aktualisieren
Vollständige Dokumentation verfügbar in docs/:
Wir freuen uns über Beiträge! Bitte lesen Sie CONTRIBUTING.md für Details zu:
- Code-Style Guidelines
- Pull Request Prozess
- Issue-Tracking
- Entwicklungsworkflow
Dieses Projekt steht unter der MIT Lizenz - siehe LICENSE für Details.
Sebastian Waschtl - GitHub
PRIM - Precision in Primality Research 🔢