Message Boards Message Boards

0
|
5901 Views
|
8 Replies
|
4 Total Likes
View groups...
Share
Share this post:

How big a number can PrimeQ work?

I've got my own personal sieve for huge numbers, I was able to generate a number larger than the known largest prime number, but I need a certificate for the prime, and PrimeQ is taking more than one day to give me an answer. Can I send to someplace at Wolfram to get it verified?

8 Replies

According to

the test used in PrimeQ is not necessarily accurate above $2^{64}$. I'd be curious to hear from someone at Wolfram about if implementation details have changed.

I suppose you might resort to the PPP, https://reference.wolfram.com/language/PrimalityProving/guide/PrimalityProvingPackage.html. I have no experience with this though.

POSTED BY: Adam Mendenhall

Hi there, thank you so much for your answer even though it was not what I wished ...but hey some questions really have no answer...thank you.

Implementation details will change with the next release, to use an updated version of the Baiillie-PSW method.

https://arxiv.org/abs/2006.14425

This of course remains probabilistic. Here is Robert Baillie's remark though, which strikes me as quite apt for the problem at hand. "There are zero known counterexamples to the original BPSW, and we expect the new test to have even fewer :)"

POSTED BY: Daniel Lichtblau

Thank you Dr. Daniel looking forward to it... i will read the article you send me...thank you so much!!!

Posted 1 year ago

So was updated PSW implemented?

POSTED BY: ZAQU zaqu

Yes, PrimeQ uses the recent version of PSW.

POSTED BY: Daniel Lichtblau
Posted 1 year ago

So base 3 Miller-Rabin no longer is used, THAT is great. BTW, you did not forget gcd(Q, n) == 1 check, right? See other implementation: https://github.com/entropyxyz/crypto-primes/pull/11

POSTED BY: ZAQU zaqu

As best I can tell, the Miller-Rabin 3-psuedoprime test is not used.

Regarding our current Lucas test, I believe the reference implementation I posted on Community is equivalent to what is implemented in our internal code.

POSTED BY: Daniel Lichtblau
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract