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 2 weeks 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