Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

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

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Open
rajucreate wants to merge12 commits intoTheAlgorithms:master
base:master
Choose a base branch
Loading
fromrajucreate:master

Conversation

@rajucreate
Copy link

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

  • I have readCONTRIBUTING.md.
  • This pull request is all my own work -- I have not plagiarized it.
  • All filenames are in PascalCase.
  • All functions and variable names follow Java naming conventions.
  • All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
  • All new code is formatted withclang-format -i --style=file path/to/your/file.java

@codecov-commenter
Copy link

codecov-commenter commentedNov 25, 2025
edited
Loading

Codecov Report

❌ Patch coverage is92.59259% with2 lines in your changes missing coverage. Please review.
✅ Project coverage is 78.53%. Comparing base (a14e1e3) to head (29e7dbe).

Files with missing linesPatch %Lines
...com/thealgorithms/maths/DiscreteLogarithmBSGS.java92.59%2 Missing⚠️
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

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report?Share it here.

🚀 New features to boost your workflow:
  • ❄️Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

Sign up for freeto join this conversation on GitHub. Already have an account?Sign in to comment

Reviewers

@DenizAltunkapanDenizAltunkapanAwaiting requested review from DenizAltunkapanDenizAltunkapan is a code owner

@yanglbmeyanglbmeAwaiting requested review from yanglbmeyanglbme is a code owner

@alxkmalxkmAwaiting requested review from alxkmalxkm is a code owner

At least 1 approving review is required to merge this pull request.

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@rajucreate@codecov-commenter

[8]ページ先頭

©2009-2025 Movatter.jp