Primi in tempo polinomiale - domanda facile - forse

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Primi in tempo polinomiale - domanda facile - forse

Messaggio da Gianfranco »

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 (credo) (https://www.cse.iitk.ac.in/users/manind ... ity_v6.pdf)
AKS_primality.PNG
AKS_primality.PNG (21.49 KiB) Visto 3378 volte
Il primo punto del test 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.
Pace e bene a tutti.
Gianfranco

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Re: Primi in tempo polinomiale - domanda facile - forse

Messaggio da Pasquale »

Uno spunto in Decimal Basic, con tutte le limitazioni del linguaggio, magari da tradurre in altro più conveniente.


Test per verificare se n=a^b interi, entro un limite per n fino a 15 cifre.
Non eseguibile in doppia precisione.
Esempi di numeri trattabili:
999706081460641, 953133216331392, 995009990004999, 995009990004999, 952809757913927, 952809757913927, 952809757913927

INPUT PROMPT "inserisci il valore di n ->":n
PRINT
LET b=1
LET t1=TIME
DO
LET b=b+1
LET a=n^(1/b)
LET k=INT(a)
IF a=k THEN
PRINT n;"=";a;"^";b
EXIT DO
ELSEIF k=1 THEN
PRINT n;"non è una potenza di a^b interi"
EXIT DO
END IF
LOOP WHILE k>1
LET t2=TIME
PRINT
PRINT "tempo impiegato = "; t2-t1
END
_________________

$\text { }$ciao Immagine ciao
E' la somma che fa il totale (Totò)

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Primi in tempo polinomiale - domanda facile - forse

Messaggio da Gianfranco »

Bravo Pasquale!
L'algoritmo è talmente veloce che il risultato è quasi sempre praticamente 0 (centesimi di sec.) - nel range dei numeri trattabili.
Credevo che timer del DECIMAL misurasse i millesimi.
L'algoritmo comunque fa il test in un tempo polinomiale perché esegue al massimo $log_2 n$ cicli do-loop.
Infatti il numero massimo di cicli si ha con i numeri che sono potenze dispari di 2.
Mi è piaciuto!
Pace e bene a tutti.
Gianfranco

Rispondi