Browse Code
This is an easy-to-understand algorithm of integer factorization with heuristically evaluated complexity L(4/15, 2), which is better than the general number field sieve algorithm with L(1/3, 1.923).
NFB searches common factors of the quadratic residues modulo n using GCD. All relations are processed by the Gaussian elimination procedure. Different strategies of searching the relations can be applied, many giving complexity better than L(1/3, 1.923).
Features
- no-factor-base
- gcd
- factorization
- integer
- congruence-of-squares
Project Samples
Follow NFB integer factorization
Other Useful Business Software
Forever Free Full-Stack Observability | Grafana Cloud
Built on open standards like Prometheus and OpenTelemetry, Grafana Cloud includes Kubernetes Monitoring, Application Observability, Incident Response, plus the AI-powered Grafana Assistant. Get started with our generous free tier today.
Rate This Project
Login To Rate This Project
User Reviews
-
You do not need to be a specialist in number theory to comprehend this algorithm and try different strategies of searching quadratic residues mod N . Good for home research in number theory :) or as a material for a diploma thesis. Significant work is needed to parallelize this on GPU or CPU for factorization of really large numbers.
