Domanda Risolto Implementazione radice primitiva

[Carmela bb]

Salve a tutti, ho implementato un programma che consente di capire se un numero inserito da tastiera è una radice primitiva di un numero primo sempre inserito da tastiera.
Io vorrei che l'utente inserisca un valore fin quando quel valore è una radice primitiva e dopo farlo terminare , ma non riesco a capire cosa fare
Vi metto il codice per intero:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

#define N 100
int Euclide(int a, int b);
int calcola (long int a,long int m, int n);

int Euclide(int a, int b) // prototipo della funzione Euclide //
{
    int r;
    while(b != 0) //ripetere finché non riduciamo a zero
    {
         r = a % b;
         a = b;
         b = r; //scambiamo il ruolo di a e b
    }
    return a; //... e quando b è (o è diventato) 0, il risultato è a
}

int calcola (long int a,long int m, int n)
{
    int r;
    int y = 1;
    
    while (m > 0)
    {
        r = m % 2;
        //esponenziazione veloce
        if(r == 1)
        {
            y = (y*a) % n;
        }
        a = a*a % n;
        m = m/2;
    }
    return y;
}
int main(void)
{
    int numero, mcd,j,k;
    long int g,potenza[N],i,x,risultato, ricerca,generatore=0;
    int controllo = 0, controllo1 = 0;
    int f=0;
    int control = 0;
    //Generiamo un numero primo     
    do
    {
        controllo = 0;
        printf("\nGeneriamo un numero\n");
        /*srand(time(NULL));
        numero = rand()%N;
        printf("\nIl numero generato è: %d\n", numero );*/
        printf("\nInserisci un valore: ");
        scanf("%d", &numero);
        for(i=2; (i<numero); i++)
        {
            risultato = numero % i;
            if(risultato == 0 && i!=numero)
            controllo++;
        }
    }
    while(controllo > 0 || numero < 1);
    
    //Generiamo una radice primitiva (generatore)
    do
    {
        printf("\nScegliere un numero minore di %d: ",numero);
        scanf("%ld",&g);
     } while(g > numero);
    for(x=1 ; (x < numero); ++x)
    {
        potenza[x] = calcola(g,x,numero);
        printf("\n %ld elevato %ld mod %d è uguale a % ld\n",g,x,numero,potenza[x]);
    }
        for(x = 1; (x < numero); x++)
        {
        mcd =Euclide (numero, potenza[x]);
        if(mcd == 1)
        {
            for(j=0;(j<numero);j++)
          {
            k=j+1;
            while((k<numero) && (f==0))
            {
                if(potenza[j] == potenza[k])
                {
                    printf("\nelementi uguali trovati: %ld\t%ld\n",potenza[j], potenza[k]);
                        f+=1;
                }
                k++;
            }
         }
         }
         }       
                if(f==0)
                {
                     printf("\nnon ci sono elementi uguali\n");
                            printf("\nIL valore %ld è un generatore\n",g);
                           
                           }
            
}

La parte che io vorrei si ripetesse fin quando non viene trovato il generatore è:

do
    {
        printf("\nScegliere un numero minore di %d: ",numero);
        scanf("%ld",&g);
     } while(g > numero);
    for(x=1 ; (x < numero); ++x)
    {
        potenza[x] = calcola(g,x,numero);
        printf("\n %ld elevato %ld mod %d è uguale a % ld\n",g,x,numero,potenza[x]);
    }
        for(x = 1; (x < numero); x++)
        {
        mcd =Euclide (numero, potenza[x]);
        if(mcd == 1)
        {
            for(j=0;(j<numero);j++)
          {
            k=j+1;
            while((k<numero) && (f==0))
            {
                if(potenza[j] == potenza[k])
                {
                    printf("\nelementi uguali trovati: %ld\t%ld\n",potenza[j], potenza[k]);
                        f+=1;
                }
                k++;
            }
         }
         }
         }       
                if(f==0)
                {
                     printf("\nnon ci sono elementi uguali\n");
                            printf("\nIL valore %ld è un generatore\n",g);
                            generatore ++;
                           }

Per favore aiutatemi, grazie mille anticipatamente

 

[St3ve]

while (f==0) {
    // tutto il codice che hai tu stesso identificato (dal do alla parentesi che chiude l'if)
}

 

[Carmela bb]

Ho risolto diversamente , grazie lo stesso.
Adesso mi sorge un altro problema, supponendo sempre il codice precedente io vorrei che i valori siano calcolati tutti in modo casuale utilizzando quindi rand().
Sostanzialmente sto implementando la radice primitiva perchè mi serve per il Diffie-Helmann che richiede un numero primo abbastanza grande sui 1024 bit, il mio problema è come faccio a far entrare in un array tanti numeri
Non so se mi sono stata abbastanza chiara

 

[St3ve]

Adesso mi sorge un altro problema, supponendo sempre il codice precedente io vorrei che i valori siano calcolati tutti in modo casuale utilizzando quindi rand().

A inizio codice chiami srand(time(NULL)); per impostare il seed del generatore di numeri casuali poi, al posto di ogni input, generi un valore casuale compreso tra max e min con

rand()%(max - min + 1) + min;

Nel tuo caso, puoi fare numero = rand() & 1; per generare un numero casuale dispari e g = rand() % numero; per generare un g inferiore a numero (a questo punto, puoi anche rimuovere il do-while visto che la condizione che verifica è forzata.

Sostanzialmente sto implementando la radice primitiva perchè mi serve per il Diffie-Helmann che richiede un numero primo abbastanza grande sui 1024 bit, il mio problema è come faccio a far entrare in un array tanti numeri

La soluzione più sensata per fare aritmetica con numeri più grandi di 64 bit consiste nell'usare librerie esterne. In questa discussione, tra le altre cose, mostro un esempio di come usare GMP. All'interno di quel codice, trial division serve anche a te. Nel codice di fermat c'è anche l'equivalente della tua funzione calcola (sempre fatto con il repeated squaring).

La soluzione più semplice, ovviamente, è cambiare linguaggio e utilizzare qualcosa che supporta i big numbers in modo trasparente al programmatore.