witam,
implementuje szyfrowanie RSA w C, jednakże natknąłem się na mały problem. Chodzi o generowanie dużych(najlepiej 128 bitowych) liczb pierwszych. Sam napisałem trywialny program, ale wielkość tych liczb mnie nie satysfakcjonuje:
#include <stdio.h>
#include <time.h>
#include <stdbool.h>
bool sprawdzanie_pierwszosci(int n);
int losowanie_p(int p);
int losowanie_q(int q);
int main(void)
{
int p, q;
p = losowanie_p(p);
q = losowanie_q(q);
printf("%d %d", p, q);
system("pause");
}
int losowanie_p(int p)
{
srand(time(NULL));
for( ; ; )
{
p = rand();
if(sprawdzanie_pierwszosci(p))
break;
}
return p;
}
int losowanie_q(int q)
{
srand(time(NULL));
for( ; ; )
{
q = rand() + 1;
if(sprawdzanie_pierwszosci(q))
break;
}
return q;
}
bool sprawdzanie_pierwszosci(int n)
{
int dzielnik;
if (n <= 1)
return false;
for (dzielnik = 2; dzielnik*dzielnik <= n; dzielnik++)
if (n % dzielnik == 0)
return false;
return true;
}
Moja metoda sprawdzania pierwszości nie jest idealna i wiem, że można skorzystać z testu Millera-Rabina, tylko nadal pozostaje problem wylosowania dużych liczb do sprawdzenia. Jakieś pomysły? A może w ogóle zmienić koncepcje zadania? :)