Sulla funzione di eulero

[ludovico1987]

Buon giorno a tutti,scusate la domanda banale ma ho cercato informazioni e non ho trovato nulla a riguardo.Volevo sapere se era stata trovata una formula che indicasse i quanti numeri sono coprimi rispetto un certo numero $ n $ ,senza ricorrere alla conoscenza dei numeri primi coprimi a $ n $.grazie

[vict85]

Se ho capito bene, ti stai chiedendo se esiste una formula per calcolare la funzione \(\phi\) di eulero di un numero. Si esiste. https://it.wikipedia.org/wiki/Funzione_%CF%86_di_Eulero

[ludovico1987]

scusa mi sono espresso male si quella formula la conoscevo volevo sapere se ne esisteva una che non richiedesse la conoscenza dei fattori primi di $ n $ .

[vict85]

Che io sappia no.

[ludovico1987]

ok grazie mille per la risposta

[Pappappero1]

Se questa formula ci fosse, calcolarla sarebbe molto difficile. In sostanza, potenzialmente potrebbe essere della stessa difficolta' di scorrere tutti gli interi da $1$ a $\sqrt{n}$ e verificare se sono coprimi con $n$.

Il motivo per cui dico questo e' il seguente: se $p,q$ sono primi, supponiamo $n =pq$, allora $\phi(n) = (p-1)(q-1)$ ovvero $\phi(n) = pq - p - q +1$. In particolare, conoscendo $n$ e $\phi(n)$ si puo' calcolare economicamente $p+q$ e conoscendo $pq$ e $p+q$ si puo' scrivere un'equazione di secondo grado che ha come radici $p$ e $q$. Riassumendo, conoscendo $n$ e $\phi(n)$ si possono calcolare facilmente $p,q$. Da questo deduciamo che una formula per calcolare $\phi(n)$ deve essere almeno "difficile" quanto calcolare la fattorizzazione.

Nota: La fattorizzazione si congettura che sia un problema $NP$-hard (se bene ci sia un algoritmo quantistico polinomiale). Tuttavia si tratta di una congettura, quindi magari da qualche parte c'e' una formula facile per calcolare $\phi(n)$ che dimostrerebbe che la fattorizzazione e' in $P$. Oppure $P=NP$ e allora un po' tutto diventa facile. :S

[Oshawott277]

Veramente calcolare quanti sono i numeri primi con $n$ é molto semplice... Sono infiniti

(é chiaro che nel messaggio iniziale manca un bel $

Cita

Segnala

[Stickelberger]

@Pappappero

La fattorizzazione si congettura che sia un problema NP-hard

Non e' vero. Cito: "... but factoring is almost undoubtedly not NP-hard."

Si veda questa pagina web di Henry Cohn di Microsoft:
http://research.microsoft.com/en-us/um/people/cohn/Thoughts/factoring.html

[Pappappero1]

Chiedo scusa...mi affidavo a un ricordo di qualcosa che avevo letto su wikipedia tempo fa.

Resta valido il fatto che se fattorizzare e' difficile (con qualche definzione oggettiva di difficile) allora il conticino fatto sopra dimostra che anche calcolare $\phi$ e' difficile.

[Stickelberger]

Si, sono d'accordo. Infatti, quando e' noto $\phi(n)$, e' facile (con GRH o in pratica)
calcolare elementi $a$ nel gruppo moltiplicativo $(ZZ//nZZ)^{\times}$ di ordine $2$.
Se $a!=\pm 1$, allora $mcd(a\pm 1,n)$ sono fattori non banali di $n$.