Z modulo n

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Z powodu ograniczeń technicznych tytuł tego artykułu jest nieprawidłowy. Właściwy tytuł to: Pierścień $\mathbb{Z}_n$ .

Pierścień $\mathbb{Z}_n^*$ jest pierścieniem, czyli zbiorem wszystkich liczb naturalnych mniejszych od n (liczonych od 0) z działaniem dodawania i mnożenia modulo n(oba).

[edytuj] Definicja

Trójkę uporządkowaną $\Big(\{0,1,\ldots,n-1\},\oplus,\otimes\Big)$ oznaczaną dalej jako $\mathbb{Z}_n$ nazywamy pierścień klas reszt modulo n. Działanie $\oplus,\otimes$ , czyli dodawanie i mnożenie liczb modulo n rozumiemy następująco:

$x \oplus y = x + y \mod n$

$x \otimes y = x\cdot y \mod n$

[edytuj] Właściwości

Pierścień $\mathbb{Z}_n$ jest pierścieniem łącznym, przemiennym i z jedynką (co wynika z tego, że Z_n i Z_n^* - grupy abelowe).

[edytuj] Elementy szczególne

Elementem neutralnym dodawania $\oplus$ jest 0. Elementem przeciwnym do danego elementu x ze względu na dodawanie jest element n-x. Elementem neutralnym mnożenia $\otimes$ jest 1. Element odwrotny do danego x istnieje wtedy i tylko wtedy, jeżeli x i n są względnie pierwsze i nie zawsze da się łatwo wskazać.

[edytuj] Dzielniki zera i elementy odwracalne

Jeżeli element pierścienia $\mathbb{Z}_n$ k nie jest względnie pierwszy z n, to jest dzielnikiem zera, tzn. istnieje w pierścieniu inny element m taki, że km mod n=0. Prawdą jest, że wszystkie elementy pierścienia $\mathbb{Z}_n$ są albo dzielnikami zera albo są odwracalne. Wynik ten się łatwo uogólnia na wszystkie pierścienie skończone. W pierścieniu $\mathbb{Z}_n$ jest dokładnie φ(n) elementów odwracalnych (a tym samym: n-φ(n) dzielników zera).

[edytuj] Ciało Z_p

Jeżeli dla pierścienia $\mathbb{Z}_n$ n jest liczbą pierwszą to mamy do czynienia z ciałem Z_p.

[edytuj] Pierwiastki z 1

W każdym pierścieniu $\mathbb{Z}_n$ istnieją przynajmniej dwa takie elementy, że ich kwadrat jest równy 1. Są to 1 oraz -1=n-1. Jeżeli n jest liczbą pierwszą (czyli mamy do czynienia z ciałem) to są to jedyne takie elementy. Natomiast, jeżeli n nie jest pierwsze, to takich pierwiastków z 1 jest więcej: dokładniej, jeżeli przez f(n) oznaczymy ilość różnych, pierwszych dzielników n to pierwiastków z 1 a przez ρ(n) ilość pierwiastków z 1 to zachodzi:

$\rho(n) \to 2^{f(n)+[8|n]-[2|n]+[4|n]}$

przy czym:

[...] - notacja Iversona, która przyjmuje wartość 1 jeżeli wyrażenie wewnątrz nawiasów jest prawdą i 0 jeżeli jest fałszem.
x|y - oznacza, że x dzieli y.

Na przykład w pierścieniu $\mathbb{Z}_{60}$ pierwiastkami z 1 jest $2 3 + 0 - 1 + 1 = 2 3 = 8$ i są to:

$1 \to\ 1^2=1$
$11 \to\ 11^2=121 \mod 60=1$
$19 \to\ 19^2=361 \mod 60=1$
$29 \to\ 29^2=841 \mod 60=1$
$31 \to\ 31^2=961 \mod 60=1\ (31^2=(-29)^2=841 \mod 60 = 1)$
$41 \to\ 41^2=1681 \mod 60=1\ (41^2=(-19)^2=361 \mod 60 = 1)$
$49 \to\ 49^2=2401 \mod 60=1\ (49^2=(-11)^2=121 \mod 60 = 1)$
$59 \to\ 59^2=3481 \mod 60=1\ (59^2=(-1)^1=1)$

[edytuj] Struktura izomorficzna

Niech $n=p_1^{a_1}\ldots p_k^{a_k}$ przy czym p_i to parami różne liczby pierwsze oraz a_i - liczby naturalne. Wówczas zachodzi:

$Z_n \cong Z_{p_1^{a_1}} \oplus \ldots \oplus Z_{p_k^{a_k}} = \biguplus_{i=1}^k Z_{p_i^{a_i}}$

gdzie $\oplus,\biguplus$ to odpowiednio znak sumy prostej pierścieni i skrócony znak sumy prostej pierścieni.

[edytuj] Zastosowania

Pierścienie $\mathbb{Z}_n^*$ mają swoje zastosowanie w informatyce i kryptografii - w szczególności zasada działania szyfru RSA opiera się m.in. na właściwościach tego pierścienia, jak również algorytm Rabina-Millera.

[edytuj] Zobacz też

Źródło: "http://pl.wikipedia.org../../../z/_/m/Z_modulo_n.html"

Kategorie: Kryptografia • Teoria pierścieni

Z modulo n

Z Wikipedii

Spis treści

[edytuj] Definicja

[edytuj] Właściwości

[edytuj] Elementy szczególne

[edytuj] Dzielniki zera i elementy odwracalne

[edytuj] Ciało Z_p

[edytuj] Pierwiastki z 1

[edytuj] Struktura izomorficzna

[edytuj] Zastosowania

[edytuj] Zobacz też

Views

nawigacja

techniczne

zmiany

Szukaj

Z modulo n

Z Wikipedii

Spis treści

[edytuj] Definicja

[edytuj] Właściwości

[edytuj] Elementy szczególne

[edytuj] Dzielniki zera i elementy odwracalne

[edytuj] Ciało Zp

[edytuj] Pierwiastki z 1

[edytuj] Struktura izomorficzna

[edytuj] Zastosowania

[edytuj] Zobacz też

Views

nawigacja

techniczne

zmiany

Szukaj

[edytuj] Ciało Z_p