Маленькая теорема Ферма в JS - PullRequest
Новая
       5

Маленькая теорема Ферма в JS

6 голосов
/ 03 августа 2010

Я только что попытался реализовать небольшую теорему Ферма в JavaScript. Я попробовал это обоими способами, ^ (p-1) mod p = 1 и ^ p mod p = mod p. 

function fermat(a, p) {
  return (((a ^ (p - 1)) % p) === 1);
}

и 

function fermat(a, p) {
  return ( ( a^p ) % p ) === ( a % p );
}

Это не работает в обоих направлениях, есть ли способ это исправить?

Ответы [ 5 ]

9 голосов
/ 03 августа 2010

В Javascript ^ означает XOR . Для возведения в степень вам нужно Math.pow(x, y). 

function fermat(a, p) {
  return Math.pow(a, p - 1) % p === 1;
}
7 голосов
/ 03 августа 2010

Вместо ^ вам нужно использовать Math.pow

3 голосов
/ 04 августа 2010

В дополнение к проблеме ^ vs. Math.pow (), на которую указывали другие, следующее препятствие вы, скорее всего, столкнетесь с ограниченной точностью встроенного числового кода Javascript типы. Вы очень быстро превысите диапазон точно представимого Javascript числа, как только показатели начинают расти, как они будут, если вы хотите использовать такую ​​процедуру в качестве теста на первичность. Вы можете посмотреть в библиотека javascript bignum (например, this ), которая поддерживает возведение в степень и модуль для сколь угодно больших целых чисел.

2 голосов
/ 04 августа 2010

В javascript карат (^) является оператором XOR. Вы хотите использовать функцию Math.pow (x, y), эквивалентную x ^ y.

0 голосов
/ 19 мая 2018

Вот мой код (JavaScript) для проверки, является ли число простым на основе теоремы Ферма. 

    function getRandomInt(min,max) { /* getting a random between given max and min values */
        min = Math.ceil(min);
        max = Math.ceil(max);
        return Math.floor(Math.random()*(max-min))+min;
    }

    function getGCD(a,b) { /* getting the greatest common divisor */
        var tmp;
        while (b !== 0) {
            tmp = b;
            b = a%b;
            a = tmp;
        }
        return a;
    }

    function getPower(a,b,p) { /* getting the a^b mod p */
        if (b == 1)
         return a%p;
        else {
         x = getPower(a,Math.floor(b/2),p);
         if (b%2 == 0) 
          return (x*x)%p;
         else return (((x*x)%p)*a)%p;
        }
    }

    function fermatTesting(Num) { //Checking Num by using Fermat's theorem
        var a = getRandomInt(2,Num-1);
        if (getGCD(a,Num) !== 1) {
            return "COMPOSITE";
        }
        else {
            if (getPower(a,Num-1,Num) !== 1) {
                return "COMPOSITE";
            }
            else {
                return "PRIME"; 
            }
        }
    }

    console.log(fermatTesting(57)); //Displays "COMPOSITE"
...