Miller–Rabin primality test: Difference between revisions

Content added Content deleted

Inline

@@ Line 1,090: / Line 1,090: @@
 end program TestMiller</lang>
 ''Possible improvements'': create bindings to the [[:Category:GMP|GMP library]], change <code>integer(huge)</code> into something like <code>type(huge_integer)</code>, write a lots of interfaces to allow to use big nums naturally (so that the code will be unchanged, except for the changes said above)
+=={{header|FunL}}==
+Direct implementation of the task algorithm.
+<lang funl>import util.rnd
+def isProbablyPrimeMillerRabin( n, k ) =
+  n_1 = n - 1
+  d = n_1
+  s = 0
+  while 2|d
+    s++
+    d /= 2
+  for _ <- 1..k
+    a = rnd( 2, n )
+    x = a^d%n
+    if x == 1 or x == n - 1 then continue
+    for r <- 1..s - 1
+      x = x^2%n
+      if x == 1 then return false
+      if x == n_1 then break
+    else
+      return false
+  true
+for i <- 3..100
+  if isProbablyPrimeMillerRabin( i, 5 )
+    println( i )</lang>
+{{out}}
+<pre>
+</pre>
 =={{header|Go}}==