Fermats kleiner Satz in JS

Question

Ich habe gerade versucht Fermats kleinen Satz in JavaScript zu implementieren. Ich versuchte, es in beiden Richtungen, a ^ (p-1) mod p = 1 und a ^ p mod p = a mod p.

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

und

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

Es ist nicht in beiden Richtungen funktioniert, ist es eine Möglichkeit, das zu beheben?

Answer 1

In Javascript ^ Mittel XOR . Für Potenzierung braucht Math.pow(x, y).

function fermat(a, p) {
  return Math.pow(a, p - 1) % p === 1;
}

Answer 2

Statt ^, müssen Sie Math.pow verwenden

Answer 3

Neben der ^ vs. Math.pow () issue andere haben darauf hingewiesen, die nächste Hürde Sie wird wahrscheinlich Gesicht ist die begrenzte Genauigkeit der Javascript integrierte numerische Typen. Sie werden sehr schnell die Reichweite genau darstellbare Javascript überschreiten Zahlen einmal beginnen die Exponenten groß wird, da sie, wenn Sie wollen, wird eine Routine, wie dies als Primzahltest zu verwenden. Vielleicht möchten Sie schauen ein Javascript bignum Bibliothek (zum Beispiel dieses ), dass Abstützungen Potenzierung und Modul für beliebig große Zahlen.

Answer 4

In Javascript, das Karat (^) ist der XOR-Operator. Was Sie verwenden möchten, ist die Math.pow (x, y) Funktion, die x ^ y entspricht.

Answer 5

Hier ist mein Code (JavaScript) zum Überprüfen, ob eine Zahl prim ist, basierend auf Fermat kleinen Satz.

    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"