Newsgroup: it.comp.sicurezza.crittografia
Titolo: Funzione di Eulero

Dati due primi p e q sia n = pq Sto cercando di capire perch $B&U (B(n) = (p-1)(q-1) ma non ci riesco. Come si procede? Per induzione? Grazie in anticipo. P.S. Ovviamente  $B&U (B(n)  Nh l'insieme di numeri compresi tra 0 ed n coprimi con n.                      Dona i tuoi cicli di clock alla ricerca!                      
http://boinc.berkeley.edu/
                           --------------------            This signature was automatically generated with            Signify v1.14.  For this and other cool products,            check out 
http://www.debian.org/
 

 riesco. Come si procede? Per induzione?
In parole semplici:
poiché p e q sono primi, tutti gli interi positivi inferiori a p sono
coprimi con p, e tutti quelli inferiori ad q sono coprimi con q.
Quindi B(p)=p-1 e B(q)=q-1.
Ora consideriamo n=pq.
p e q sono primi, e quindi coprimi fra loro.
Considerando questo fatto, da quali numeri può essere diviso n?
a) Da n, ovviamente;
b) da p e dai suoi multipli 2p, 3p, ... , (q-1)p;
c) da q e dai suoi multipli 2q, 3q, ... , (p-1)q.
In totale n può quindi essere diviso da 1 + p-1 + q-1 = p+q-1 numeri.
Con tutti gli altri interi inferiori a n, n è coprimo.
Ci sono pq interi positivi inferiori o uguali a n=pq, naturalmente.
Quindi pq è coprimo con pq-(p+q-1) = (p-1)(q-1) interi positivi
inferiori o uguali a n.
Che è come dire che B(pq)=(p-1)(q-1).
--
Bye, Lem

Ghost <Le...@Hotmail.com> writes:

Il fatto che phi(n=pq) = phi(p) · phi(q) è forse un corollario di
questa dimostrazione?
-- 


Ghost <Le...@Hotmail.com> writes:
[...]
Ah, quasi dimenticavo, grazie mille!
-- 
                     Dona i tuoi cicli di clock alla ricerca!
 
http://boinc.berkeley.edu/
                          --------------------
Ora basta parlare di me, parliamo un po' di voi.  Cosa ne pensate di me?
		-- Bette Midler

 Ah, quasi dimenticavo, grazie mille!
Scusami, giglio, ma nello scrivere l'articolo avevo inizialmente fatto
confusione fra n, p e q. Apportate le correzioni, alcune frasi sono
però rimaste clamorosamente errate!
Naturalmente pq non può essere diviso dai multipli di p o di q, come
non si può dividere 35 per 14. np ha, invece, un divisore in comune
con i multipli di p e di q, cioè proprio, rispettivamente, p e q: così
come 35 ha 7 come divisore in comune con 14.
Quindi ci sono p+q-1 interi inferiroi a pq che hanno un divisore in
comune con pq, e quindi che NON sono coprimi con pq. Gli altri (p-1)
(q-1) interi inferiori a pq sono, invece, coprimi con pq, perché non
possono avere con pq divisori comuni.
Se preferisci un linguaggio più tecnico:
sia x un intero 0<x<pq.
Sia il MCD(x,pq)=y. Quindi y|pq (cioè y divide pq) e y|x. Poiché p e q
sono primi, il loro mcm(p,q) è proprio pq. Ciò significa che non ci
sono multipli di p o di q, più piccoli di pq, che dividano pq. y non
può quindi essere un multiplo di p o di q, poiché abbiamo posto x<pq
come condizione, e y deve dividere x.
Allora y è sicuramente coprimo con p e con q. Siccome y|pq, y|p o y|q.
Cioè y deve dividere o p o q, per dividere pq. Ma, essendo p e q
primi, o y è 1 (questi casi c'interesserà contare), oppure y è p (e
allora x sarà p o un multiplo di p inferiore a pq, e abbiamo q-1 casi
possibili), oppure y è q (e allora x sarà q o un multiplo di q
inferiore a pq, e abbiamo p-1 casi possibili).
Quanti sono i casi in cui y=1? Contiamo: x può assumere pq-1 valori,
da 1 (compreso) a pq-1. Di questi:
a) in q-1 casi y=p;
b) in p-1 casi y=q;
c) restano quindi pq-1-[(q-1)+(p-1)]=pq-q-p+1=(p-1)(q-1) casi in cui
y=1. Ecco fatto.
--
Bye, Lem