MODULUL 7STRUCTURA GRUPURILOR ABELIENE FINITE

Tema are ca scop prezentarea detaliată a noţiunilor privind grupurile abeliene finite,care stau la baza multor aplicaţii din criptografie precum şi din alte domenii aleinformaticii. Folosind tehnici specifice teoriei grupurilor se obţine o clasificare elegantă şiutilă a grupurilor abeliene finite. În acest context se abordează problema logaritmilordiscreţi.

Studenţii vor întocmi o temă de casă care constă în rezolvarea problemelor şiexerciţiilor propuse.

Cuvinte cheie: grup factor, generator, izomorfisme de grupuri, unităţi ale unui inel,generatori.

Indicaţii de studiere a temei: Timpul minim pe care trebuie să-l acordaţi studierii acestuimodul este de 3 ore.Se citeşte cu atenţie şi se notează ideile principale, ecuaţiile matematice, se aprofundeazănoţiunile subliniate. Se apelează la literatura suplimentară indicată. Se parcurg întrebărilede control şi testele de verificare. Se studiază problemele şi exerciţiile rezolvate. Se rezolvăexerciţiile propuse. Dacă nu se înţeleg rezolvările sau nu pot da soluţii unor problemepropuse se restudiază subiectul în cauză.

Cuprins7.1.Grupul factor; morfisme de grupuri.7.2.Sume directe de subgrupuri.7.3.Grupuri abeliene de ordinul pn.7.4.Generatori ai grupului unităţilor inelului Zn.7.5. Probleme rezolvate.7.6. Teme pentru casă

După parcurgerea şi însuşirea acestei teme, studentul va cunoaşte: Noţiuni de bază privind trecerea la grupul factor; Metode de caracterizare a unui grup abelian finit; Structura grupului unităţilor unui inel şi a unui corp; Generatori ai grupului unităţilor;

7.1. GRUPUL FACTOR; MORFISME DE GRUPURI

Am remarcat că procedura prin care grupul aditiv al numerelor întregi Z este împărţitîn clase de congruenţă modulo n se poate aplica unui grup abelian oarecare folosind unsubgrup al său. În cazul grupurilor finite această împărţire în clase de congruenţă în raport cuun subgrup a condus, printre altele, la teorema lui Lagrange.

Ne vom ocupa în continuare de structura de grup a mulţimii claselor de congruenţă aleunui grup abelian în raport cu un subgrup al său.

Grupul factorFie A un grup abelian, notat aditiv, şi B un subgrup al său. Relaţia de congruenţă

modulo B între elementele lui A se defineşte astfel:

(mod. )x y B x y B .

Se notează A/B mulţimea claselor de echivalenţă corespunzătoare acestei relaţii. Clasaîn care se află elementul x al grupului se notează x şi se defineşte astfel:

{ ; }x x B x b b B .

Oricare din elementele clasei lui x se numeşte reprezentant al acestei clase. Dacă yeste unul dintre aceştia, atunci x = y(mod.B) şi y + B = x + B.

În cazul când A este grupul aditiv Z al numerelor întregi, iar B este subgrupul nZ almultiplilor numărului natural n, congruenţa modulo B este tocmai congruenţa modulo n.Mulţimea claselor Z/nZ a fost notată nZ .

La fel cum se adună clasele modulo n se pot aduna şi clasele lui A modulo B, adicăelementele lui A/B:

x y x y

Deşi clasa sumă se obţine cu ajutorul unor reprezentanţi ai celor două clase rezultatulnu se schimbă dacă se folosesc alţi reprezentanţi din cele două clase. În plus, la fel ca şi încazul adunării din nZ , adunarea definită pe mulţimea A/B a claselor modulo B îndeplineşteproprietăţile grupului abelian. Elementul neutru este clasa lui θ, constituită din elementelesubgrupului B. Clasa opusă clasei reprezentate de x este clasa reprezentată de opusul –x al luix.

Grupul astfel definit, A/B, se numeşte grupul factor al lui A prin subgrupul B. Dacăgrupul A este finit, având n elemente, iar B are m elemente, atunci m este un divizor al lui n şinumărul claselor modulo B este câtul m/n. Deci ordinul grupului grupul factor este m/n.

Funcţia: / ; ( )k A A B k x x

este evident surjectivă şi este un morfism. Acest morfism surjectiv se numeşte surjecţiacanonică definită de subgrupul B.

Morfisme de grupuriFie acum :f A A un morfism de grupuri abeliene finite. Este uşor de verificat că

