Talteori...kryptologi

Nogle der kan forklare mig?

Fordi for ethvert primtal p er restklasseringen (Zp,+p,.p) et legeme. Nulreglen gælder i ethvert legeme, d.v.s. 0 er den eneste nuldivisor.

Termerne anvendt her kræver kendskab til abstrakt algebra at forstå.

Hvad går nulreglen egentlig ud på? Det står ikke noget om nulreglen i den bog vi arbejder med om Kryptologi.

Kan du måske forklare hvad (Zp,+p,.p)er? Tror ikke jeg forstår hvad +p,.p er for npget? Hvad menes med et legeme? Jeg har nemlig bladret samtlige sider gennem min kryptologi bog og der står intet om det.

Det vil derfor vær dejligt med en forklaring.

På forhånd tak!

Abstrakt algebra beskæftiger sig med studiet af grupper, ringe, legemer og moduler. Tid og plads tillader ikke en fyldig introduktion til disse emner her. Det kan mageligt fylde et 1. eller 2. semesters kursus på universitetet bare at komme igennem det grundlæggende.

Så du må nøjes med en destillat.

Et legeme er en dobbeltorganiseret mængde, d.v.s. en mængde forsynet med 2 operationer, sædvanligvist kaldet + og *. En mængde er blot en samling ting. Det kan f.eks. være de hele tal N, de kontinuerte funktioner, huskatte eller noget helt fjerde. En operation er noget man kan gøre med tingene i mængden. Addition af de naturlige tal er et eksempel på en operation. At bringe to katte sammen og se om de parrer sig er en anden. Selvom operationerne skrives + og * behøver de altså ikke være addition og multiplikation i sædvanlig forstand.

For at en dobbeltorganiseret mængde (L,+,*) skal være et legeme skal den opfylde en række betingelser som koger ned til at (L,+) og (L/{0},*) begge skal være abelske grupper. Symbolet 0 angiver det neutrale element for +-operationen.

I et legeme gælder de regneregler du kender så godt: den associative lov, den distributive lov, kommutativitet, forkortningsreglerne og nulregelen. Årsagen til, at du kender disse regler så godt, er, at du er vandt til at arbejde i tallegemer: (Q,+,*), (R,+,*) og (C,+,*) er alle legemer. Det samme er (Zp,+p,*p) hvor jeg med "+p" og "*p" mener addition og multiplikation modulus p.

Nulregelen siger, at for to vilkårlige elementer a,b i legemet L gælder, at a*b = 0 hvis og kun hvis enten a=0 eller b=0. Altså at 0 er den eneste nuldivisor.

Inden du fortvivler helt over alt dette, så lad mig vende tilbage til dit oprindelige spørgsmål. Forestil dig at du kunne vælge en repræsentant fra 2 restklasser modulus p (p primtal) således at deres produkt var en repræsentant for restklassen [0]. Ville det ikke betyde, at p kunne faktoriseres og dermed ikke var et primtal? Tænk over det.

Korrektion:

Nulregelen siger, at for to vilkårlige elementer a,b i legemet L gælder, at a*b = 0 hvis og kun hvis enten a=0 eller b=0. Altså at 0 er den eneste nuldivisor.

->

Nulregelen siger, at for to vilkårlige elementer a,b i legemet L gælder, at a*b = 0 hvis og kun hvis mindst een af a,b er lig 0. Altså at 0 er den eneste nuldivisor.

Tusind tak for din fyldestgørende besvarelse af mine spørgsmål! Jeg fik en større forståelse, hvilket er godt.

Jeg skal som den sidste opgave i min aflevering, redegør:

1.

[a]+([b]+[c]) = ([a]+[b]) + [c] (associative lov)

2.

[0]+[a] = [a] (neutrale elementer)
[1][a] = [a]

3.

[a]([b]+[c]) = [a][b] + [a][c] (distributive lov)

4.

