generator liczb pierwszych

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? :)

w taki sposób nigdy tego nie zrobisz szybko, poszukaj w google: chiński test pierwszości

O, dziękuję za wskazówkę. Ale nadal pozostaje pytanie o wygenerowanie dużych liczb.

Po pierwsze musisz zastosować sprytny generator liczb losowych. Te standardowe są za słabe (mają za dużą powtarzalność i dają małe wartości). Tu ludzi kombinują na różne sposoby (śledzą ruchy myszki, czas systemowy przypadkowy fragment pamięci itd itp).
Potem losujesz liczbę do skutku aż przejdzie chiński test.

Ten chiński test to szczególny przypadek małego twierdzenia Fermata
a^p % p == a spełnione tylko wtedy gdy p jest liczbą pierwszą
to bardzo słaby test, przechodzi go zbyt wiele liczb złożonych
Dla a=2 zdają ten test np. 341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, ....
Znacznie mocniejszy jest test Rabina-Millera
Ale dla 128 bitów lepiej skorzystać z jakiegoś gotowca do wielkich liczb np. mpir albo gmp

Co do twojego testu:
najmniejsza 128 bitowa liczba pierwsza
170141183460469231731687303715884105757
pierwiastek z niej to 13'043'817'825'332'782'212
jeżeli by wykonywać miliard dzieleń na sekundę potrzeba by ponad 200 lat

O, chyba trochę przesadziłem w takim razie z tymi 128 bitami, ale chyba już do 64bitów można zejść? (. A co do małego twierdzenia fermata, to nie brałem w ogóle go pod uwagę ze względu właśnie na liczby Carmichaela.

Taki kombinowany test n<2^62

/*(C)Xitami*/
#include <stdio.h>
#include <stdlib.h>

typedef unsigned long long int umod_t;
typedef signed long long int smod_t;
typedef long double ldouble;

inline umod_t mul_mod(umod_t a, umod_t b, umod_t m){
	umod_t x=a*b;
	umod_t y=m * (umod_t)( (ldouble)a * (ldouble)b/m + (ldouble)1/2 );
	umod_t r = x - y;
	if ( (smod_t)r < 0 ) r += m;
	return r;}

inline umod_t mul_sqr(umod_t a, umod_t m){
	umod_t x=a*a;
	umod_t y=m * (umod_t)( (ldouble)a * (ldouble)a/m + (ldouble)1/2 );
	umod_t r = x - y;
	if ( (smod_t)r < 0 ) r += m;
	return r;}

inline umod_t pow_mod(umod_t a, umod_t e, umod_t m) {
	if ( 0==e ) { return 1; }
	else {
		umod_t z = a;
		umod_t y = 1;
		while ( 1 ){
			if ( e&1 ) y = mul_mod(y, z, m); // y *= z;
			e >>= 1;
			if ( 0==e ) break;
			//z = mul_mod(z, z, m); // z *= z;
			z=mul_sqr(z,m);
		}
		return y;}}

int composite(umod_t n, umod_t r, unsigned s, unsigned a){
	umod_t y=pow_mod(a, r, n);
	if(y == 1 || y == n-1) return 0; //jest złożona 
	while (s>1 && y!=(n-1)){
		y=mul_mod(y,y,n);
		if(y == 1) return 1; // jest pierwsza
		s--;
	}
	if (y != n-1) return 1;
	return 0;
}

#define M(a,b,c,d,N) (mul_mod(a,b,N) + mul_mod(c,d,N))
#define TMUL(a,b,c,d,e,f,g,h,N) {umod_t A=M(e,a,g,b,N), B=M(f,a,h,b,N), \
                                        C=M(e,c,g,d,N), D=M(f,c,h,d,N); \
                                        a= A>=N ? A-N : A; \
                                        b= B>=N ? B-N : B; \
                                        c= C>=N ? C-N : C; \
                                        d= D>=N ? D-N : D;}
 
unsigned int lucas(umod_t n){  // n<2^62
        umod_t xa=1,xb=1,xc=1,xd=0,ra=1,rb=1,rc=1,rd=1, m=n;
        n-=2;
        while(n){
                if(n&1)
                        TMUL(ra,rb,rc,rd,xa,xb,xc,xd,m)
                n/=2;
                if(n==0) break;
                TMUL(xa,xb,xc,xd,xa,xb,xc,xd,m) 
        }
        xa=ra+rb+rb; 
        if(xa>=m) xa-=m;
        if(xa>=m) xa-=m;
	return xa==1;        
}
 
int rab_mil(umod_t n){
const unsigned sp[100]={
	2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,
	79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,
	163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,
	241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,
	337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,
	431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,
	521,523,541};
	
	umod_t r;
	unsigned s;
	for(s=0; s<50; s++)
		if(n%sp[s]==0) return n==sp[s];
	r=n-1; s=0;
	while(!(r&1)){
		r>>=1; s++;
	}
	if (composite(n, r, s, 2)) return 0;
	if(n<4759123141ull) {    // poprawność z gwarancją :)
		if (composite(n, r, s, 7)) return 0;
		if (composite(n, r, s,61)) return 0;
		return 1;
	}
	//jeśli znajdzie się błąd można zarobić parę dolarów
	if (composite(n, r, s, 3)) return 0; 
	return(lucas(n));
} 

to bardzo słaby test, przechodzi go zbyt wiele liczb złożonych

W przypadku małych liczb. Matematycznie jest to niedoskonały sposób, ale...

W przypadku dużych liczb większa jest szansa że promieniowanie z księżyca wpłynie negatywnie na pracę komputera i sprawi że algorytm zwróci błędną wartość niż to że trafimy na liczbę dla której test daje negatywny wynik. A chyba właśnie o dużych (nawet bardzo) liczbach mowa.

Taka ciekawostka.

to chyba najprostsza implementacja owego algorytmu:

 

/* sprawdzanie pierwszosci "losowo" wybranej liczby */
#include <stdio.h>
#include <time.h>

int fermat(void)
{
    int n;
    for( ; ; )
    {
        int a;
        srand((unsigned) time(NULL));
        a = rand();
        n = rand();
    
        if(a > 2 && a < n - 2)
        {
            int r;
            r = pow(a, n - 1);
            r = r % n;
            if(r = 1)
                break;
        }
    }
    return n;
}

int main(void)
{
    int  n;
    n = fermat();
    printf("%d ", n);
    
    system("pause");
}
    

i nadal pozostaje problem generowania dużych liczb, ale już biorę się za gmp, mam nadzieję, że ten algorytm wystarczy :)

@M.zoltowski nie tam srand ;)

@Macron: a to ma znaczenie?

Zasada: srand(time()) wołasz raz na początku main
bo inaczej zamiast rand() możesz napisać sobie np: 123534

a może coś takiego?
x=rand()
while(x<????) x= x<<1 ^ rand();
x|=1;
e.... do chrzanu, liczba będzie wielka, ale wszystkich możliwych tylko RAND_MAX

testowanie pierwszości wynieś do funkcji, kiedyś może będziesz chciał to poprawić

Ogólnie przy projektowaniu bym nie używał srand(time(0)), ponieważ traci się powtarzalność, a jest ona bardzo potrzebna w dobrym przetestowaniu programu. Ogólnie za pomocą kongrugencji liniowej otrzymuje się sensowne liczby losowe, ale do wielu przypadków niewystarczające (o ile dobrze pamiętam to glibc używa tej metody, lub jej niewielkiej modyfikacji w funkcji rand()). Szczególny duży problem jest przy bardzo dużej ilości wywołań (przy rand 10^9) oraz przy próbie złożenia dwóch wartości w celu otrzymania większej liczby losowej.