Skip to content
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 our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve performance for modular arithmetic #328

Open
chiphogg opened this issue Nov 21, 2024 · 0 comments
Open

Improve performance for modular arithmetic #328

chiphogg opened this issue Nov 21, 2024 · 0 comments
Labels
⬇️ affects: code (implementation) Affects implementation details of the code 📁 kind: bug Something isn't working correctly, or there's a mistake 💪 effort: medium

Comments

@chiphogg
Copy link
Contributor

Right now, there are numbers we know we can't factor at compile time: see comments in #217. We're using too many steps, and clang bails. However, those comments also suggest that it should be possible to get away with far far fewer steps. It turns out that we are spending almost all of our steps on our custom implementation of mul_mod. If we can find a much more efficient implementation, we should be able to factor a much wider variety of numbers. Leading candidate options include:

  1. Implement Montgomery/REDC form
  2. Do manual "double-wide" multiplication and mod

Whichever route we go, getting a more efficient mul_mod should also make it worthwhile to switch to a "batched" implementation of Pollard's rho, which replaces many GCD calls (slow no matter what) with modular multiplication calls (which can be made fast). The batched implementation is a pretty marginal win if we implement it now (and is in some cases a little bit worse), but is a much bigger win if multiplication is cheap.

@chiphogg chiphogg added 📁 kind: bug Something isn't working correctly, or there's a mistake 💪 effort: medium ⬇️ affects: code (implementation) Affects implementation details of the code labels Nov 21, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
⬇️ affects: code (implementation) Affects implementation details of the code 📁 kind: bug Something isn't working correctly, or there's a mistake 💪 effort: medium
Projects
None yet
Development

No branches or pull requests

1 participant