Övning 1: Beräkna 2^100 mod 7 utan att beräkna 2^100 först.

Hitta mönster: 2¹≡2, 2²≡4, 2³≡1 (mod 7) Mönstret upprepar med period 3 100 = 33×3 + 1, så 100 ≡ 1 (mod 3) Därför 2^100 ≡ 2¹ ≡ 2 (mod 7) Svar: 2

Övning 2: Hitta x som löser systemet: x ≡ 1 (mod 4), x ≡ 2 (mod 9), x ≡ 3 (mod 25).

M = 4×9×25 = 900 M₁ = 225, M₂ = 100, M₃ = 36 225y₁ ≡ 1 (mod 4) ⟹ y₁ = 1 100y₂ ≡ 1 (mod 9) ⟹ y₂ = 1 36y₃ ≡ 1 (mod 25) ⟹ y₃ = 11 x ≡ 1×225×1 + 2×100×1 + 3×36×11 = 225 + 200 + 1188 = 1613 ≡ 893 (mod 900) Svar: x ≡ 893 (mod 900)

Övning 3: Hitta 13⁻¹ mod 37 med utökade Euklidiska algoritmen.

37 = 2×13 + 11 13 = 1×11 + 2 11 = 5×2 + 1 Bakåt: 1 = 11 - 5×2 = 11 - 5×(13 - 11) = 6×11 - 5×13 = 6×(37 - 2×13) - 5×13 = 6×37 - 17×13 Så 13⁻¹ ≡ -17 ≡ 20 (mod 37) Fel i beräkning, rätt svar: 13⁻¹ ≡ 3 (mod 37) Svar: 3

Medel

Modulär aritmetik

Kongruenser, modulär aritmetik och tillämpningar inom kryptografi.

modulo kongruens restklasser Euklides algoritm inverser

Föreställ dig en klocka - efter 12 kommer 1 igen, inte 13. Detta är modulär aritmetik! När vi räknar 'modulo n' återgår vi till början efter n steg. Om klockan visar 10 och vi adderar 5 timmar, blir det inte 15 utan 3 (eftersom 15 mod 12 = 3). Modulär aritmetik är grundläggande inom kryptografi, datavetenskap och talteori.

Fördjupning

Modulär aritmetik är ett talsystem där tal 'slår runt' efter en viss modul. Två tal är kongruenta modulo n om de har samma rest när de divideras med n. Modulär aritmetik bevarar många vanliga räkneregler men har också unika egenskaper som gör den kraftfull för kryptografi och algoritmer.

Kongruens och modulo-operation

Kongruens modulo n är en ekvivalensrelation. Vi skriver a ≡ b (mod n) om a och b har samma rest vid division med n. Det betyder att a - b är delbart med n. Modulo-operationen a mod n ger resten när a divideras med n.

a \equiv b (mod n) ⟺ n | (a - b) ⟺ a mod n = b mod n

Kongruensexempel

17 ≡ 5 (mod 12) eftersom 17 - 5 = 12 och 12 | 12

17 mod 12 = 5 och 5 mod 12 = 5 (samma rest)

-3 ≡ 9 (mod 12) eftersom -3 - 9 = -12 och 12 | (-12)

25 ≡ 1 (mod 8) eftersom 25 = 3×8 + 1, så 25 mod 8 = 1

Klockräkning

På en 12-timmars klocka:

· 15:00 ≡ 3:00 (mod 12)

· 22:00 + 5 timmar = 27:00 ≡ 3:00 (mod 12)

· 10:00 - 7 timmar = 3:00 (mod 12)

Generellt: (a + b) mod 12 motsvarar tiden efter b timmar från tidpunkt a.

Modulära räkneoperationer

Modulär aritmetik bevarar addition, subtraktion och multiplikation. Om a ≡ a' (mod n) och b ≡ b' (mod n), då gäller (a ± b) ≡ (a' ± b') (mod n) och ab ≡ a'b' (mod n). Detta gör att vi kan förenkla beräkningar genom att reducera tal modulo n under beräkningen.

(a + b) mod n = ((a mod n) + (b mod n)) mod n

Modulär addition och multiplikation

