Rust icon indicating copy to clipboard operation
Rust copied to clipboard

feat: add fermats little theorem

Open saahil-mahato opened this issue 1 year ago • 2 comments

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 (k tests) 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 warnings just before my last commit and fixed any issue that was found.
  • [x] I ran cargo fmt just before my last commit.
  • [x] I ran cargo test just before my last commit and all tests passed.
  • [x] I added my algorithm to the corresponding mod.rs file within its own folder, and in any parent folder(s).
  • [x] I added my algorithm to DIRECTORY.md with the correct link.
  • [x] I checked COUNTRIBUTING.md and my code follows its guidelines.

saahil-mahato avatar Oct 06 '24 23:10 saahil-mahato

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.

codecov-commenter avatar Oct 06 '24 23:10 codecov-commenter

@vil02 I have resolved the comments. Please review and let me know if anything is missing.

saahil-mahato avatar Oct 12 '24 07:10 saahil-mahato