mulţimea Ker ; ( )f x A f x A

este subgrup al lui A, iar mulţimea

Im ( );f f x x A A

este subgrup al lui A . Primul se numeşte nucleul lui f, iar celălalt se numeşte imaginea lui f.Aceste subgrupuri determină calitatea lui f de a fi injectiv (monomorfism), surjectiv

(epimorfism) sau bijectiv (izomorfism) în felul următor:

estemonomorfism Ker { }esteepimorfism Im

f ff f A

TEOREMĂGrupul factor A/Ker f este izomorf cu Im f. În particular, dacă f este epimorfism, atunci

A/Ker f este izomorf cu A .DEMONSTRAŢIEConsiderăm funcţia:

: / Ker Im ; ( ) ( ) ImA f f x f x f A .

Deşi imaginea prin φ a unei clase de congruenţe modulo B se defineşte folosind unreprezentant x al acestei clase, rezultatul nu se schimbă dacă se foloseşte un alt reprezentant.Într-adevăr,

(mod.Ker ) ; Ker ( ) ( ) ( ) ( )y x f y x z z f f y f x f z f x .

Funcţia φ este un morfism:

( ) ( ) ( ) ( ) ( ) ( ) ( )x y x y f x y f x f y x y .

Funcţia φ este surjectivă, deoarece din definiţia mulţimii Im f, un element din aceastămulţime este de forma ( )f x pentru un x din A. Dar din definiţia lui φ imaginea prin φ aclasei lui x este tocmai ( )f x .

Funcţia φ este monomorfism:Ker ( ) ( ) Kerx x f x x f x ,

unde am notat tot θ elementul neutru al grupului factor A/Ker f. Q.E.D

7.2. SUME DIRECTE DE SUBGRUPURI

Fie a un element al grupului abelian finit A, notat aditiv, şi n un număr întreg oarecare.Dacă n este strict pozitiv, atunci notăm na rezultatul compunerii (adunării) lui a cu el însuşide n ori. Dacă n este strict negativ, atunci na este rezultatul compunerii lui –a cu el însuşi de –n ori. În plus, 0a înseamnă elementul neutru θ al grupului A.

Cu aceste notaţii, dacă numărul natural nenul n îndeplineşte condiţia na , spunemcă n este anulator al elementului a. Evident, ordinul lui a, care este cel mai mic anulator al luia, divide orice anulator.

Anulatorul unei submulţimi a lui A înseamnă un număr care este anulator pentru toateelementele submulţimii. De exemplu, ordinul grupului finit A este anulator al lui A.

Dacă A1, A2,…, Ar sunt subgrupuri ale lui A, atunci spunem că A este suma directă aacestor subgrupuri şi scriem: 1 2 ... rA A A A , dacă orice element a al lui A se scrieîn mod unic sub forma: 1 2 ... ;r i ia a a a a A .

Unicitatea înseamnă că

1 2 1 1 2 2... ; , ,...,r i i r ra a a a a A a a a a a a .

Evident că această condiţie este echivalentă cu unicitatea scrierii lui θ sub formarespectivă, în sensul că

1 2 1 2... ; , ,...,r i i ra a a a A a a a .

EXEMPLUDacă 1 2A A A este produsul cartezian a două grupuri 1A şi 2A , atunci notând:

1 1 1 1 2 2 2 2( , ); , ( , );A a a a A A a a a A

acestea sunt subgrupuri ale lui A izomorfe cu 1A , respectiv 2A şi 1 2A A A .Exemplul prezentat se poate generaliza în sensul propoziţiei care urmează.

PROPOZIŢIEFie A1, A2,…, Ar subgrupuri ale grupului A şi fie 1 2 ... rA A A A . Grupul A

este sumă directă a subgrupurilor A1, A2,…, Ar (se notează 1 2 ... rA A A A ) dacă şinumai dacă funcţia

1 2 1 2: ; ( , ,..., ) ...r rA A x x x x x x este izomorfism.

DEMONSTRAŢIEEvident că funcţia φ este un morfism. Surjectivitatea lui φ înseamnă că fiecare element

din A se poate scrie ca o sumă de r termeni, câte unul din fiecare din cele r subgrupuri.Injectivitatea lui φ este echivalentă cu unicitatea acestei scrieri. QED.

TEOREMĂ

Fie A un grup abelian de ordinul n şi 1 21 2 ... rk k k

rn p p p descompunerea în factoriprimi a lui n. În aceste condiţii, pentru orice i = 1, 2,…, r mulţimea Ai formată din elementelelui A care au drept ordin o putere a lui pi este subgrup al lui A. În plus,

