Add Baby-Step Giant-Step (BSGS) Discrete Logarithm Algorithm
Summary
This PR adds the Baby-Step Giant-Step (BSGS) algorithm for solving the discrete logarithm problem:
Find x such that: a^x ≡ b (mod m)
This algorithm is widely used in number theory and cryptography and runs in O(√m) time.
What’s Included
i) Added full implementation:
- src/main/java/com/thealgorithms/maths/DiscreteLogarithmBSGS.java
ii) Added JUnit tests:
- src/test/java/com/thealgorithms/maths/DiscreteLogarithmBSGSTest.java
iii) Added entry in DIRECTORY.md under the maths section
iv) Includes detailed Javadoc and follows repository coding conventions
Algorithm Overview
- Time Complexity: O(√m)
- Space Complexity: O(√m)
- Uses the Baby-Step Giant-Step technique to compute discrete logarithms efficiently
- Includes modular exponentiation helper using fast power
- [x] I have read CONTRIBUTING.md.
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [ ] All new code is formatted with
clang-format -i --style=file path/to/your/file.java
Codecov Report
:x: Patch coverage is 92.59259% with 2 lines in your changes missing coverage. Please review.
:white_check_mark: Project coverage is 78.53%. Comparing base (a14e1e3) to head (29e7dbe).
| Files with missing lines | Patch % | Lines |
|---|---|---|
| ...com/thealgorithms/maths/DiscreteLogarithmBSGS.java | 92.59% | 2 Missing :warning: |
Additional details and impacted files
@@ Coverage Diff @@
## master #7118 +/- ##
============================================
+ Coverage 78.51% 78.53% +0.01%
- Complexity 6752 6760 +8
============================================
Files 759 760 +1
Lines 22402 22429 +27
Branches 4400 4406 +6
============================================
+ Hits 17589 17614 +25
- Misses 4108 4110 +2
Partials 705 705
:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.
:rocket: New features to boost your workflow:
- :snowflake: Test Analytics: Detect flaky tests, report on failures, and find test suite problems.