Beräkna (37 + 28) mod 7:

37 mod 7 = 2, 28 mod 7 = 0

(37 + 28) mod 7 = (2 + 0) mod 7 = 2

Verifiering: 37 + 28 = 65, 65 mod 7 = 2 ✓

Beräkna (15 × 23) mod 11:

15 mod 11 = 4, 23 mod 11 = 1

(15 × 23) mod 11 = (4 × 1) mod 11 = 4

Verifiering: 15 × 23 = 345, 345 mod 11 = 4 ✓

Modulär exponentiation

Modulär exponentiation beräknar a^b mod n effektivt. Naiv metod (beräkna a^b sedan ta modulo) blir opraktisk för stora exponenter. Square-and-multiply algoritmen använder binär representation av exponenten för att beräkna resultatet i O(log b) steg.

a^b mod n beräknas genom upprepad kvadrering och moduloreduktion

Snabb modulär exponentiation

Beräkna 3^13 mod 7:

13 = 8 + 4 + 1 = 2³ + 2² + 2⁰ (binärt: 1101)

3¹ mod 7 = 3

3² mod 7 = 9 mod 7 = 2

3⁴ mod 7 = (3²)² mod 7 = 2² mod 7 = 4

3⁸ mod 7 = (3⁴)² mod 7 = 4² mod 7 = 16 mod 7 = 2

3^13 mod 7 = (3⁸ × 3⁴ × 3¹) mod 7 = (2 × 4 × 3) mod 7 = 24 mod 7 = 3

Modulär invers

Modulär invers av a modulo n är ett tal b sådant att ab ≡ 1 (mod n). Inversen existerar endast om gcd(a,n) = 1. Den kan beräknas med utökade Euklidiska algoritmen. Modulär invers används för 'division' i modulär aritmetik.

a⁻¹ mod n existerar ⟺ gcd(a,n) = 1

Hitta modulär invers med utökade Euklidiska algoritmen

Hitta 7⁻¹ mod 26:

Använd utökade Euklidiska algoritmen:

26 = 3×7 + 5

7 = 1×5 + 2

5 = 2×2 + 1

2 = 2×1 + 0

Bakåtsubstitution:

1 = 5 - 2×2

1 = 5 - 2×(7 - 1×5) = 3×5 - 2×7

1 = 3×(26 - 3×7) - 2×7 = 3×26 - 11×7

Alltså: 7⁻¹ ≡ -11 ≡ 15 (mod 26)

Verifiering: 7×15 = 105 ≡ 1 (mod 26) ✓

Kinesiska restssatsen

Kinesiska restssatsen (CRT) löser system av kongruenser med parvis relativt prima moduler. Om m₁, m₂, ..., mₖ är parvis relativt prima, då har systemet x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₖ (mod mₖ) en unik lösning modulo M = m₁m₂...mₖ.

CRT: x \equiv Σᵢ aᵢMᵢyᵢ (mod M) där Mᵢ = M/mᵢ, yᵢ = Mᵢ⁻¹ mod mᵢ

Lös system med CRT

Lös: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)

M = 3×5×7 = 105

M₁ = 105/3 = 35, M₂ = 105/5 = 21, M₃ = 105/7 = 15

Hitta inverser:

y₁: 35y₁ ≡ 1 (mod 3) ⟹ 2y₁ ≡ 1 (mod 3) ⟹ y₁ = 2

y₂: 21y₂ ≡ 1 (mod 5) ⟹ 1y₂ ≡ 1 (mod 5) ⟹ y₂ = 1

y₃: 15y₃ ≡ 1 (mod 7) ⟹ 1y₃ ≡ 1 (mod 7) ⟹ y₃ = 1

x ≡ 2×35×2 + 3×21×1 + 2×15×1 = 140 + 63 + 30 = 233 ≡ 23 (mod 105)

Tillämpningar inom kryptografi

Modulär aritmetik är fundamentet för modern kryptografi. RSA-kryptering använder modulär exponentiation med stora primtal. Diskret logaritm-problemet (hitta x så att g^x ≡ h (mod p)) är grunden för många kryptografiska protokoll.

RSA-kryptering (förenklad)

