Rosetta Code

Miller–Rabin primality test: Difference between revisions

Page Discussion

Miller–Rabin primality test (view source)

Revision as of 15:41, 21 June 2017

83 bytes added ,  6 years ago
→‎{{header|C sharp|C#}}
(→‎{{header|Kotlin}}: Updated example see https://github.com/dkandalov/rosettacode-kotlin for details)
Line 695:
public static bool IsPrime(int n, int k)
{
if ((n < 2) || (n % 2 == 0)) return (n == 2);
if(n < 2)
 
{
return false int s = n - 1;
}while (s % 2 == 0) s >>= 1;
 
if(n != 2 && n % 2 == 0)
{
return false;
}
int s = n - 1;
while(s % 2 == 0)
{
s >>= 1;
}
Random r = new Random();
for (int i = 0; i < k; i++)
{
doubleint a = r.Next((int)n - 1) + 1;
int temp = s;
intlong mod = (int)Math.Pow(a, (double)temp) % n1;
whilefor (tempint j != n0; -j 1< &&temp; mod++j) != 1 && mod != n(mod -* 1a) % n;
while (temp != n - 1 && mod != 1 && mod != n - 1)
{▼
mod = (mod * mod) % n;▼
temp = temp * 2;
}
if(mod != n - 1 && temp % 2 == 0)▼
{
▲ mod = (mod * mod) % n;
return false;
▲ { temp *= 2;
}
 
▲ if (mod != n - 1 && temp % 2 == 0) return false;
}
return true;
}
}</lang>
[https://stackoverflow.com/questions/7860802/miller-rabin-primality-test] Corrections made 6/21/2017
<br><br>
<lang csharp>// Miller-Rabin primality test as an extension method on the BigInteger type.
// Based on the Ruby implementation on this page.
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/107936"