Miller–Rabin primality test: Difference between revisions

Content added Content deleted

Inline

@@ Line 357: / Line 357: @@
       y := i&1 ? mod(y*z,m) : y, z := mod(z*z,m), i >>= 1
    Return y
 }</lang>
 =={{header|bc}}==
@@ Line 431: / Line 431: @@
 }
 quit</lang>
 =={{header|Bracmat}}==
 {{trans|bc}}
@@ Line 687: / Line 688: @@
 }</lang>
 Inspiration from http://stackoverflow.com/questions/4424374/determining-if-a-number-is-prime
 =={{header|C sharp|C#}}==
@@ Line 2,863: / Line 2,862: @@
 End Function
 </lang>
 =={{header|Mathematica}}==
 <lang Mathematica>MillerRabin[n_,k_]:=Module[{d=n-1,s=0,test=True},While[Mod[d,2]==0 ,d/=2 ;s++]
@@ Line 3,610: / Line 3,610: @@
 for (1..100) { say if is_prime_mr($_) }</lang>
 Math::Pari can be used in a fashion similar to the Pari/GP custom function.  The builtin accessed using a second argument to <tt>ispseudoprime</tt> was added to a later version of Pari (the Perl module uses version 2.1.7) so is not accessible directly from Perl.
-=={{header|Perl 6}}==
-{{works with|Rakudo|2015-09-22}}
-<lang perl6># the expmod-function from: http://rosettacode.org/wiki/Modular_exponentiation
-sub expmod(Int $a is copy, Int $b is copy, $n) {
-	my $c = 1;
-	repeat while $b div= 2 {
-		($c *= $a) %= $n if $b % 2;
-		($a *= $a) %= $n;
-	}
-	$c;
-}
-subset PrimeCandidate of Int where { $_ > 2 and $_ % 2 };
-my Bool multi sub is_prime(Int $n, Int $k)            { return False; }
-my Bool multi sub is_prime(2, Int $k)                 { return True; }
-my Bool multi sub is_prime(PrimeCandidate $n, Int $k) {
-	my Int $d = $n - 1;
-	my Int $s = 0;
-	while $d %% 2 {
-		$d div= 2;
-		$s++;
-	}
-	for (2 ..^ $n).pick($k) -> $a {
-		my $x = expmod($a, $d, $n);
-		# one could just write "next if $x == 1 | $n - 1"
-		# but this takes much more time in current rakudo/nom
-		next if $x == 1 or $x == $n - 1;
-		for 1 ..^ $s {
-			$x = $x ** 2 mod $n;
-			return False if $x == 1;
-			last if $x == $n - 1;
-		}
-		return False if $x !== $n - 1;
-	}
-	return True;
-}
-say (1..1000).grep({ is_prime($_, 10) }).join(", "); </lang>
 =={{header|Phix}}==
@@ Line 4,252: / Line 4,207: @@
 (prime? 4547337172376300111955330758342147474062293202868155909489) ;-> outputs true
 </lang>
+=={{header|Raku}}==
+(formerly Perl 6)
+{{works with|Rakudo|2015-09-22}}
+<lang perl6># the expmod-function from: http://rosettacode.org/wiki/Modular_exponentiation
+sub expmod(Int $a is copy, Int $b is copy, $n) {
+	my $c = 1;
+	repeat while $b div= 2 {
+		($c *= $a) %= $n if $b % 2;
+		($a *= $a) %= $n;
+	}
+	$c;
+}
+subset PrimeCandidate of Int where { $_ > 2 and $_ % 2 };
+my Bool multi sub is_prime(Int $n, Int $k)            { return False; }
+my Bool multi sub is_prime(2, Int $k)                 { return True; }
+my Bool multi sub is_prime(PrimeCandidate $n, Int $k) {
+	my Int $d = $n - 1;
+	my Int $s = 0;
+	while $d %% 2 {
+		$d div= 2;
+		$s++;
+	}
+	for (2 ..^ $n).pick($k) -> $a {
+		my $x = expmod($a, $d, $n);
+		# one could just write "next if $x == 1 | $n - 1"
+		# but this takes much more time in current rakudo/nom
+		next if $x == 1 or $x == $n - 1;
+		for 1 ..^ $s {
+			$x = $x ** 2 mod $n;
+			return False if $x == 1;
+			last if $x == $n - 1;
+		}
+		return False if $x !== $n - 1;
+	}
+	return True;
+}
+say (1..1000).grep({ is_prime($_, 10) }).join(", "); </lang>
 =={{header|REXX}}==