peterolson / BigInteger.js

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

fixed isPrime, minor optimization of millerRabinTest (all tests passed) #155

Closed gardhr closed 6 years ago

gardhr commented 6 years ago

Modified isPrime in such a way that the result is now fail-safe. Should note that isProbablePrime is still a better option. Damgård-Landrock-Pomerance proved that the maximum error-term for a randomized probabalistic test decreases rapidly as the number of trials increases (and in fact the larger number of bits in the number under test actually equates to less iterations needed). In short, 5 to 20 iterations is more than sufficient for all practical purposes to produce a nearly 100% certain result.

Minor optimization of millerRabinTest simply reduces a BigInteger calculation to small-integer math. (Since the exponent of the power of two being factored out of N-1 is obviously guaranteed to fit into a small integer, and that exponent is essentially what determines the number of iterations for the inner loop).

coveralls commented 6 years ago

Coverage Status

Coverage increased (+0.005%) to 99.423% when pulling b1913c134976c6f396ae91a73d8386b0bd3abc5a on gardhr:master into 092c29dbc5288d6a041128f6c0a88af284a15bca on peterolson:master.

peterolson commented 6 years ago

Looks good!