## 14.6A Euler en Fermat

Inhoud van de pagina Euler en Fermat:
EF.1 De Eulerindicator
EF.2 Somregel en productregel
EF.3 Een regel voor φ(pr)
EF.4 De stelling van Euler
EF.5 De kleine stelling van Fermat

EF.1 - De Eulerindicator

Leonhard Euler (1707-1783) wordt beschouwd als de belangrijkste wiskundige van de achttiende eeuw en is de wiskundige die het meest gepubliceerd heeft. Zijn verzameld werk beslaat zo'n zeventig delen. Euler heeft onder andere de symbolen e, i, en de goniometrische functies sinus, cosinus en tangens geïntroduceerd.

Beroemd is zijn vergelijking waarin de bijzondere getallen 0, 1, e, i en verenigd zijn.

In deze paragraaf zullen we de stelling van Euler bekijken die ons goed van pas komt als we naar wat moderne cryptosystemen gaan kijken. De stelling van Euler gaat over machtsverheffen en maakt het rekenen met grote machten eenvoudiger.

Op de hoofdpagina van les 14 hebben we het getal K gedefinieerd als het aantal priemdelers van een getal m.
Hieronder volgt een definitie die op hetzelfde neerkomt: Het getal dat aangeeft hoeveel priemdelers een getal heeft staat bekend als de Eulerindicator, Eulerfunctie of totiëntfunctie.

Definitie:
De Eulerindicator φ(m) is het aantal gehele, niet-negatieve getallen k waarvoor geldt 0 ≤ k ≤ m -1 en ggd(k,m)=1.
We geven het ook wel aan met de letter K.

Eulerindicator φ(m) is vanzelfsprekend gelijk aan het aantal getallen k waarvoor geldt dat
0 ≤ k ≤ m -1 en dat k een inverse in Zm heeft.
Reflectie
Waarom is vanzelfsprekend het aantal φ(m) gelijk aan het aantal getallen k dat een inverse in Zm heeft?
klik hier
Voorbeeld:
Hoe bepaal je φ(10)?

Je weet dat 10=5∙2
Dus alle veelvouden van 2 en 5 hebben een deler gemeen met 10.
Voor 0 ≤ k ≤ 10 -1 zijn dat de getallen: 2,4,6,8 en 5.
Dus k in het rijtje 1,3,7 en 9 heeft de eigenschap dat ggd(k,10)=1

Dus φ(10)=4.

Opgave 1
Bepaal het aantal priemdelers
a. φ(12)
b. φ(5)
c. φ(7)
d. φ(p) als p een priemgetal is.
e. φ(35)
f. Is er een verband tussen de antwoorden op vraag b., c. en e.?

EF.2 - Somregel en productregel

Voor de Eulerindicator gelden bepaalde wetmatigheden. We zagen er al één in opgave 1d. In opgave 3b en opgave 4d zullen we er nog twee bekijken.

We proberen φ(35) te vinden. Nu is 35=5∙7. Merk op dat 5 en 7 priemgetallen zijn.
Hiervoor maken we een blokje van 5 bij 7.
Op de 1e rij zetten we de getallen 1, ..., 7; op de 2e rij 8, .. 14, enzovoorts.
Dan geven we aan welke getallen niet relatief priem zijn met 5 en 7.

1 | 2 | 3 | 4 | 5 | 6 | 7
8 | 9 | 10 | 11 | 12 | 13 | 14
15 | 16 | 17 | 18 | 19 | 20 | 21
22 | 23 | 24 | 25 | 26 | 27 | 28
29 | 30 | 31 | 32 | 33 | 34 | 35

Hierin is goed te zien dat elk getal in de 7e kolom uitsluitend veelvouden van 7 bevat. En het zijn ze ook allemaal.
Verder kun je opmerken dat in de andere kolommen steeds precies één getal zit dat een veelvoud is van 5.

