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

Implement Baille-PSW instead of using F&J's hashtable #1

Open
JASory opened this issue Nov 8, 2024 · 0 comments
Open

Implement Baille-PSW instead of using F&J's hashtable #1

JASory opened this issue Nov 8, 2024 · 0 comments

Comments

@JASory
Copy link

JASory commented Nov 8, 2024

Forisek and Jancina's 16384-element hashtable requires 3 total SPRP tests, but modified variants of the BPSW can run in the same time as 2.5 fermat tests. So it is both faster and considerably more space efficient. Only when you call the 262144-element table to use 2 SPRP tests do you gain a speed improvement over the (modified) BPSW.

A reference implementation of a such a modified BPSW for 64-integers can be found in the Machine-prime source code. Directly translating it might be difficult particularly in the Montgomery arithmetic, but just replacing all the Montgomery forms with standard integer representations and operations will work.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant