Java icon indicating copy to clipboard operation
Java copied to clipboard

Add Baby-Step Giant-Step (BSGS) Discrete Logarithm Algorithm

Open rajucreate opened this issue 3 months ago • 1 comments

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

rajucreate avatar Nov 25 '25 12:11 rajucreate

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.

codecov-commenter avatar Nov 25 '25 12:11 codecov-commenter