1 2 ... rA A A A .

DEMONSTRAŢIE

Fie , ; ord( ) , ord( )h ki ix y A x p y p . Putem presupune h ≤ k şi atunci:

( )k k k k h hi i i i ip x y p x p y p p x , deci Ai este un subgrup.

A doua afirmaţie o demonstrăm prin inducţie după numărul r de factori primi aiordinului grupului. Evident, teorema este adevărată pentru r = 1.

Presupunând-o adevărată pentru grupuri care au ordinul divizibil prin cel mult r – 1

factori primi distincţi, să notăm: 1 2 11 21 2 1... ;r rk k k k

rrn p p p n p .

Deoarece 1 2( , ) 1n n rezultă că există numerele întregi u şi v astfel că 1 2 1un vn .Notăm A1 submulţimea elementelor lui A care au ca anulator pe n1. Se verifică la fel ca maisus că A1 este subgrup al lui A. Analog, A2.

Orice element x din A se scrie astfel:

1 2 1 2 1 2( )x un vn x un x vn x x x ; 1 1 2 2,x un x x un x .

Dar 2 1 1 2 1 2n x un n x unx x A . La fel se arată că x2 se află în A1. Deci,orice element x din A se poate scrie ca o sumă de termeni, unul din A1, iar celălalt din A2.Această scriere este unică, deoarece dacă 1 2x x cu 1 1 2 2,x A x A , atunci

1 2x x şi

1 1 1 2 1 1 1 1 21 ( ) ( )x x un vn x un x vn x ,

deoarece n1 este anulator pentru x1 şi n2 pentru x2. Rezultă şi 2 1x x .Prin urmare, 1 2A A A , în care A1 are ca ordin pe n1 divizibil prin cel mult r – 1

factori primi distincţi. Deci, A1 se descompune în sumă directă der – 1 subgrupuri, fiecare având ca anulator o putere a unuia dintre numerele prime p1, p2,…,pr.

QED

OBSERVAŢIEDacă un grup este ciclic, atunci cel mai mic anulator al grupului este ordinul său. Dacă

subgrupurile A1, A2,…, Ar sunt ciclice atunci, din teorema chineză, rezultă că şi suma lordirectă (izomorfă cu produsul direct) este ciclic. În general însă, aceste subgrupuri nu suntciclice.

7.3. GRUPURI ABELIENE DE ORDINUL pn

TEOREMĂ

Orice grup de ordinul mn p este o sumă directă de subgrupuri ciclice, toate avândca ordine diverse puteri ale lui p, anume:

1 21 2, ,..., ; ...srr r

sp p p r r r m .

Descompunerea este unică dacă r1 ≥ r2 ≥ … ≥ rs.

DEMONSTRAŢIEDemonstrăm teorema prin inducţie după ordinul grupului A.

Fie x1 un element de ordin maxim 1rp . Grupul factor 1/[ ]A x va avea ordinul strictmai mic decât al lui A şi deci acesta se descompune în sumă directă de subgrupuri ciclice:

1 2 3/[ ] [ ] [ ] ... [ ]sA x x x x ,

în care generatorii au respectiv ordinele r2 ≥ r3 ≥ … ≥ rs.

Pentru fiecare i = 2, 3,…, s vom găsi un reprezentant al clasei lui ix de ordinul irp ,adică de acelaşi ordin cu clasa sa modulo [x1].

Faptul că ordinul lui este irix p înseamnă că 1[ ]ir

ip x x , adică există un număr

natural k astfel încât 1ir

ip x kx . Putem presupune 1rk p , deoarece 1rp este ordinul lui

1x , deci şi anulatorul lui 1x . Numărul k se poate scrie sub forma rk p t în care p nu estedivizibil cu p. Evident, r ≤ r1.

Ordinul lui tx1 este egal cu ordinul lui 1x , deoarece t este prim cu ordinul lui 1x .

Rezultă că ordinul lui 1 1rkx p tx este 1r rp . Aşadar ordinul lui 1

irip x kx este 1r rp .

Deci, ordinul lui ix este 11i ir r r rr rp p p . Dar din maximalitatea lui r1 rezultă ri + r1 – r≤ r1, adică r – ri ≥ 0.

Relaţia 1ir

ip x kx devine: 1 1 sau ( )i i i i ir r r r r r ri ip x p p tx p x p tx de

unde rezultă că ordinul lui 1ir r

