search

peterolson / BigInteger.js

An arbitrary length integer library for Javascript
The Unlicense
1.12k stars 187 forks source link

Function isPrime is misleading (not deterministic) #154

Closed gardhr closed 6 years ago

gardhr commented 6 years ago

The documentation for isPrime implies that the test is deterministic, which it is clearly not. Correct results using the bases [2, 325, 9375, 28178, 450775, 9780504, 1795265022] are only guaranteed for N <= 2^64. The only way to make the test truly deterministic is to try all bases below 2*log(N)^2. (Assuming that the Generalized Riemann Hypothesis is true, which by all accounts is believed to be so; see here for example). Or alternately, just go with the general consensus supported by the overwhelming experimental evidence which indicates that the lower bound is actually at most log(N). (I can find a reference in case you're interested).

Anyhow, at the very least please amend the docs to make it absolutely clear that isPrime is not strictly deterministic, as it stands.

peterolson commented 6 years ago

I think this may have been an oversight in pull request #152

@oogFranz Could you look into this?

gardhr commented 6 years ago

For what it's worth I went ahead and submitted a pull request.

peterolson commented 6 years ago

I merged in your pull request.