Lemat 1.37 Jeżeli


oraz
, to równania












63


oraz





('



'


63

'

s¸a równoważne, czyli maj¸a ten sam zbiór rozwi¸azań w zbiorze liczb całkowitych.
18
Rozdział 1. Teoria liczb
Dowód




3

wtedy i tylko wtedy, gdy istnieje
takie że








a to zachodzi wtedy i tylko wtedy, gdy istnieje
takie, że







('




'



'

czyli wtedy i tylko wtedy, gdy





('




'


63

'

9

Przypuśćmy teraz, że dzieli
i rozwi¸ażmy równanie


(1.2)


w pierścieniu
, czyli szukamy takich


, że





9 9
9



(1.3)



3

Z lematu 1.37, to równanie jest równoważne równaniu




(1.4)

('



'


63

'

Ale teraz



i równanie (1.4) ma dokładnie jedno rozwi¸azanie



('

'






takie że


9 9
9

'






('



'


3

'

9
Ale równania (1.4) i (1.3) s¸a spełnione także przez liczby


.











'


'
9 9
9





'
9
S¸a to wszystkie liczby ze zbioru

spełniaj¸ace równania (1.4) i (1.3), czyli


9
9 9


wszystkie rozwi¸azania równania (1.2) w pierścieniu
.

Przykład 1.38 Rozwi¸ażmy równanie



(1.5)



63
9
Ponieważ



, wi¸ec najpierw rozwi¸azujemy równanie












63


W
mamy


wi¸ec rozwi¸azaniem jest





. Tak wi¸ec rozwi¸azaniami



równaia (1.5) w

s¸a liczby





9
1.12. Szyfry liniowe
19
1.12
Szyfry liniowe Przypuśćmy, że mamy tekst zapisany za pomoc¸a 26 liter alfabetu łaci ńskiego:










































i chcemy ten tekst zaszyfrować. W tym celu utożsamiamy zbiór liter z elementami pier-
ścienia
:














9
9 9

wybieramy dwie liczby
, takie że


, i szyfrujemy litera po










literze według wzoru:










3


9
Funkcja deszyfruj¸aca jest określona wzorem:
















63

9
Rzeczywiście:





































9

Z tego wynika, że funkcja szyfruj¸aca
jest wzajemnie jednoznaczna.



Przykład 1.39 Wybierzmy



i

)
i zaszyfrujmy słowo









6
9
W tym celu musimy zaszyfrować 6 liter:
, , , ,
oraz . Obliczenia przedstawiono w





tabeli:

litera
szyfr




m
12
10
k
a
0
20
u
t
19
15
p
e
4
8
i
y
24
0
a
k
10
16
q
SÅ‚owo
po zaszyfrowaniu wygl¸ada tak:







6




9
Jeżeli zaś zastosujemy ten sam szyfr do pocz¸atkowego zdania z wiersza Lokomotywa Ju-liana Tuwima:
stoi na stacji lokomotywa,
to otrzymamy:
spewhuspuotwneqekepagu.
20
Rozdział 1. Teoria liczb
A oto program w j¸ezyku Pascal, który szyfruje teksty zapisane za pomoc¸a 26 liter alfabetu łacińskiego:
var
t:string;
a,b,i,m:integer;
begin
writeln(’podaj klucz’);
write(’a=’);
readln(a);
write(’b=’);
readln(b);
writeln(’podaj tekst do zaszyfrowania’);
readln(t);
for i:=1 to length(t) do
begin
m:=((ord(t[i])-97)*a+b)mod(26)+97;
write(chr(m))
end
end.
Komentarz. Zmienna t jest typu string, czyli Å‚a Å„cuch. Tak¸a zmienn¸a można traktować jak tablic¸e z indeksami od 1 do length(t) i z wartoÅ›ciami typu char (znak). Zmienne typu char s¸a przechowywane w jednym bajcie i mog¸a zawiera ć jeden znak. List¸e znaków wraz z odpowiadaj¸acymi im numerami (od 0 do 255) zawiera tak zwany kod ASCII. MaÅ‚e litery alfabetu Å‚aci Å„skiego maj¸a tam numery od 97 — a, do 122 — z.
Instrukcja
readln(t)
czyta z klawiatury tekst do zaszyfrowania i zapisuje go do zmiennej t. Elementy tablicy t[i], dla i od 1 do length(t), zawieraj¸a poszczególne znaki naszego tekstu.
Funkcja ord przypisuje znakom ich numery w kodzie ASCII, a funkcja chr działa na odwrót, przypisuje znak numerowi. P¸etla for, dla każdego znaku tekstu t po kolei, wylicza numer tego znaku po zakodowaniu:
m:=((ord(t[i])-97)*a+b)mod(26)+97,
a nast¸epnie drukuje zakodowany znak na ekranie:
write(chr(m)).
Klucz do kodowania przechowywany jest w postaci dwóch liczb, a i b, typu integer.
Szyfry liniowe s¸a bardzo starym wynalazkiem. W prostszej wersji z

sto-


 

 

 

 

 

 

 

 

 

 

 

 

   
 
  jest wartoÅ›ci¸a funkcji , czyli gdy 63 to istnieje takie ,...
Pomodliłem się do każdego boga jaki istniał bym był w wstanie wkurzyć tę kobietę do granic możliwości.