PDA

View Full Version : راهنمایی در مورد الگوریتم RabinMiller



NIMA_1981
شنبه 02 اردیبهشت 1391, 17:49 عصر
سلام دوستان
من دو قسمت از این الگوریتم را نفهمیدم میشه بگید دقیقا چه کاری انجام میدن

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
یک شنبه 03 اردیبهشت 1391, 02:52 صبح
دوستان میشه راهنمایی کنید

سوداگر
یک شنبه 03 اردیبهشت 1391, 03:24 صبح
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
یک شنبه 03 اردیبهشت 1391, 12:46 عصر
سلام ممنون از توضیح شما - بسیار مفید بود