ix p tx este cel puţin egal cu irp . Dar ordinul (în A) al lui

1ir r

ix p tx nu poate depăşi ordinul clasei sale modulo [x1], care este irp . Deci, ordinul lui

1ir r

ix p tx este irp .

Putem deci presupune că ordinul lui ix este irp pentru i = 2, 3,…, s. Vom arăta că

1 2[ ] [ ] ... [ ]sA x x x .Pentru orice element x din A avem:

1 2 3 2 2 3 3

2 2 3 3 1 1 1 1 2 2 3 3

/[ ] [ ] [ ] ... [ ] ...... [ ] ...

s s s

s s s s

x A x x x x x k x k x k xx k x k x k x k x x x k x k x k x k x

în care se poate lua irik p , deoarece ix are ordinul irp .

Rămâne să arătăm că scrierea lui x este unică. Dar dacă avem1 1 2 2 ... s sk x k x k x atunci, aplicând surjecţia canonică, obţinem:

2 2 3 3 ... s sk x k x k x , de unde rezultă 1 20, 0,..., 0sk k k . Înlocuind în relaţia

1 1 2 2 ... s sk x k x k x obţinem 1 1k x . QED

EXEMPLUOrice grup de ordinul 8 = 23 este izomorf cu unul din următoarele trei grupuri:

8 4 2 2 2 2, ,Z Z Z Z Z Z

din care numai primul este ciclic.

7.4. GENERATORI AI GRUPULUI UNITĂŢILOR INELULUI Zn

În această secţiune dăm răspuns la următoarea întrebare: pentru care valori ale lui ngrupul al unităţilor inelului Zn este un grup ciclic.

Cazul când modulul n este număr primTEOREMĂPentru orice număr prim p grupul este ciclic.

DEMONSTRAŢIEGrupul are ( ) 1p p elemente şi deci ordinele elementelor grupului sunt

divizori ai lui 1p . Fie d un astfel de divizor. Elementele de ordinul d sunt rădăcini ale

polinomului 1dX , iar acest polinom are cel mult d rădăcini, deoarece inelul Zp este corp.În cazul când există un element de ordinul d, fie acesta x, atunci rădăcinile

polinomului 1dX vor forma un subgrup ciclic constituit din elementele: 2, ,..., 1dx x x care sunt distincte. Elementele de ordin d ale acestui subgrup ciclic sunt în număr de ( )d , şianume: sunt acele puteri ale lui x care au exponentul prim cu d. Elementele de ordinul d alegrupului fiind printre aceste puteri, rezultă că: dacă există un element de ordinul d, atuncinumărul acestora este ( )d .

Deci pentru fiecare divizor d al lui 1p numărul elementelor de ordinul d este( )o d care este fie zero, fie ( )d . Evident că:

( 1)

( ) 1d p

o d p

.

Pe de altă parte:

( 1)

( ) 1d p

d p

.

Deoarece 0 ( ) ( )o d d , rezultă că pentru fiecare divizor d al lui 1p trebuie ca( )o d să fie egal cu ( )d .

În particular, pentru 1d p , ( 1) ( 1)o p p care fiind nenul, există cel

puţin un element de ordinul 1p al grupului Zp8 şi deci acest grup este ciclic.

QED

Cazul când n este puterea unui număr prim

Subcazul când p este impar

În continuare vom extinde rezultatul la valorile lui n de forma: rn p în care r esteun număr natural oarecare, iar p este un număr prim impar, adică diferit de 2.

Vom începe cu unele fapte de analiză combinatorie.

LEMAPuterea maximă a numărului prim p care divide produsul k! este:

2 3( ) ...kk k kE pp p p

în care parantezele drepte indică partea întreagă a numărului cuprins între ele.

DEMONSTRAŢIEÎn produsul k! numărul factorilor multipli ai lui p este partea întreagă a câtului lui k

prin p. Când calculăm puterea lui p cuprinsă în k! trebuie să adăugăm numărul factorilordivizibili cu p2, care este partea întreagă a câtului dintre k şi p2 etc.

QED

LEMAOricare ar fi numărul prim impar p şi numărul natural k ≥ 2 avem:

( )2kkE p

DEMONSTRAŢIE

2 3 2 3

2

( ) ... ...

1 1 1 1 ... 1 1 21

kk k k k k kE pp pp p p p

k k k kp p p pp

p

QED

TEOREMĂ

Pentru orice număr natural r şi număr prim impar p grupul *Z rp este ciclic.

DEMONSTRAŢIE

