Java
Java copied to clipboard
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