[a]+[b] = [b]+[a] (kommutative lov)
[a][b]=[b][a]

Er der nogle der vil hjælpe mig med at bevise netop de 4 ovenstående punkter. Endvidere må jeg kun bruge definitionen af addition og multiplikation af restklasser, samt regnereglerne for Z.

Har nemlig ikke nogle ideer til hvordan jeg skal bevise dem. Har kigget i min bog, men der står ikke der kan hjælpe mig.

Håber derfor nogle vil hjælpe mig.

På forhånd tak!

Kan I henvise mig til nogle krptologi bøger hvor beviserne i #6 er udledt?

Prøv at hente inspiration i følgende tråd, nok specielt #9 og #15:

https://www.studieportalen.dk/Forums/Thread.aspx?id=187499

Ellers skriv igen.

Jo det har givet mig lidt mere forståelse, især inden for neutrale elementer. Men jeg er ikke istand til at udlede:

1.

[a]+([b]+[c]) = ([a]+[b]) + [c] (associative lov)

2.

[0]+[a] = [a] (neutrale elementer)
[1][a] = [a]

3.

[a]([b]+[c]) = [a][b] + [a][c] (distributive lov)

4.

[a]+[b] = [b]+[a] (kommutative lov)
[a][b]=[b][a]

Håber på at du kan hjælpe mig. Sætter pris på din hjælp.

På forhånd tak!

Da står beviset for den associative lov i Z_n da ellers i indlæg #15 i nævnte tråd.

For de øvrige skal du blot benytte samme metode. Benyt at ækvivalensklassen for et element a netop er elementerne

[a] = {a + qp: q E Z} = {b E Z | b == a (mod) p}

og som nævnt i den refererede tråd skriver vi dette på formen a+pZ.

Til eksempel fås så, at

[0] + [a] = (0+pZ) + (a+pZ) = (0+a) + pZ = a+pZ = [a]

og man bemærker sig i der gøres brug af, at addition i Z er kommutativ.

Du vil måske undre dig over, hvorfor pZ+pZ=pZ, men der skal du huske på, at det er en symbolsk skrivemåde. Med a+pZ mener vi tallet af plus p gange et vilkårligt helt tal. Med 0+pz mener vi 0 plus p gange et (muligvis andet) vilkårligt helt tal. Derfor er summen blot 0+a = a plus p gange et (måske helt tredie) vilkårligt helt tal; altså a+pZ.

Prøv med de øvrige regler og se om der forstår ideen idet.

Prøv evt. også med nogle eksempler for at få en fornemmelse for hvad en restklasse er. Sæt f.eks. p=7. Så er

Zp = Z_7 = {0,1,2,3,4,5,6}

og restklasserne består af følgende hele tal:

[0] = {...,-7q, -7(q-1),...,-7,0,7,...,7(q-1), 7q,...}

[1] = {...,1-7q, 1-7(q-1),...,1-7,1,1+7,...,1+7(q-1), 1+7q,...}

:

o.s.v.

Som repræsentanter for restklasserne [0] og [5] kan vi derfor eksempelvis vælge h.h.v. a=-7*2 = -14 og b=5+8*7 = 61. Addition indenfor de _hele_ tal Z giver a+b = -14+61 = 47. Men 47 == 5 (mod) 7 fordi 47 = 6*7+5. Derfor er 47 en repræsentant for restklassen [5] og vores regninger overført på restklasserne er derfor [0]+[5]=[5]. Prøv evt. selv med flere eksempler.

Hej. Jeg er igang med at skrive SRP opgave, om kryptologi - og er netop nået til det punkt hvor jeg skal forklare restklasse begrebet og bevise hvordan man kan regne med summer, produkter og restklasser.

Er der nogle der kan hjælpe? for jeg er helt på bar bund - jeg har bogen "kryptologi" men kan ikke rigtig finde ud af det! :s håber der er nogle der vil hjælpe..