6 releases
new 0.2.2 | Apr 29, 2025 |
---|---|
0.2.1 |
|
0.1.4 | Jun 16, 2024 |
#599 in Math
384 downloads per month
9KB
126 lines
Quadratic Residues -- A Brief Overview
"In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that: $$x^2 \equiv q \pmod{n}$$ Otherwise, q is called a quadratic nonresidue modulo n.
Originally an abstract mathematical concept from the branch of number theory known as modular arithmetic, quadratic residues are now used in applications ranging from acoustical engineering to cryptography and the factoring of large numbers."
Source: https://en.wikipedia.org/wiki/Quadratic_residue
For a quick overview of quadratic residues I recommend this video from Michael Penn.
Usage
Add the Crate to Your Project
cargo add quadratic_residues
or manually specify in Cargo.toml
[dependencies]
quadratic_residues = "0.2.2"
Examples
get_residues(7) => [1, 2, 4] // returns the quadratic residues of 7
get_non_residues(7) => [3, 5, 6] // returns the quadratic non-residues of 7
get_all_residues(7) => [1, 4, 2, 2, 4, 1] // returns the quadratic residues of 7 including duplicates
TODO
- add quadratic_residues_all() to include redundant integers for symmetry lovers [x]
- add T.quad_res(), T.non_res(), & T.all_res() [in progress]
- Impl Trait for signed and unsigned integers [in progress]
- improve test robustness [in progress]
1.0.0 release roadmap
- add n/2 optimization to double speed []
- sidestep de_dep-ing filter as micro-optimization []
- modify quadratic_residues_all behavior to return Vec<> from quadratic_residues() with it's reverse []
- account for rust '%' operator's handling of negative values []
- change naming conventions []
- full Impl coverage of std lib integer types []