Доброго времени суток!
Кто-нибудь может дать рабочую реализацию на C или Pascal? А то я не совсем понимаю принцип работы данного алгоритма.
P.S. Без ассемблерных вставок!
Тест Миллера-Рабина
Модератор: Модераторы разделов
-
Crazy
- Сообщения: 862
- Статус: Адепт Дзен.
- ОС: Mint, Win7.
-
BratSinot
- Сообщения: 812
- ОС: Slackware64
Re: Тест Миллера-Рабина
Тут GMP используется.
-
/dev/random
- Администратор
- Сообщения: 5412
- ОС: Gentoo
Re: Тест Миллера-Рабина
GMP тут используется только для арифметических операций с большими числами. Для чисел, которые помещаются в регистры процессора, особого смысла использовать этот тест нет. Но для ясности можете заменить mpz_mul(a, b, c) на a = b * c, mpz_add_ui(a, b, c) на a = b + c и т.д.
-
BratSinot
- Сообщения: 812
- ОС: Slackware64
Re: Тест Миллера-Рабина
/dev/random писал(а): ↑22.03.2011 09:38
GMP тут используется только для арифметических операций с большими числами. Для чисел, которые помещаются в регистры процессора, особого смысла использовать этот тест нет. Но для ясности можете заменить mpz_mul(a, b, c) на a = b * c, mpz_add_ui(a, b, c) на a = b + c и т.д.
А можете тогда еще помочь с остальными функциями? Просто я тут покопался и не понимаю предназначение пачки функций, да и вообще как этот GMP действует.
Ладно, попробую еще раз сам написать.
Вообщем попробовал я переписать с GMP на обычный C, получилось вот это, и оно не работает:
Код:
void swap(unsigned long int *x, unsigned long int *y)
{
unsigned long int t;
t = *x;
*x = *y;
*y = t;
}
unsigned long int decompose(unsigned long int n, unsigned long int *o)
{
unsigned long int i;
unsigned long int tmp, d;
i = 0;
while(n>1)
{
d=1;
do
{
tmp=d+1;
swap(&tmp, &d);
}while(n%d);
tmp=(unsigned long int)(n/d);
swap(&tmp, &n);
o[i++]=d;
}
return i;
}
#define MAX_DECOMPOSE 100
_Bool miller_rabin_test(unsigned long int n, int j)
{
_Bool res;
unsigned long int f[MAX_DECOMPOSE];
unsigned long int s, d, a, x, r;
unsigned long int n_1, n_3;
unsigned long int l=0, k;
res = 0;
if(n<=3) return 1;
if(n&1==0)
{
n_1=n-1;
n_3=n-3;
l = decompose(n_1, f);
s=0;
d=1;
for(k=0; k < l; k++)
{
if(f[k]==2)
s++;
else d=d*f[k];
}
while(j-- > 0)
{
a=rand()%n_3;
a+=2;
x=((unsigned long int)pow(a, d))%n;
if(x==1) continue;
r=0;
while(r<s)
{
if(x==n_1) break;
x=((unsigned long int)pow(x, 2))%n;
r++;
}
if(x==n_1) continue;
}
res = 1;
}
return res;
}
Вообщем нашел наконец-то, то что нужно:
http://www.topcoder.com/tc?module=Static&...rimalityTesting