В чем ошибка в реализации теста Ферма нахождения простого числа?

Question

function isPrime(num) {
  
    if(num <= 1) return false;
    
    for(let i = 0; i < 100; i++){
      
      let a = Math.floor(Math.random()*(num-1) + 1);
      if(gcd(a, num) !== 1) return false;
      
      if((a ** (num - 1)) % num !== 1 ) return false; 
    
    }
    
    return true;
  }
  
  function gcd(x, y){
    
    if(y == 0) return x;
    else return gcd(y, x % y);
  }

Если входное число, например, 73, то возвращает false. Основание степени А генерит корректно. Судя по всему, проблема в выражении в 10 строке. Подскажите, пожалуйста, где брешь.

Answer 1

Возведение в степень выполняется неточно на вещественных числах. Вам нужно написать возведение в степень по модулю, не опираясь на стандартную операцию **.

Например, вычислим 3 ** (73 - 1). Это число требует 115 бит. Числа в JavaScript вещественные с мантиссой в 53 бита. Следовательно 62 младших бита будут отброшены. Получившееся округлённое число бесполезно в тесте Ферма.

Вам нужно возводить числа в степень по модулю точно: Возведение в степень по модулю.

В коде ниже найдите функцию pow, которая возводит число в степень быстро и без переполнений.

const gcd = (a, b) => {
    return (b == 0) ? a : gcd(b, a % b);
}

// a^b mod m
const pow = (a, b, m) => {
    if (b == 0) {
        return 1;
    }
    if (b % 2 == 0) {
        return pow(a * a % m, b / 2, m);
    }
    return a * pow(a, b - 1, m) % m;
};
    
const isPrimeFermat = n => {
    if (n <= 1) {
        return false;
    }

    for (let i = 0; i < 100; ++i) {
        const a = Math.floor(Math.random() * (n - 1) + 1);
        if (gcd(a, n) !== 1) {
            return false;
        }

        if (pow(a, n - 1, n) !== 1) {
            return false;
        }
    }

    return true;
};

БЛОГ НА HUSL

В чем ошибка в реализации теста Ферма нахождения простого числа?

Ответы (1 шт):