Skip to content

The function "isPrime" may emit a endless loop when paramater is huge. #2133

@JamesLIAOHJ

Description

@JamesLIAOHJ

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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions