Algoritmi - Algoritmo numeri primi

Mi sembra tu stia parlando del suo Crivello, giusto? Ho preferito partire con uno script più intuitivo. Piuttosto cosa c'entrano con la crittografia asimmetrica (mi sa)?

Esatto, l'algoritmo di Eratostene è noto come "Crivello di Eratostene" e l'applicazione della sua tecnica ha dato il via alla nascita di molti altri algoritmi più avanzati denominati in genere "Crivelli".

Per arrivare alla crittografia asimmetrica ci sono sono parecchi teoremi di algebra da studiare.

In poche parole ci sono alcuni algoritmi (come lo storico e ormai superato RSA) che si basano sulla moltiplicazione di grandi numeri primi (da migliaia di cifre). La moltiplicazione è un processo molto veloce (complessità polinomiale rispetto al numero di cifre), mentre la fattorizzazione è estremamente lenta (complessità esponenziale).
Basandosi sulla differenza di complessità tra due operazioni inverse è possibile costruire algoritmi in cui i numeri primi sono le chiavi segrete, mentre il loro prodotto costituisce la chiave pubblica.

Altri algoritmi simili sono ad esempio quello di El Gamal che sfrutta i logaritmi discreti in un gruppo Zn con n primo molto grande. Poi ci sono algoritmi su curve ellittiche e altri che non si basano sui primi ma sfruttano comunque la differenza di complessità tra un algoritmo ed il suo inverso.

Questa roba si studia in matematica discreta e teoria dei numeri, roba medio-avanzata che potrai incontrare all'università se sceglierai un indirizzo informatico o matematico.

Salve, vorrei porvi una domanda da niubbo..

Io per stabilire se un numero è primo mi affido alla formula già collaudata di dividere il numero per tutit i numeri da 2 alla radice quadrata dello stesso e vedere se il resto è 0

Il fatto è che non ho la benché minima idea di perchè si utilizza la radice quadrata del numero come cap limite massimo... E' grave??
Voi riuscite a capirci la logica?

Evidentemente è stato dimostrato che sotto quel limite è inutile scendere

non ti faccio la dimostrazione matematica perchè senza carta e penna non riesco

Comunque sì, è facilmente dimostrabile che un numero se ha un divisore maggiore della sua radice, allora ha anche un altro divisore che è minore e quindi l'avrai già trovato durante l'iterazione.

Ad esempio 26 si divide in 13 (che è maggiore della sua radice) e 2 (che è minore).

Una volta scoperto il 2, si fa 26 / 2 = 13 e si itera sul 13.

La radice di 13 è 3,xxxx quindi ci si ferma al 3 per lo stesso motivo di prima.