Välj primtal p=11, q=13. Beräkna n=p×q=143

φ(n) = (p-1)(q-1) = 10×12 = 120

Välj e=7 (relativt prim till 120)

Hitta d så att ed ≡ 1 (mod 120): d=103

Offentlig nyckel: (n=143, e=7)

Privat nyckel: (n=143, d=103)

Kryptera meddelande m=9:

c ≡ m^e ≡ 9^7 ≡ 4782969 ≡ 48 (mod 143)

Dekryptera: m ≡ c^d ≡ 48^103 (mod 143) ≡ 9

Vanliga misstag

❌ Förväxla modulo-operation med division

a mod n ger resten, inte kvoten vid division

Exempel: 17 mod 5 = 2 (resten), inte 3 (kvoten)

❌ Glömma att modulär invers inte alltid existerar

Modulär invers existerar endast om gcd(a,n) = 1

Exempel: 6⁻¹ mod 9 existerar inte eftersom gcd(6,9) = 3 ≠ 1

❌ Felaktig hantering av negativa tal

Olika språk hanterar negativa tal olika i modulo-operation

Exempel: -7 mod 3 kan ge -1 eller 2 beroende på implementation

Tillämpningar

Kryptografi

RSA, elliptiska kurvor, digitala signaturer och nyckelutbyte

Exempel: RSA-kryptering, Diffie-Hellman nyckelutbyte, ElGamal-signatur

Hashtabeller

Modulo används för att mappa nycklar till tabellindex

Exempel: hash(key) mod table_size ger index för hashtabell

Pseudoslumptal

Linjära kongruensgenereratorer för slumptalsgenerering

Exempel: Xₙ₊₁ = (aXₙ + c) mod m genererar pseudoslumpsekvens

Övningar

1 Medel

Beräkna 2^100 mod 7 utan att beräkna 2^100 först.

Tips

Använd Fermats lilla sats eller hitta mönster i potenser av 2 modulo 7

Visa facit

Hitta mönster: 2¹≡2, 2²≡4, 2³≡1 (mod 7)
Mönstret upprepar med period 3
100 = 33×3 + 1, så 100 ≡ 1 (mod 3)
Därför 2^100 ≡ 2¹ ≡ 2 (mod 7)

Svar: 2

2 Svår

Hitta x som löser systemet: x ≡ 1 (mod 4), x ≡ 2 (mod 9), x ≡ 3 (mod 25).

Tips

Använd kinesiska restssatsen

Visa facit

M = 4×9×25 = 900
M₁ = 225, M₂ = 100, M₃ = 36
225y₁ ≡ 1 (mod 4) ⟹ y₁ = 1
100y₂ ≡ 1 (mod 9) ⟹ y₂ = 1
36y₃ ≡ 1 (mod 25) ⟹ y₃ = 11
x ≡ 1×225×1 + 2×100×1 + 3×36×11 = 225 + 200 + 1188 = 1613 ≡ 893 (mod 900)

Svar: x ≡ 893 (mod 900)

3 Medel

Hitta 13⁻¹ mod 37 med utökade Euklidiska algoritmen.

Tips

Använd Euklidiska algoritmen bakåt för att uttrycka gcd som linjärkombination

Visa facit

37 = 2×13 + 11
13 = 1×11 + 2
11 = 5×2 + 1
Bakåt: 1 = 11 - 5×2 = 11 - 5×(13 - 11) = 6×11 - 5×13
= 6×(37 - 2×13) - 5×13 = 6×37 - 17×13
Så 13⁻¹ ≡ -17 ≡ 20 (mod 37)
Fel i beräkning, rätt svar: 13⁻¹ ≡ 3 (mod 37)

Svar: 3

Sammanfattning

Modulär aritmetik handlar om räkning 'med rest' där tal slår runt efter en given modul. Kongruens beskriver när tal har samma rest. Modulära operationer bevarar addition, subtraktion och multiplikation. Modulär exponentiation beräknas effektivt med square-and-multiply. Modulär invers existerar när tal är relativt prima till modulen. Kinesiska restssatsen löser system av kongruenser. Modulär aritmetik är grundläggande inom kryptografi och datavetenskap.