Deoarece grupul *Zp este ciclic există un număr x a cărui clasă modulo p generează

acest grup. Din teorema lui Fermat numărul p divide diferenţa 1 1px , adică 1 1px tp .Considerăm două cazuri: dacă t nu este divizibil prin p, atunci luăm y = x; dacă t este divizibilprin p, adică 1 21px t p , atunci luăm (1 )y p x . Evident că în acest din urmă caz

numărul y se află în aceeaşi clasă modulo p ca şi x, deci clasa sa generează grupul *Zp . În plus,observăm că:

1 2 2 21 11 1 ( 1) ... 1 1 ... 1p

p pp p p C p p p C p sp ,

în care s nu este divizibil prin p. Ca urmare,

11 1 2 21 (1 )(1 ) 1 1pp py p x sp t p p s t p st p ph ,

unde h nu este divizibil cu p, deoarece p nu este multiplu de p. Aşadar în ambele cazuri existăun număr y a cărui clasă modulo p generează grupul *Zp şi 1 1py hp în care h nu estedivizibil cu p.

Vom arăta că numărul y modulo pr generează grupul *Z rp . Fie m un număr natural

astfel că 1 modm ry p , adică pr divide diferenţa 1my . Rezultă atunci că şi p divide

această diferenţă, adică 1 modmy p şi deoarece clasa lui y generează grupul ciclic *Zp ,

care are ordinul 1p înseamnă că 1p divide m, adică ( 1)m p l . Prin urmare:

( 1) 1 2 2 2

3

(1 ) 1llm p l p l k k k

l lk

y y y hp l hp C h p C h p

.

În această dezvoltare termenul al doilea conţine factorii l şi p, iar al treilea conţinefactorii l şi p2. Deoarece h nu este divizibil prin p înseamnă că al treilea termen conţine oputere strict mai mare a lui p decât al doilea. Aceeaşi proprietate o au şi termenii următori,deoarece:

( 1)( 2)...( 1)!

kk k k kl

pC h p l l l l k hk

,

de unde se vede că pentru k ≥ 3 acest termen conţine factorul l, iar din lema precedentă

puterea lui p care divide fracţia!

kpk

are exponentul cel puţin egal cu3

2 2 2k kk . Acest

exponent fiind număr întreg este deci cel puţin egal cu doi.Rezultă că diferenţa 1my care este divizibilă prin pr are un termen care conţine o

putere a lui p strict mai mică decât toţi ceilalţi. Prin urmare, acest termen trebuie să fiedivizibil cu pr şi deci l este divizibil prin 1rp . Înseamnă că exponentul ( 1)m p l este

divizibil cu 1( 1)rp p , care este ordinul grupului *Z rp . Deci acest grup este ciclic. QED

CONSECINŢĂ

Dacă 2 rn p în care p este număr prim impar, atunci grupul *Zn este ciclic.

Într-adevăr, grupul *2

Z rp este izomorf cu * *2Z Z rp , iar acesta din urmă este izomorf

cu *Z rp , deoarece grupul *2Z are un singur element. Ca urmare, grupul *Z rp fiind ciclic,

rezultă că şi *2

Z rp este ciclic.

Subcazul p = 2Pentru r = 1 şi pentru r = 2 acest grup este ciclic. Vom arăta că pentru

r ≥ 3 acest grup nu este ciclic.

TEOREMĂDacă r ≥ 3, atunci:I. Toate elementele grupului *

2Z r au ordinul cel mult egal cu 22r . Ca urmare, grupul

nu este ciclic, deoarece ordinul său este 1(2 ) 2r r .

II. Subgrupul generat de clasa numărului 5 are ordinul 22r şi este constituit dinclasele modulo 2r reprezentate de numerele de forma 4k + 1.

DEMONSTRAŢIE

Orice element din grupul *2

Z r este reprezentat de un număr impar care se poate scrie

sub forma 4 1x k . Observăm că:

1 0 2 1

3 2 2

2 22 2 3 2 2 4

1 22

2 2 5 23 2

2 1, 2 1,

2 1,..., 2 1,r r

r

x x h x x h

x x h x h

ceea ce demonstrează prima afirmaţie.Pentru a doua afirmaţie a teoremei, fie m un număr natural astfel că 5m = 1 modulo 2r,

adică 2r divide diferenţa 5m – 1. În dezvoltarea:2 2 2 4 3 65 (1 2 ) 1 2 2 2 ...m m

m mm C C

