Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
16
Rozdział2.Klasycznakryptografia
201010Szyfrprzestawieniowy
Wtympunkcieopiszemyszyfrprzestawieniowy,któryjestopartynaarytmetycemodu-
larnej.Alenajpierwprzypomnimykilkapodstawowychdefinicjiarytmetykimodularnej.
DEFINICJA2020Załóżmy,żeaibsąliczbamicałkowitymi,amjestliczbącałkowitą
dodatnią.Wówczaspiszemya≡b(modm),jeślimjestdzielnikiemb-a.Wyrażenie
a≡b(modm)nazywamykongruencją(przystawaniem)modulomiczytamynajest
przystającedobmodulom”.Liczbęcałkowitąmnazywamymodułem.
Załóżmy,żedzielimyaibprzezm,otrzymująccałkowiteilorazyireszty,gdzieresztysą
między0am-1.Czylia=q
1m+r
1,ab=q
2m+r
2,gdzie0≤r
1≤m-1i0≤r
2≤m-1.
Wtedynietrudnozauważyć,żea≡b(modm)wtedyitylkowtedy,gdyr
1=r
2.Użyjemy
zapisuamodm(beznawiasów),abyoznaczyćresztęzdzieleniaaprzezm(wartośćr
1po-
wyżej).Zatema≡b(modm)wtedyitylkowtedy,gdyamodm=bmodm.Jeślizastąpimy
aprzezamodm,mówimy,żeajestzredukowanamodulom.
Otokilkaprzykładów.Abyobliczyć101mod7,piszemy101=7×14+3.Ponieważ
0≤3≤6,wynikaztego,że101mod7=3.Winnymprzykładziezałóżmy,żechcemy
obliczyć(-101)mod7.Wtymwypadkupiszemy-101=7×(-15)+4.Ponieważ0≤4
≤6,zatem(-101)mod7=4.
UWAGA0Wielejęzykówprogramowaniadefiniujeamodmjakoresztęwzakresie-m+1,
ł,m-1mającątakisamznakjaka.Naprzykład(-101)mod7będzierówne-3,anie4,
jakzdefiniowanopowyżej.Aledoinnychcelówwygodniejjestzdefiniowaćamodmjako
wartośćzawszenieujemną.
'
Terazzdefiniujemyarytmetycznemodulom:ℤ
mjestzbiorem{0,ł,m-1},naktórym
możnawykonywaćdwadziałania+i×.Dodawanieimnożeniewℤ
mdziaładokładnietak
jakdodawanieimnożenieliczbrzeczywistych,zwyjątkiemtego,żewynikisąredukowane
modulom.
Przypuśćmy,żemamyobliczyć11×13wℤ
16.Ponieważsątoliczbycałkowite,11×
13=143.Następnieredukujemy143modulo16,jakopisanopowyżej:143=8×16+15,
więc143mod16=15,azatem11×13=15wℤ
16.
Tedefinicjedodawaniaimnożeniawℤ
16spełniająwiększośćznanychregułmatema-
tycznych.Wymienimyjetutajbezdowodu:
1.Dodawaniejestdomknięte,czylidladowolnycha,b∈ℤ
m,a+b∈ℤ
m.
2.Dodawaniejestprzemienne,czylidladowolnycha,b∈ℤ
m,a+b=b+a.
3.Dodawaniejestłączne,czylidladowolnycha,b,c∈ℤ
m,(a+b)+c=a+(b+c).
4.0jestelementemneutralnym,czylidladowolnegoa∈ℤ
m,a+0=0+a=a.
5.Liczbąprzeciwnądodowolnegoa∈ℤ
mjestm-a,czylia+(m-a)=(m-a)+a=0
dladowolnegoa∈ℤ
m.
