Miller–Rabin primality test: Difference between revisions

Content added Content deleted

Inline

@@ Line 210: / Line 210: @@
 }</lang>
-=={{header|Bc}}==
+=={{header|bc}}==
+Requires a <tt>bc</tt> with long names.
-{{works with|GNU bc}}
-<lang bc>next = 1;    # seed of the random generator
-scale = 0;
+{{works with|OpenBSD bc}}
-# random generator (according to POSIX...); since
+(A previous version worked with [[GNU bc]].)
-# this gives number between 0 and 32767, we can
+<lang bc>seed = 1   /* seed of the random number generator */
-# test only numbers in this range.
+scale = 0
-define rand()
-{
+/* Random number from 0 to 32767. */
-  next = next * 1103515245 + 12345;
+define rand() {
-  return ((next/65536) % 32768);
+  /* Cheap formula (from POSIX) for random numbers of low quality. */
+  seed = (seed * 1103515245 + 12345) % 4294967296
+  return ((seed / 65536) % 32768)
 }
-define rangerand(from, to)
+/* Random number in range [from, to]. */
+define rangerand(from, to) {
-{
+  auto b, h, i, m, n, r
-  return (from + rand()%(to-from+1));
+  m = to - from + 1
+  h = length(m) / 2 + 1  /* want h iterations of rand() % 100 */
+  b = 100 ^ h % m        /* want n >= b */
+  while (1) {
+    n = 0                /* pick n in range [b, 100 ^ h) */
+    for (i = h; i > 0; i--) {
+      r = rand()
+      while (r < 68) { r = rand(); }  /* loop if the modulo bias */
+      n = (n * 100) + (r % 100)       /* append 2 digits to n */
+    }
+    if (n >= b) { break; }  /* break unless the modulo bias */
+  }
+  return (from + (n % m))
 }
-define miller_rabin_test(n, k)
-{
-  auto d, r, a, x, s;
+/* n is probably prime? */
-  if ( n <= 3) { return(1); }
+define miller_rabin_test(n, k) {
-  if ( (n % 2) == 0) { return(0); }
+  auto d, r, a, x, s
-  # find s and d so that d*2^s = n-1
+  if (n <= 3) { return (1); }
+  if ((n % 2) == 0) { return (0); }
-  d = n-1;
-  s = 0;
-  while( (d%2) == 0 ) {
+  /* find s and d so that d * 2^s = n - 1 */
-     d = d/2;
+  d = n - 1
-     s += 1;
+  s = 0
+  while((d % 2) == 0) {
+     d /= 2
+     s += 1
   }
-  while(k-- > 0) {
+  while (k-- > 0) {
-    a = rangerand(2, n-2);
+    a = rangerand(2, n - 2)
-    x = (a^d) % n;
+    x = (a ^ d) % n
-    if ( x != 1 ) {
+    if (x != 1) {
-      for(r=0; r < s; r++) {
+      for (r = 0; r < s; r++) {
-         if ( x == (n-1) ) { break; }
+        if (x == (n - 1)) { break; }
-         x = (x*x) % n;
+        x = (x * x) % n
       }
-      if ( x != (n-1) ) {
+      if (x != (n - 1)) {
-         return (0);
+        return (0)
       }
     }
   }
-  return (1);
+  return (1)
 }
+for (i = 1; i < 1000; i++) {
+  if (miller_rabin_test(i, 10) == 1) {
-for(i=1; i < 1000; i++) {
+    i
-  if ( miller_rabin_test(i, 10) == 1 ) {
-     i
   }
 }
-quit;</lang>
+quit</lang>
 =={{header|C}}==