0
Я пытаюсь сделать алгоритм RSA. Для этого мне нужно показать rabin-miller + witness + modular exponentiation (по крайней мере, я должен использовать это). Проблема возникает, когда я генерирую случайные числа, чтобы проверять с помощью ранинового мельника, если они являются простыми числами, и в результате нечетные числа являются первичными для алгоритма рабина-мельника. Может кто-нибудь дать мне руку, чтобы увидеть, где я терпеть неудачу. Спасибо заранее.Тест примитивности Миллера-Рабина дает неправильный ответ
int mod_exp(int a, int b, int n){
int d = 1,i,j=0;
int binary[15];
for(i=0;i<=15;i++){
binary[i] = -1;
}
i=0;
do{
binary[i]=(b%2);
if((b%2)==1)
b=(b-1)/2;
else
b=b/2;
i++;
}while(b!=0);
do{
d= (d*d)%n;
if(binary[i]==1)
d=(d*a)%n;
i--;
}while(i!=-1);
return d;
}
bool wittness(int a, int n){
int u=n-1,k=0;
long x, temp;
while(u%2== 0){
u=u/2;
k++;
}
x=mod_exp(a,u,n);
for(int i=1;i<=k;i++){
temp=x;
cout<< "primera x:"<<x<<endl;
x=long(x*x)%n;
cout<< "segunda x:"<<x<<endl;
if(x==1 && temp!=1 && temp != n-1)
return true;
}
if(x!=1)
return true;
return false;
}
bool miller_rabin(int n, int s){
int a,j;
srand(time(NULL));
for(j = 0; j<=s;j++){
a=rand()%s+1;
if(!wittness(a,n))
return false;
}
return true;
}
Я считаю, что это упражнение, а не код, который вы планируете выпустить в реальном продукте? Первое прекрасно; для последнего - просто используйте библиотеку, написанную экспертами! (Вы не можете написать тесты для «эта библиотека небезопасна?») –
Я только что видел, что вы используете «int» - обычно 32 бит. Учитывая, что uint512_t безнадежно небезопасен для RSA, это * четко * «упражнение», а не «производство». –
Я думал, что все уйдут, когда я скажу «(по крайней мере, я должен использовать это)« извините, если вы этого не сделали. Да, это упражнение, и это работает, у меня просто были проблемы с вызовами функций. Спасибо всем тем, кто помогал. – Lolo