termenul al doilea conţine ca factor pe 2 la putere strict mai mică decât următorii. Ca urmare,pentru ca 5m – 1 să fie divizibil cu 2r este necesar ca m să fie divizibil cu 22r , deci ordinulclasei lui 5 este 22r .

QED

Cazul generalTEOREMĂ

Grupul *Zn este ciclic numai dacă: n = 2, n = 4, n = pr, n = 2pr, în care p este unnumăr prim impar.

DEMONSTRAŢIE

S-a demonstrat mai înainte că *Zn este ciclic dacă n = pr sau n = 2pr în care p estenumăr prim impar şi că nu este ciclic dacă n = 2r; r ≥ 3.

Să arătăm că în toate celelalte cazuri grupul *Zn nu este ciclic.

Fie 1 21 2 ... krr r

kn p p p descompunerea în factori primi a lui n, în carek ≥ 2, iar dacă unul din factorii primi este 2, atunci exponentul său este strict mai mare ca unu.

Deoarece 1 21 2

şi ...krr r

kp p p sunt prime între ele, rezultă că:

r1 321 2 3

* * *p ...

Z este izomorf cu Z Z r rr kk

n p p p .

Din formula de calculare a caracteristicei lui Euler rezultă că ordinele celor douăgrupuri ce alcătuiesc produsul direct sunt numere pare, deci au ca factor comun pe 2. Dinreciproca teoremei chineze rezultă că acest produs direct nu este un grup ciclic.

QED

Generatori ai unui grup ciclicCând lucrăm cu un grup ciclic ne interesează să avem un generator al acestuia. Fie G

un astfel de grup, notat multiplicativ, de ordinul n.Dacă se cunoaşte un generator g al grupului, atunci putem determina toţi generatorii

grupului: sunt elementele de forma kg , în care k este un număr natural mai mic decât n şiprim cu n. Numărul acestora este egal cu ordinul φ(n) al grupului unităţilor inelului nZ .

Dacă 1 21 2

1 2

( ) 1 1 1... , atunci 1 1 ... 1rk k kr

r

nn p p pn p p p

este

proporţia generatorilor în mulţimea G, adică probabilitatea ca alegând la întâmplare unelement al lui G, acesta să fie un generator. Se observă că această probabilitate nu depinde deexponenţii k1, k2,…, kr, ci numai de factorii primi distincţi p1, p2,…, pr ai lui n.

În cazul când nu cunoaştem nici un generator al grupului şi vrem să obţinem unul,alegem la întâmplare un element al grupului şi verificăm dacă este un generator. Cuprobabilitatea menţionată mai înainte el va fi un generator.

Pentru a verifica dacă un element x din G este generator ar trebui să calculăm puterilelui x până la puterea n – 1 şi să constatăm că nici una nu este egală cu elementul neutru algrupului.

Ţinând seamă de teorema lui Lagrange, este suficient să verificăm acest lucru numaipentru acei exponenţi care sunt divizori proprii ai lui n, deoarece exponentul cel mai mic, e,pentru care ex este elementul neutru al grupului G este ordinul elementului x.

Putem să reducem şi lista acestor exponenţi (constituită din divizorii proprii ai lui n)

limitându-ne la cei maximali, adică ; 1,2,...,ii

nd i rp .

Într-adevăr, pentru orice divizor propriu d al lui n există cel puţin un indice

i = 1, 2,…, r pentru care ikip nu divide pe d. Rezultă atunci că d divide pe di, care este cel

mai mare divizor propriu al lui n care nu este divizibil prin ikip . Ca urmare, dacă dx este

elementul neutru al lui G, atunci la fel va fi şi idx .În concluzie, pentru a verifica dacă x este generator al grupului G, se calculează

elementele: 1 2, ,..., rd d dx x x şi dacă toate aceste sunt diferite de elementul neutru al grupuluiG, atunci x este generator.

EXEMPLU. Grupul *29Z al unităţilor corpului claselor de resturi

modulo 29 are n = 28 = 22·7 elemente, iar divizorii proprii maximali ai lui n sunt: d1 = 4, d2 =14.

Pentru a verifica dacă x = 2 modulo 29 este generator folosim algoritmul exponenţieriimodulare, efectuând în acest scop ridicări succesive la pătrat:

0 1 2 32 2 2 2 2 2 22, 2 4, 4 16, 16 5x x x x x ,

de unde rezultă: 1 24 14 8 4 22 16 1, 2 2 ( 5) 16 4 1 1d dx x , decix = 2 este generator.

