Rust
Rust copied to clipboard
feat: add fermats little theorem
Description
Fermat Primality Test Implementation
This PR introduces an implementation of the Fermat Primality Test in Rust. The algorithm leverages Fermat's Little Theorem, which states that if ( p ) is a prime number, then for any integer ( a ) such that ( 1 < a < p - 1 ), it holds that:
a^(p−1) ≡ 1 (mod p)
Key Features:
- Modular Exponentiation: Efficient computation of ( a^{(p-1)} \mod p ) is performed using a helper function to handle large numbers without overflow.
- Probabilistic Approach: The algorithm allows for multiple iterations (
ktests) with randomly selected bases to increase the reliability of the primality check. - Composite Detection: While it identifies prime numbers effectively, the implementation also recognizes that some composite numbers, known as Carmichael numbers, can pass the test under certain conditions.
Test Cases:
- The PR includes comprehensive unit tests for various scenarios, including known prime numbers, composite numbers, small integers, large numbers, and special cases like Carmichael numbers.
This implementation provides a fast, probabilistic approach to primality testing, making it suitable for applications in cryptography and numerical analysis.
Type of change
Please delete options that are not relevant.
- [x] New feature (non-breaking change which adds functionality)
Checklist:
- [x] I ran bellow commands using the latest version of rust nightly.
- [x] I ran
cargo clippy --all -- -D warningsjust before my last commit and fixed any issue that was found. - [x] I ran
cargo fmtjust before my last commit. - [x] I ran
cargo testjust before my last commit and all tests passed. - [x] I added my algorithm to the corresponding
mod.rsfile within its own folder, and in any parent folder(s). - [x] I added my algorithm to
DIRECTORY.mdwith the correct link. - [x] I checked
COUNTRIBUTING.mdand my code follows its guidelines.
Codecov Report
Attention: Patch coverage is 96.00000% with 1 line in your changes missing coverage. Please review.
Project coverage is 95.36%. Comparing base (
bc8d6fa) to head (dfcdea6). Report is 8 commits behind head on master.
| Files with missing lines | Patch % | Lines |
|---|---|---|
| src/math/fermats_little_theorem.rs | 96.00% | 1 Missing :warning: |
Additional details and impacted files
@@ Coverage Diff @@
## master #809 +/- ##
==========================================
+ Coverage 95.32% 95.36% +0.04%
==========================================
Files 310 312 +2
Lines 22484 22698 +214
==========================================
+ Hits 21433 21647 +214
Misses 1051 1051
:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.
@vil02 I have resolved the comments. Please review and let me know if anything is missing.