Algebra - Równania diofantyczne

Nasza ocena:

3
Pobrań: 35
Wyświetleń: 1421
Komentarze: 0
Notatek.pl

Pobierz ten dokument za darmo

Podgląd dokumentu
Algebra - Równania diofantyczne - strona 1 Algebra - Równania diofantyczne - strona 2 Algebra - Równania diofantyczne - strona 3

Fragment notatki:

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)

Zaloguj się, aby dodać komentarz