Wykład 10 Równania diofantyczne Równanie postaci P(x1, x2,…,xn)=0, gdzie P – wielomian od n zmiennych x1, x2,…,xn z całkowitymi wskaźnikami, nazywamy równaniem diofantycznym. Równanie diofantyczne 2-x zmiennych x i y ma postać: ax+by = c, gdzie a, b, c ∈ Z . Niech d = NWD(a,b). 1) Jeśli d nie dzieli c, to równanie nie ma rozwiązania w liczbach całkowitych. 2) Jeśli c = dc1, a = da1, b=db1, to a1x+b1y = c1, oraz NWD(a1,b1)=1. Twierdzenie Równanie ax+by = c, gdzie x, y – zmienne, a,b,c ∈ Z , ma rozwiązanie w liczbach całkowitych wtedy i tylko wtedy gdy d |c, gdzie d = NWD(a,b). Twierdzenie Zbiór wszystkich rozwiązań równania ax+by = c, gdzie a,b,c ∈ Z , NWD(a,b)=1, ma postać x= x0 +bt, y = y0 – at, gdzie t ∈ Z , (x0, y0) - szczegółowe rozwiązanie równania ax+by = c. Dowód. 1) a(x0 +bt) + b(y0 – at)= ax0 + by0 =c. 2) a(x- x0) + b(y- y0) =0 a(x- x0) = b(y0 – y) ⇒ b | (x- x0) ⇒ x- x0 = bt ⇒ x = x0 + bt abt = b(y0 – y) ⇒ at = y0 – y ⇒ y = y0 – at. Przykład 1. Rozwiązać równanie 13x + 7y =1 x0 = -1, y0 = 2 x = -1 +7t, y = 2 – 13t 2. Rozwiązać równanie 1000x+73y=1 x0 = -10, y0 = 137 x= -10+73t, y=137-1000t Kongruencje liniowe Kongruencje liniowe ax ≡ b (mod m) ma rozwiązanie wtedy i tylko wtedy gdy równanie diafontyczne: ax + my =b ma rozwiązanie w liczbach całkowitych. Twierdzenie Kongruencje liniowe ax ≡ b (mod m), gdzie a,b,m ∈ Z , ma rozwiązanie w liczbach całkowitych wtedy i tylko wtedy gdy d |b, gdzie d = NWD(a,m). 1) Jeśli NWD(a,m)=1, to istnieją liczby s,t takie, e as+mt=1 ⇒ as ≡ 1 (mod m) Liczbę s nazywamy odwrotnej do liczby a. Wtedy asb ≡ b (mod m), skąd x = sb + mt – rozwiązanie kongruencji. 3) Jeśli NWD(a,m) =d oraz d|b, to a=a1d, b=b1d, m=m1d, i mamy a1x ≡ b1 (mod m1) NWD(a1, m1)=1 i istnieją liczby s,t takie, e a1s+m1t=1 ⇒ a1s ≡ 1 (mod m1) Wtedy a1sb1 ≡ b1 (mod m1 ), skąd x = sb1 + m1t – rozwiązanie kongruencji. 3) Jeśli NWD(a,m) =d oraz d nie dzieli b,
(…)
… (mod 9) ⇒ 8u ≡ 4 (mod 9) ⇒ 2u ≡ 1 (mod 9)
⇒ u ≡ 5 (mod 9) ⇒ u = 5 + 9v
Zatem x = 24 + 35(5+9v)= 199 + 315v
x = 199.
Kryptosystem RSA
R.Rivest, A.Shamir, L.Adleman (1977)
Definicja
Funkcja wzajemnie jednoznaczna f : X → Y jest jednokierunkowa, jeśli dla danego x
∈ X łatwo jest policzyć f(x), ale obliczenie f -1(y) dla przypadkowo wybranego y jest
trudne.
Tekst zamieniamy liczbami naturalnymi z przedziału
0≤w<N
Ka dą literą zamieniamy liczbą naturalną i tekst rozbijamy na bloki.
1. Generowanie kluczy
1. Wybieramy losowo dwie liczby pierwsze: p, q
2. Obliczamy
m=p⋅q
3. Wybieramy liczbę k taką, e
1 < k < ϕ(m) = (p-1)(q-1)
oraz
NWD(k, ϕ(m)) =1
Para liczb (m, k) – klucz publiczny
Obliczamy h:
1 < h < ϕ(m)
k⋅h ≡ 1(mod ϕ(m))
Para liczb (m, h) – klucz prywatny
m – modul RSA
k – wykładnik szyfrowania
h…
... zobacz całą notatkę
Komentarze użytkowników (0)