Miller–Rabin primality test: Difference between revisions

Content added Content deleted

Inline

@@ Line 490: / Line 490: @@
 (937 941 947 953 967 971 977 983 991 997)
 </pre>
+=={{header|D}}==
+<lang d>import std.random;
+bool isProbablePrime(long n, int k) {
+    if (n < 2 || n % 2 == 0)
+        return n == 2;
+    long d = n - 1;
+    long s = 0;
+    while (d % 2 == 0) {
+        d /= 2;
+        s++;
+    }
+    bool isComposite(long a) {
+        if (modpow(a, d, n) == 1)
+            return false;
+        foreach (i; 0 .. s+1) {
+            if (modpow(a, 2^^i * d, n) == n-1)
+                return false;
+        }
+        return true;
+    }
+    foreach (i; 0 .. k+1) {
+        if (isComposite(uniform(2, n)))
+            return false;
+    }
+    return true;
+}
+long modpow(long b, long e, long m) {
+    long result = 1;
+    while (e > 0) {
+        if ((e & 1) == 1) {
+            result = (result * b) % m;
+        }
+        b = (b * b) % m;
+        e >>= 1;
+    }
+    return result;
+}</lang>
 =={{header|E}}==