E' utile in pratica un test di primalità in O(k)?

[P_1_6]

E' utile in pratica un test di primalità in O(k)?
A che cosa?
http://www.albericolepore.org/test-di-p ... ici-in-ok/

[Pappappero1]

Ti suggerisco di riscrivere il tuo algoritmo in termini di $G$ (cosi' da eliminare tutte le divisioni che rendono difficile la lettura). Inoltre, potresti imparare due righe di tex, e provare a scrivere il tutto in maniera un pochino piu' chiara.

Comunque, chi e' k? Appare nel titolo della pagina e mai piu' durante l'algoritmo
Il test AKS e' polinomiale nella lunghezza dell'input (quindi in $log(n)$, se $n$ e' il numero del quale vogliamo testare la primalita').

[P_1_6]

Ora l'ho corretto mi potresti dire la complessità gentilmente

[Pappappero1]

La complessita' di cosa? Quello che scrivi non e' un test di primalita'. Se vuoi pensare che lo sia, i conti che fai a occhio hanno bisogno di un numero di operazioni dell'ordine di $\log^3(n)$ (dato dall'algoritmo di euclide, il resto costa meno).

Prendi il tuo caso $n = 6g+1$. Scrivi che se
\[
4g^2 + g \equiv -2 \mod n
\]
allora $n=6g+1$ non e' primo. E se non e' $-2 \mod n$? Dubito che in tutti quei casi il numero in questione sia primo.

Ad esempio per $g = 2$ otteniamo $n=13$, ma $4g^2 + g \equiv_n 18 \equiv_n 5$, dove indico con $\equiv_n$ l'uguaglianza modulo $n$.

Per $g \leq 500$ non ci sono casi in cui $4g^2 + g \equiv -2 \mod n$. Hai dei casi in cui succede? Di cosa stiamo parlando?