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

Further optimization of Lucas test may be possible #11

Open
danaj opened this issue Jun 20, 2014 · 0 comments
Open

Further optimization of Lucas test may be possible #11

danaj opened this issue Jun 20, 2014 · 0 comments
Assignees

Comments

@danaj
Copy link
Owner

danaj commented Jun 20, 2014

See: flintlib/flint#81
also: https://github.com/wbhart/flint2/blob/trunk/ulong_extras/is_probabprime_lucas.c

It may be possible to reduce the number of operations in the Lucas test inner loop. The C-P method for V chain uses 2 mulmuds and 2 submods for each loop. They include a way to do this for all Lucas tests.

MPU uses:
2+1 / 5+3 for Q=1 (bit 0 vs. bit 1)
2+1 / 3+3 for P=1/Q=-1 (bit 0 vs. bit 1, also includes more logic)
3+2 / 7+4 otherwise (bit0 vs. bit1, also more logic)

MPUGMP uses:
2+2 for Q=1, P>2 (with inversion)
2+1 / 5+3 for Q=1 (P <= 2 or non-invertible)
4+1 / 8+3 otherwise

We should also look at merging some of these so we do the best thing.

Consider using the inversion method in MPU, and note that if gcd(a,n) == 1, then the inverse should exist, so we don't need to include code for no-inversion.

@danaj danaj self-assigned this Jun 20, 2014
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant