PDA

Visualizza la versione completa : Numeri primi grandi (1024bit)


LordSaga640
28-07-2004, 20:57
Ciao, come da subject.
Mi serve una formula per avere numeri random primi a 1024bit.

Grazie in anticipo.

LordSaga640
28-07-2004, 22:54
diciamo che mi basta un algoritmo di primalità semplice.


Mi servirebbe per l'rsa

LordSaga640
28-07-2004, 23:17
l'ho trovato!!

grazie lo stesso

http://digilander.libero.it/crittazione/6.htm

unomichisiada
29-07-2004, 02:15
Si però l'algoritmo del link non ti da la certezza della primalità,ne esiste uno chiamato setaccio di eratostene che te la da questa certezza anche se al momento non lo ricordo a memoria,lo devo cercare.Se ti interessa te lo posto.Ovviamente la velocità di calcolo non sarà la stessa di quello del link,specialmente al crescere del numero

LordSaga640
29-07-2004, 11:38
Ciao, bhè, ti ringrazio in prima cosa.

Se non ti scoccia io accetto il tuo piacere.


CMQ io continuo a cercare su google cme sempre.

Generalmente mi affido al forum solo quando, dopo tante ore trovo poco o nulla.

grazie ^^

iguana13
29-07-2004, 12:06
Ti conviene cercare "algoritmo AKS" perchè, anche se è complicato, garantisce alte prestazioni soprattutto con un input elevato.

unomichisiada
29-07-2004, 13:01
Invece del setaccio di Eratostene ho deciso di postarti quest'altra tecnica basata
sul LEMMA DI FIBONACCI,il setaccio infatti ha bisogno di utilizzare un array di n
elementi come appoggio e non mi piace tanto (se n è grande non è il massimo).

------------------------------------------------------------------------------
LEMMA DI FIBONACCI

Sia n un intero (supponiamo positivo ma per i negativi prendiamo il modulo),
il PIU' PICCOLO dei fattori primi di n,chiamiamolo p(i),soddisfa la relazione:

p(i) <= parte_intera _inferiore(radice_quadrata(n))
------------------------------------------------------------------------------
Se ti interessa ti posto la dimostrazione,altrimenti fidati.
Il lemma in pratica ci dice che se c'è un fattore di n (e quindi n non è primo)
esso è minore o uguale alla parte intera inferiore della radice quadrata di n
altrimenti si contraddice il lemma (che però è dimostrato e quindi vero).Infatti
ammettendo per assurdo che prima della parte intera inferiore della radice non si trovino
fattori, e se ne trovi uno subito dopo,questo sarebbe il primo,contraddicendo
l'affermazione che il primo sia più piccolo della parte intera inf.....
Da cui il semplice algoritmo che controlla se tra quelli prima del suddetto limite
c'è un numero che divide esattamente n oppure no.
Nota che anche per n pari ad 1.000.000 ,l'algoritmo vien eseguito al più in 1000 passi circa
(solo se n è primo) quindi è abbastanza buono.





#include <stdio.h>

#define TRUE 1
#define FALSE 0

typedef unsigned char BOOL;

BOOL isPrime(int n);

main()
{
int m,i;
do
{
printf("Introduci un intero positivo:");
scanf("%d",&m);
if(m<1)
printf("Un intero POSITIVO!!!\n");
}while(m<1);
printf("I numeri primi da 1 a %d:\n\n",m);
for(i=1;i<=m;i++)
if(isPrime(i))
printf("%d ",i);

//non far caso a queste due istruzioni
fflush(stdin);
getchar();

}

//Ritorna vero se n è primo e falso
//altrimenti
BOOL isPrime(int n)
{
int p;
int limit = (int)sqrt(n);
for(p=2;p<=limit;p++)
if(n % p == 0) //controlla se è divisibile
return FALSE;
return TRUE;
}

unomichisiada
29-07-2004, 13:13
Ti conviene cercare "algoritmo AKS" perchè, anche se è complicato, garantisce alte prestazioni soprattutto con un input elevato.
Ho dato uno sguardo veloce all'algoritmo AKS e da quanto ho capito (la lettura è stata mooolto veloce quindi c'è una possibilità che possa sbagliarmi) usa lo stesso criterio probabilistico dell'algoritmo indicato nel link che l'autore del 3d ha postato,perciò non da la certezza della primalità,d'altra parte però per numeri molto grandi non bisogna aspettare il tempo di vita dell'universo con quello :fagiano:

LordSaga640
29-07-2004, 13:31
Dopo questa ricerca sui numeri primi ho capito che la matematica non l'ha inventata l'uomo.

L'uomo la sta solo scoprendo piano piano. :D


Grazie dell'aiuto. Sto trovando parecchie cose interessanti.

Ciao ^^

unomichisiada
30-07-2004, 11:44
Ho dato uno sguardo veloce all'algoritmo AKS e da quanto ho capito (la lettura è stata mooolto veloce quindi c'è una possibilità che possa sbagliarmi) usa lo stesso criterio probabilistico dell'algoritmo indicato nel link che l'autore del 3d ha postato,perciò non da la certezza della primalità,d'altra parte però per numeri molto grandi non bisogna aspettare il tempo di vita dell'universo con quello


Mi sbagliavo (la lettura era effettivamente troppo veloce),AKS da la certezza della primalità anche se ha una complessità polinomiale dell'ordine di n^12 con n numero di cifre.Però è veramente complesso come algoritmo.

Loading