PRIMI IN TEMPO POLINOMIALE - SOLO IL PUNTO 1
Per gli appassionati di coding.
Qui sotto vedete l'algoritmo AKS (Agrawal-Kayal-Saxena) che permette di stabilire se un numero è primo in un tempo polinomiale.
E' tratto dall'articolo PRIMES in P del 2002 (https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf).
Il primo punto dell'algoritmo consiste nel verificare se il numero dato è una potenza qualsiasi di un altro numero qualsiasi (naturale).
Ecco le mie domande:
a) Come si potrebbe fare per verificare se un numero è una potenza?
b) Sarebbe bello avere anche un programmino per computer che faccia il test.
c) Poi ci vuole anche la verifica che il programma faccia il test in un tempo polinomiale.
Cosa significa? Significa che il tempo impiegato sia proporzionale alla lunghezza della scrittura del numero (e non alla grandezza del numero).
Per esempio: 43046721 è circa 43 volte più grande di 1024 ma la sua scrittura (in base 10) è soltanto 2 volte più lunga, mentre in base 2 il rapporto è 2,5.
...
Tratto dal Forum di BASE Cinque (http://www.base5forum.it/primi-in-tempo-polinomiale-domanda-facile-forse-t7968.html)
...
Pace e bene a tutti!
GfBo
Photo
Shared publiclyView activity
Related Collections