Laten we eens kijken of we erachter kunnen komen hoe dat komt:
Bekijk de 1e kolom.
Achtereenvolgens staan daar de getallen : 1, 8, 15, 22, 29
Ofwel: 1, 1+7, 1+2∙7. 1+3∙7. 1+4∙7
Bekijk nu de resten na deling door 5. Dat zijn achtereenvolgens:
1, 3, 0, 2 en 4.
Deze resten zijn alle onderling verschillend!
De resten berekenen we bij het modulo-rekenen waarvoor de volgende regels gelden:

Voor gehele getallen a, b, c en d en positieve gehele getallen m geldt:
als a(modm)=b(modm) en c(modm)=d(modm) dan

Somregel: (a+c)modm=(b+d)modm

Productregel: (a*c)modm=(b*d)modm

Reflectie
Deze resten zijn alle onderling verschillend! Zoek eens uit hoe dat komt.

a) Waarom heeft het rijtje 2, 2+7, 2+2∙7. 2+3∙7. 2+4∙7 dezelfde resten na delen door 5 als 2, 2+2, 2+2∙2. 2+3∙2. 2+4∙2?

b) Waarom kan 2+2k = 2+2l in Z5 alleen als k = l?

klik hier

In elke kolom staat dus precies één getal dat een veelvoud is van 5.
Dus is φ(35) gelijk aan het aantal kolommen zonder zevenvouden ( dat zijn er 7 -1 = 6),
vermenigvuldigd met het aantal getallen in elke kolom dat geen vijfvoud is (dat zijn er in elke kolom 5 - 1 = 4).
Dit geeft φ(35) = φ(7)∙ φ(5) = 6∙4=24 .

Opgave 2

a) Bepaal φ(77)
b) Bepaal φ(82)
c) Bepaal φ(1055)
d) Bepaal φ(8). Pas op.

Opgave 3

a) Bepaal het aantal priemdelers van p*q als p en q priem zijn en p ≠ q. Leg uit hoe je aan je antwoord komt.
b) Laat zien dat het aantal priemdelers φ(p*q)=φ(p)*φ(q) als p en q priem zijn en p ≠ q.

De regel uit 3b geldt ook als p en q relatief priem zijn. We zullen dit hier niet bewijzen, maar je kunt het natuurlijk zelf proberen.

EF.3 - Een regel voor φ(p r )

We bekijken een voorbeeld: φ(72)=?
Eerst maar eens een tabel maken met behulp van Excel.

1 | 2 | 3 | 4 | 5 | 6 | 7
8 | 9 | 10 | 11 | 12 | 13 | 14
15 | 16 | 17 | 18 | 19 | 20 | 21
22 | 23 | 24 | 25 | 26 | 27 | 28
29 | 30 | 31 | 32 | 33 | 34 | 35
36 | 37 | 38 | 39 | 40 | 41 | 42
43 | 44 | 45 | 46 | 47 | 48 | 49

Alleen in de laatste kolom staan veelvouden van 7. Alle andere getallen zijn relatief priem met 49.
Immers een gemeenschappelijke deler kan alleen 7 zijn.
Dus zijn er 6 kolommen met 7 getallen die relatief priem zijn met 49.
φ(72)=7∙6=42.

Reflectie

Bedenk dat in de 1e kolom elk getal geschreven kan worden in de vorm: 1+k∙7, k=0,1,2,3,4,5,6.
a) Leg uit dat in de 1e kolom dus geen enkel zevenvoud kan voorkomen.
b) Kan er in de 2e kolom een 7-voud voorkomen?

c) Leg uit dat dus φ(72)=7∙(7-1).

klik hier

Opgave 4

a) Bepaal φ(25).
b) Bepaal φ(125).
c) Bepaal φ(625).
d) Leg uit dat φ(pr) = (p-1)*pr-1.

In opgave 3b en opgave 4d hebben we twee regels aangetoond die nu van belang zijn:

1.φ(p*q)=φ(p)*φ(q) als p en q (relatief) priem zijn en p ≠ q. 2. φ(pr) = (p-1)*pr-1 voor een priemgetal p.

Met deze twee regels voor de Eulerindicator kunnen we voor alle getallen de Eulerindicator berekenen. Om van een getal de Eulerindicator te vinden, schrijven we het getal eerst als product van machten van zijn priemfactoren. Die machten van priemfactoren zijn onderling vanzelfsprekend relatief priem en daarom mogen we de regels toepassen, zoals in het volgende

