search

peterolson / BigInteger.js

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

Miller-Rabin test optimization #156

Closed gardhr closed 6 years ago

gardhr commented 6 years ago

Just a slight optimization, but if x^2 = 1 mod n then any further iterations cannot possibly produce n-1 (since obviously 1^2 = 1 mod n, for any given n > 1) and so in that case n is definitely composite and we can just go ahead and exit the test early on.

coveralls commented 6 years ago

Coverage Status

Coverage increased (+0.0007%) to 99.424% when pulling 237743f285d68a91c18b3f24ba4aa360071cb822 on gardhr:master into ee602ccb7acaedc75f5b1a1df82820e4d839c1be on peterolson:master.

coveralls commented 6 years ago

Coverage Status

Coverage increased (+0.0007%) to 99.424% when pulling 237743f285d68a91c18b3f24ba4aa360071cb822 on gardhr:master into ee602ccb7acaedc75f5b1a1df82820e4d839c1be on peterolson:master.

peterolson commented 6 years ago

Thanks! Looks good to me