Miller–Rabin primality test: Difference between revisions

Content added Content deleted

Inline

@@ Line 2,788: / Line 2,788: @@
 For the return values of this function, <code>true</code> means "probably prime" and <code>false</code> means "definitely composite."
-<lang JavaScript>function probablyPrime(n, k) {
+<lang JavaScript>function probablyPrime(n) {
-	if (n === 2 || n === 3)
+  if (n === 2 || n === 3) return true
+  if (n % 2 === 0 || n < 2) return false
-		return true;
-	if (n % 2 === 0 || n < 2)
-		return false;
-	// Write (n - 1) as 2^s * d
+  // Write (n - 1) as 2^s * d
-	var s = 0, d = n - 1;
+  var s = 0,
-	while (d % 2 === 0) {
+    d = n - 1
+  while ((d & 1) == 0) {
-		d /= 2;
+    d >>= 1
-		++s;
+    ++s
-	}
+  }
+  let base = 2
-	WitnessLoop: do {
+  var x = Math.pow(base, d) % n
-		// A base between 2 and n - 2
-		var x = Math.pow(2 + Math.floor(Math.random() * (n - 3)), d) % n;
-		if (x === 1 || x === n - 1)
+  if (x == 1 || x == n - 1) return true
-			continue;
-		for (var i = s - 1; i--;) {
+  for (var i = 1; i <= s; i++) {
-			x = x * x % n;
+    x = (x * x) % n
-			if (x === 1)
-				return false;
-			if (x === n - 1)
-				continue WitnessLoop;
-		}
-		return false;
+    if (x === n - 1) return true
+  }
-	} while (--k);
+  return false
-	return true;
 }</lang>