mathjs: The function "isPrime" may emit a endless loop when paramater is huge.

my testing code:

const { create, all } = require('mathjs');
const config = {
  epsilon: 1e-12,
  matrix: 'Matrix',
  number: 'BigNumber',
  precision: 256, //i have try 64 128
  predictable: false,
  randomSeed: null
}
const math = create(all, config)
let a = math.bignumber("230584300921369395");
let b = math.bignumber("2305843009213693951");
console.log("230584300921369395 is Prime", math.isPrime(a));  //this number is fit for then function isPrime
console.log("------");
console.log("2305843009213693951 is Prime?");
console.log(math.isPrime(b));  //this line will not finish, the cpu is 100%
console.log("exit");

I run it in node v12.18.1 on macOS Big Sur

I have try precision: 64 , precision:128 and 256, result is the same.

Then I have check source file isPrime.js in path ./node_modules/mathjs/lib/cjs/function/utils/isPrime.js

I think the problem maybe there.

//  ./node_modules/mathjs/lib/cjs/function/utils/isPrime.js

...
BigNumber: function BigNumber(n) {
...
     for (var i = 5; n.gte(i * i); i += 6) {
        if (n.mod(i).eq(0) || n.mod(i + 2).eq(0)) {
          return false;
        }
      }
...

my question is: can i*i here cause the endless loop when n is big enough ?

thx.

About this issue

Original URL
State: closed
Created 3 years ago
Comments: 17 (13 by maintainers)

Most upvoted comments

The first software I open-sourced was a diskette (5-1/4) of prime number functions along with the necessary Unlimited Precision math. This went to the ‘C’ User Group. Sometime in the 70’s I think. I thought of this while looking at the bottom of the Wikiencylopedia page reference earlier. Seems like doing those using the obvious library in JS would be at least as much fun as doing them in BDS C. See; https://www.bdsoft.com/resources/bdsc.html

On Sun, Mar 14, 2021 at 3:55 AM Viktor @.***> wrote:

@hsmyers https://github.com/hsmyers nice example, There is a “Deterministic variant” although, which is not probabilistic, seems. Well… it relies on something not proved. Btw, seems, “deterministic” is a much like probabilistic, but iterates for a range up to some limit…

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/josdejong/mathjs/issues/2133#issuecomment-798879035, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAHE7PWI2L544QZ6SDPOSDTTDSBXXANCNFSM4Y7OL2NA .

hsmyers on Mar 14, 2021

Well, by definition, ‘probabilistic’ can’t guarantee 100%. No more than a sieve can unless infinite. But as you test under more and more bases, it is less and less likely that the test is wrong. A bit like calculus and the area under a curve. At some point someone yells out ‘enough!’ and you quit testing. I remember when my partner in a small architects firm, walked in and asked what I was doing. I told him I was making sure of the details on the current set of plans (I was a plans architect—it’s what they do.) He looked at the screen and asked me what the scale was. I typed the code to display the distance from point to point. He then rudely pointed out that at the scale shown, the ‘fix’ would take an electron microscope to see! I said ‘Oh!’ Sort of like that 😃

On Sat, Mar 13, 2021 at 10:31 AM Viktor @.***> wrote:

@hsmyers https://github.com/hsmyers , I don’t know, but is the “deterministic variant” 100% accurate?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/josdejong/mathjs/issues/2133#issuecomment-798670341, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAHE7PTRKBKRFCWIXI4RV6TTDOONVANCNFSM4Y7OL2NA .

hsmyers on Mar 13, 2021

@JamesLIAOHJ If you need something much faster (for number bigger than 2**53) - a variant is https://en.wikipedia.org/wiki/Miller–Rabin_primality_test#Deterministic_variants .

Yaffle on Mar 11, 2021