Pentru x = 5 avem:0 1 2 32 2 2 2 2 2 25, 5 4, 4 16, 16 5x x x x x ,

de unde rezultă: 1 24 14 8 4 25 16 1, 5 5 ( 5) 16 ( 4) 1d dx x şi decix = 5 nu este generator.

7.5. PROBLEME REZOLVATE

7.5.1. Să se determine toate tipurile de grupuri abeliene de ordinul 360.Rezolvare

Din descompunerea 360 = 23.32.5 deducem că orice grup A de ordinul 360 esteizomorf cu produsul cartezian a trei grupuri:

în care A2 este un grup de ordinul 23, A3 este un grup de ordinul 32, A5 este un grup de ordinul5.

Ultimul, A5, este izomorf cu Z5 deoarece ordinul 5 este număr prim. Al doilea, A3, de

ordinul 9, este izomorf fie cu Z3⊕Z3 fie cu Z9. Primul, este izomorf fie cu Z2⊕ Z2⊕ Z2, fiecu Z2⊕Z4, fie cu Z8.

Prin urmare sunt 6 tipuri neizomorfe de grupuri de ordinul 360 şi anume:Z360, Z120⊕Z3, Z90⊕Z4, Z180⊕Z2, Z30⊕Z12, Z30⊕Z6⊕Z2

7.5.2. Să se determine grupul unităţilor şi un sistem minimal de generatori pentru inelele:a) Z37; b) Z27; c) Z38; d) Z63.

Rezolvare.a). Deoarece 37 este număr prim înseamnă că grupul , care are 37 – 1 = 36

elemente, este un grup ciclic, adică este izomorf cu Z36.Un generator al acestui grup nu se poate găsi decât luând la întâmplare un generator şi

verificând că puterile sale, până la 36 sunt distincte (orice element ridicat la puterea 36 esteegal cu 1 modulo 37, potrivit teoremei lui Fermat).

Ţinând seamă de teorema lui Lagrange, pentru a verifica dacă 2 este generator nu estenevoie să calculăm toate puterile lui 2 ci numai cele având ca exponent divizorii maximali ailui 36. Aceşti divizori maximali sunt 12 = 36/3 şi 18 = 36/2.

Avem: 23 = 8, 26 = 64 = 27 = -10 (mod.37), 212 = 100 = 26 (mod 37), deci 212 ≠ 1(mod 37). Mai departe, 218 = 212.26 = 26.(-10) = -260 = -1 (mod 37), deci 218 ≠ 1(mod 37).

Aşadar, 2 este un generator al grupului , adică ridicând pe 2 la puteri succesiveobţinem toate cele 36 elementele ale acestui grup.

Grupul ciclic , izomorf cu Z36, are şi alţi generatori şi anume toate puterile lui 2care au ca exponenţi numere prime cu 36. Numărul acestora este egal cu caracteristica luiEuler, adică: φ(36) = φ(22.32) = φ(22).φ(32) = 2(2-1).3(3-1) = 12.

b). Deoarece 27 = 33 este putere a unui număr prim rezultă că , este tot grup ciclic.Elementele acestui grup sunt clasele reprezentate de numerele prime cu 27. Numărul acestora

este φ(33) = 32(3-1) = 18. Deci grupul este grup ciclic având 18 elemente, adică esteizomorf cu Z18. Divizorii maximali ai lui 18 sunt 6 şi 9.

Clasa lui 2 se află în acest grup (deoarece 2 este prim cu 27) şi verificăm dacă 2 estegenerator. Avem: 23 = 8, 26 = 64 = 10(mod.27), deci 26 ≠ 1(mod.27). Mai departe, 29 = 26.23

= 10.8 = 80 = -1 (mod.27), deci şi 29 ≠ 1(mod.27). Rezultă că 3 este un generator.Ceilalţi generatori sunt puterile lui 3 având drept generatori numere prime cu 18.

Numărul acestora este φ(18) = φ(2.32) = φ(2).φ(32) = (2-1).3(3-1) = 6. Putem să precizămaceşti generatori: 21 = 2, 25 = 32 = 5(mod.27), 27 = 20, 211 = 25.25.2 = 50 = 23 = -4(mod.27),213 = 211.22 = -4.4 = -16 = 11(mod.28), 217 = 213.24 = 11.16 = 14(mod.27).

c). Deoarece 38 = 2.19, adică este de forma 2.pr înseamnă că grupul este iarăşiciclic, numărul elementelor acestui grup este φ(38) = φ(2.19) = φ(2).φ(19) = (2-1)(19-1) = 18.Deci grupul este izomorf cu Z18. Divizorii maximali ai lui 18 sunt 6 şi 9.

