Curiosità (crittografia, primi, fattoriale)
Lo scrivo in sezione "generale" perché non è un problema e neanche un esercizio; però ho scritto l'argomento tra parentesi in modo che questo post venga aperto da chi è interessato.
Allora, sono quasi due mesi che sto studiando "numeri e crittografia" (anche per questo sono venuto qui poche volte
) una materia davvero interessante anche se complicata almeno per me. Non avevo mai affrontato un corso - seppur parziale - sulla TDN e non credevo che i naturali fossero tanto interessanti e misteriosi.
Comunque si parla di test di primalità e di algoritmo AKS.
Per quanto riguarda l'algoritmo AKS (su wikipedia italiano ci sono tre righe ma su quella inglese 10 volte tanto) esso dimostra che esiste un algoritmo "rapido" per riconoscere i numeri primi (AKS fa in modo che il problema dei primi è in $P$ per chi ha seguito teoria della complessità o informatica teorica o qualcosa di simile). E' un algoritmo molto interessante anche se mi piace di più l'algoritmo probabilistico di Soloway-Strassen.
Il teorema che mi è piaciuto davvero tanto (anche se la dimostrazione inizialmente mi ha fatto penare... poi mi sono accorto che era molto facile e che ero io ad essere ottuso) è il teorema di Wilson.
"Un numero $n$ è primo se e solo se $n$ divide $(n-1)!+1$."
Questo teorema mi ha colpito molto, un po' come il piccolo teorema di Fermat: sono due teoremi molto semplici che fanno pensare come spesso l'eleganza di tanti teoremi della matematica sia proprio nel fatto di essere semplici e concisi.
Purtroppo, però non esiste una formula rapida per il calcolo del fattoriale. Se ci fosse, il "difficile" (per me
) algoritmo AKS creperebbe di invidia di fronte al teorema di Wilson. Ora la mia domanda è "come mai?".
Non si tratta di un "come mai" di quelli che come risposta hanno un "che ne so" oppure un "perché no", il mio "come mai" vuole indagare più a fondo. Il calcolo del fattoriale è una cosa che all'università (dove vado io è così) la danno per scontata, però secondo me dovrebbe avere l'importanza di altri problemi come "la congettura di Goldbach" (che la si vede in tanti corsi differenti).
C'è un'approssimazione del fattoriale che va avanti da almeno 3 secoli: la formula di Stirling. C'è anche la funzione gamma ma, non avendo fatto nessun corso di analisi complessa, non mi inoltro in certi argomenti.
Il mio "come mai" è quindi il seguente. Il calcolo del fattoriale non possiede una formula "rapida", mi chiedo, quindi, se la ragione stia in delle difficoltà oggettive (che non conosco perché ho fatto matematica economica e non mi sono addentrato in molti ambiti di matematica pura!) oppure nel fatto che è un problema a cui non si da il giusto peso oppure per altri motivi che io personalmente non so.
Ciao a tutti
Allora, sono quasi due mesi che sto studiando "numeri e crittografia" (anche per questo sono venuto qui poche volte
) una materia davvero interessante anche se complicata almeno per me. Non avevo mai affrontato un corso - seppur parziale - sulla TDN e non credevo che i naturali fossero tanto interessanti e misteriosi.Comunque si parla di test di primalità e di algoritmo AKS.
Per quanto riguarda l'algoritmo AKS (su wikipedia italiano ci sono tre righe ma su quella inglese 10 volte tanto) esso dimostra che esiste un algoritmo "rapido" per riconoscere i numeri primi (AKS fa in modo che il problema dei primi è in $P$ per chi ha seguito teoria della complessità o informatica teorica o qualcosa di simile). E' un algoritmo molto interessante anche se mi piace di più l'algoritmo probabilistico di Soloway-Strassen.
Il teorema che mi è piaciuto davvero tanto (anche se la dimostrazione inizialmente mi ha fatto penare... poi mi sono accorto che era molto facile e che ero io ad essere ottuso) è il teorema di Wilson.
"Un numero $n$ è primo se e solo se $n$ divide $(n-1)!+1$."
Questo teorema mi ha colpito molto, un po' come il piccolo teorema di Fermat: sono due teoremi molto semplici che fanno pensare come spesso l'eleganza di tanti teoremi della matematica sia proprio nel fatto di essere semplici e concisi.
Purtroppo, però non esiste una formula rapida per il calcolo del fattoriale. Se ci fosse, il "difficile" (per me
) algoritmo AKS creperebbe di invidia di fronte al teorema di Wilson. Ora la mia domanda è "come mai?".Non si tratta di un "come mai" di quelli che come risposta hanno un "che ne so" oppure un "perché no", il mio "come mai" vuole indagare più a fondo. Il calcolo del fattoriale è una cosa che all'università (dove vado io è così) la danno per scontata, però secondo me dovrebbe avere l'importanza di altri problemi come "la congettura di Goldbach" (che la si vede in tanti corsi differenti).
C'è un'approssimazione del fattoriale che va avanti da almeno 3 secoli: la formula di Stirling. C'è anche la funzione gamma ma, non avendo fatto nessun corso di analisi complessa, non mi inoltro in certi argomenti.
Il mio "come mai" è quindi il seguente. Il calcolo del fattoriale non possiede una formula "rapida", mi chiedo, quindi, se la ragione stia in delle difficoltà oggettive (che non conosco perché ho fatto matematica economica e non mi sono addentrato in molti ambiti di matematica pura!) oppure nel fatto che è un problema a cui non si da il giusto peso oppure per altri motivi che io personalmente non so.
Ciao a tutti
Risposte
Un problema rilevante è quello tecnico... se stai seguendo crittografia sai che è importante determinare la primalità di numeri $p$ molto grandi... e $p!$ di questi numeri è un mostro.
Grazie dei link. Quando starò meglio, li guarderò. Non so quando tornerò sul forum dato che sono inchiodato a letto con l'influenza o roba simile (anche se a Giugno fa tristezza beccarsi ste cose!).
"Ganza la NT", eh sì, è proprio vero!
Ciao a tutti
"Ganza la NT", eh sì, è proprio vero!
Ciao a tutti
Ganza la number theory, eh? Se ti interessa approfondire, puoi partire da DJB:
http://cr.yp.to/ntheory.html
http://cr.yp.to/ntheory.html
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo