راهنمایی در مورد الگوریتم RabinMiller

[NIMA_1981]

سلام دوستان
من دو قسمت از این الگوریتم را نفهمیدم میشه بگید دقیقا چه کاری انجام میدن

public static class RabinMiller
{
public static bool IsPrime(int n, int k)
{
if(n < 2)
{
return false;
}
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++)
{
double a = r.Next((int)n - 1) + 1;
int temp = s;
int mod = (int)Math.Pow(a, (double)temp) % n;
while(temp != n - 1 && mod != 1 && mod != n - 1)
{
mod = (mod * mod) % n;
temp = temp * 2;
}
if(mod != n - 1 && temp % 2 == 0)
{
return false;
}
}
return true;
}
}

اول این خط

s >>= 1;

و در این کد منظور از next چیه

double a = r.Next((int)n - 1) + 1;

[NIMA_1981]

دوستان میشه راهنمایی کنید

[سوداگر]

s >>= 1;
بیتهای متغیر s رو یکی به سمت راست، شیفت میده (عملا تقسیم بر 2 میشه)
================================================

اما با خوندن ویکی پدیا (http://en.wikipedia.org/wiki/Miller–Rabin_primality_test) و اینجا (http://www.acmfever.blogfa.com/post-20.aspx) به صورت دست و پا شکسته :گیج: متوجه شدم که این الگوریتم، احتمال اول بودن n را با دقت k را بررسی می کند:


Miller Robin algorithm:

Input: n > 2, an odd integer to be tested for primality;

Input: k, a parameter that determines the accuracy of the test

Output: composite if n is composite, otherwise probably prime

write n − 1 as 2s·d with d odd by factoring powers of 2 from n − 1

LOOP: repeat k times:

pick a randomly in the range [2, n − 1]

x ← ad mod n

if x = 1 or x = n − 1 then do next LOOP

for r = 1 .. s − 1

x ← x2 mod n

if x = 1 then return composite

if x = n − 1 then do next LOOP

return composite

return probably prime


تا جایی که یادم میاد، اعداد اول خیلی بزرگ، مربوط میشد به اعتبارسنجی براساس رمزنگاری Encryption Authentication، شاید این الگوریتم شما به این قضیه مربوط بشه.

[NIMA_1981]

سلام ممنون از توضیح شما - بسیار مفید بود