entropyxyz / crypto-primes

Random prime generation and primality testing library based on `crypto-bigint`.
https://docs.rs/crypto-primes
Apache License 2.0
17 stars 4 forks source link

Add a GCD check to the Lucas test #11

Closed fjarri closed 1 year ago

fjarri commented 1 year ago

Fixes #1

According to Robert Baillie himself (from private correspondence), strictly speaking the gcd(Q, n) == 1 check is necessary. Of course, in practice the Lucas test will be executed on a pre-sieved n, and Q is always small, so this condition is satisfied automatically. But in order to avoid having implicit assumptions in the code (since lucas_test() is public), this PR adds the GCD check. The performance impact is negligible, so why not.

codecov-commenter commented 1 year ago

Codecov Report

Base: 95.85% // Head: 95.95% // Increases project coverage by +0.10% :tada:

Coverage data is based on head (06591f8) compared to base (7d32520). Patch coverage: 98.33% of modified lines in pull request are covered.

:mega: This organization is not using Codecov’s GitHub App Integration. We recommend you install it so Codecov can continue to function properly for your repositories. Learn more

Additional details and impacted files ```diff @@ Coverage Diff @@ ## master #11 +/- ## ========================================== + Coverage 95.85% 95.95% +0.10% ========================================== Files 7 8 +1 Lines 940 989 +49 ========================================== + Hits 901 949 +48 - Misses 39 40 +1 ``` | [Impacted Files](https://codecov.io/gh/entropyxyz/crypto-primes/pull/11?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None) | Coverage Δ | | |---|---|---| | [src/hazmat.rs](https://codecov.io/gh/entropyxyz/crypto-primes/pull/11?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None#diff-c3JjL2hhem1hdC5ycw==) | `71.42% <ø> (ø)` | | | [src/hazmat/lucas.rs](https://codecov.io/gh/entropyxyz/crypto-primes/pull/11?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None#diff-c3JjL2hhem1hdC9sdWNhcy5ycw==) | `95.01% <91.66%> (-0.26%)` | :arrow_down: | | [src/hazmat/gcd.rs](https://codecov.io/gh/entropyxyz/crypto-primes/pull/11?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None#diff-c3JjL2hhem1hdC9nY2QucnM=) | `100.00% <100.00%> (ø)` | | Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None)

:umbrella: View full report at Codecov.
:loudspeaker: Do you have feedback about the report comment? Let us know in this issue.