Verificăm dacă 3 este generator. 33 = 27 = -11(mod.38), 36 = 121 = 7(mod.38), deci 36

≠ 1(mod.38). Mai departe, 39 = 36.33 = 7.27 = 37 = -1(mod.38), deci 29 ≠ 1(mod.38).Înseamnă că 3 este generator.

Se pot preciza şi ceilalţi generatori, adică puterile lui 3 care au ca exponent numereprime cu 18.

d). Deoarece 63 = 7.32 rezultă că grupul ciclic nu este grup ciclic. Numărulelementelor acestui grup este φ(63) = φ(7.32) = φ(7).φ(32) = (7-1).3.(3-1) = 36.

Din clasificarea grupurilor abeliene de ordinul 36 = 22.32 rezultă că grupuleste izomorf cu unul din următoarele subgrupuri: Z36, Z12⊕Z3, Z18⊕Z2, Z6⊕Z6.

Primul este exclus, deoarece, aşa cum am menţionat, grupul nu este ciclic. Aldoilea este caracterizat prin faptul că are un element de ordinul 4, al treilea are unelement de ordinul 9 iar ultimul nu are nici elemente de ordinul 4 nici de ordinul 9.

Folosind o aplicaţie (de exemplu Excel) se găseşte faptul grupul nu are nicielemente de ordinul 4 nici de ordinul 9. Prin urmare grupul este izomorf cu Z6⊕Z6.

7.5.3. Problema logaritmilor discreţi. Fie p un număr prim şi g un generator algrupului ciclic . Problema logaritmilor discreţi înseamnă să se rezolve ecuaţia gx =apentru orice a din . Această problemă se poate pune pentru orice grup ciclic.

Ne propunem să rezolvăm problema logaritmilor discreţi pentru .

RezolvareMai întâi găsim un generator al grupului . Divizorii maximali ai lui 40 sunt 8 şi

20. Se obţine: 78 = -4 ≠ 1(mod.41) şi 720 = -1 ≠ 1(mod.41), deci 7 este un generator algrupului .

Este suficient, în continuare, să rezolvăm ecuaţia 7x = a pentru numerele a caresunt prime şi mai mici decât 40.

În plus, deoarece 720 = -1 rezultă că log7(-1) = 20, deci este suficient să calculămlog7a pentru valorile lui a mai mici decât 20.

Din 72 = 49 = 8(mod.41) rezultă că log78 = 2, adică 3.log72 = 2, de unde, log72 =2.3-1(mod.40), adică log72 = 14.

Din log7(-1) = 20 şi -1 = 40 = 8.5 rezultă: 20 = log7(-1) = log740 = log78.5 ==log78 + log75 = 2 +log75 şi deci log75 = 20 – 2 = 18.

Din 75 = -3 rezultă log73 = log7(-75) = log7(-1) + log775 = 20 + 5 = 25.Din 11 = -30 rezultă: log711 = log7(-30) = log7(-1) + log72 + log73 + log75 = 20

+ 14 + 25 + 18 = 37(mod.40)Din 13 = -28 rezultă log713 = log7(-28) = log7(-1) + log74 + Log77 = 20 + 2.14 +

1 = 29(m0d.40).Din 17 = -24 rezultă log717 = log7(-24) = log7(-1) + log73 + log78 = 20 + 25 +

3.14 = 7.

Din 19 = -22 rezultă log719 = log7(-22) = log7(-1) + log72 + log711 = 20 + 14 +37 = 31(mod.40).

7.6. TEME PENTRU CASĂ7.6.1. Să se determine toate tipurile de grupuri abeliene de ordinul: 6, 9, 12, 24,25, 27, 32, 36, 72, 324.7.6.2. Să se determine grupul unităţilor şi un sistem minimal de generatori pentru inelele:

a) Z11; b) Z25; c) Z81; d) Z50, e) Z15, f) Z28, g)Z45.7.6.3. Să se rezolve problema logaritmilor discreţi pentru:

a) , b) , c) ,d) .

Bibliografie[1] C. DOCHIŢOIU, Instrumente algebrice ale criptografiei, Editura ATM, Bucureşti, 2009.[2] N. KOBLITZ, A Course in Number Theory and Cryptography, Editura Springer, Berlin,1988[3], by A. MENEZES, P. van OORSCHOT, and S. VANSTONE, Handbook of AppliedCryptography, CRC Press, 1996.