Voorbeeld:

Bereken φ(18000).
18000=24*32*53. Er geldt dat 24, 32 en 53 relatief priem zijn. We passen daarom de regels toe:

φ(18000)=φ(24)*φ(32)*φ(53) volgens regel 1
φ(18000)=(1*23)*(2*31)*(4*52)=8*6*100=4800 volgens regel 2.

Opgave 5

a) Bepaal φ(640)
b) Bepaal φ(49000)
c) Bepaal φ(245025)

We zouden de Eulerindicator van m ook graag willen uitrekenen zonder m eerst in factoren te ontbinden. Helaas is niet bekend hoe dat zou moeten. In feite is het uitrekenen van de Eulerindicator equivalent met het ontbinden van m in factoren. We zagen op de hoofdpagina hoe nuttig functies zijn die heel erg moeilijk te berekenen zijn als je niet beschikt over extra informatie, zoals de ontbinding van een getal, en juist makkelijk te berekenen zijn als je wel over extra informatie beschikt. De Eulerindicator komt voor in de stelling van Euler en deze stelling helpt ons bij het rekenen met machten.

EF.4 - De stelling van Euler:

Voor alle gehele getallen a en m met ggd(a,m)=1 geldt dat a φ(m)=1 in Zm.

Dit is een resultaat waarmee we grote machten heel snel kunnen reduceren en waardoor ondermeer Alice en Bob wel in staat zijn te vercijferen volgens het algoritme van Diffie en Hellman, maar Eve niet in staat is de sleutel te achterhalen! Zie de opmerking in les 10 hierover.

Voorbeeld:
Bereken 3300 in Z25.
Er geldt ggd(3,25)=1, dus we mogen de stelling van Euler gebruiken: 3φ(25)=1 in Z25
φ(25)=20, dus 320=1 in Z25.
3300=(320)15=115=1.

Opgave 6

Bereken
a) 73843 in Z640
b) 161033 in Z81
c) 252999 in Z99

Uit de stelling van Euler volgt de kleine stelling van Fermat.

EF.5 - De kleine stelling van Fermat

Als p een priemgetal is en a een positief geheel getal en ggd(a,p)=1, dan geldt ap-1=1 mod p .

Opgave 7
Laat zien dat de kleine stelling van Fermat uit de stelling van Euler volgt.

Waarom het RSA algoritme werkt

Het algoritme zegt:

Kies twee grote priemgetallen p en q en bereken n=p*q.
Bereken φ(n)=(p-1)*(q-1)= K
Kies een getal e dat relatief priem is ten opzichte van K en bereken
de inverse d mod K.
Een bericht x met x>0 en x kleiner dan het minimum van p en q, dat vercijferd is met xe mod n = y
is nu te ontcijferen met yd mod n = x.
{e,n} heet de publieke sleutel.
{d,n} heet de privé sleutel.

Bewijs:
Gegeven is n=p*q met p en q priem.
Kies e,d zodanig dat ed = 1(mod φ(n))

dat wil zeggen ed = 1+k∙φ(n) met φ(n) = (p-1)(q-1).

Nu geldt xed(mod n) = x1+k∙φ(n) (mod n)= x∙xk∙φ(n) (mod n)
en omdat ab(mod p) = {a mod p}b volgt x∙xk∙φ(n) (mod n) = x∙{xφ(n) mod n}k

Met 0<x<min{p,q} en n=p∙q moeten x en n relatief priem zijn, zodat uit de stelling van Euler volgt,
dat xφ(n) mod n= 1 zodat
xed(mod n) = x∙{xφ(n) mod n}k= x∙1k = x.

Als x≥min{p,q} dan kan x een veelvoud zijn van p of q. De kans is erg klein omdat er maar weinig van deze getallen zijn, maar in dat geval zijn x en n niet relatief priem. Toch werkt ook in dit geval het RSA algoritme maar het bewijs is veel complexer. Zie voor een uitgebreider bewijs bijvoorbeeld http://pajhome.org.uk/crypt/rsa/maths.html