Z modulo n

Z Wikipedii

Pierścień jest pierścieniem, czyli zbiorem wszystkich liczb naturalnych mniejszych od n (liczonych od 0) z działaniem dodawania i mnożenia modulo n(oba).

Spis treści 1 Definicja 2 Właściwości 2.1 Elementy szczególne 2.2 Dzielniki zera i elementy odwracalne 2.3 Ciało Zp 2.4 Pierwiastki z 1 2.5 Struktura izomorficzna 3 Zastosowania 4 Zobacz też

[edytuj] Definicja

Trójkę uporządkowaną oznaczaną dalej jako nazywamy pierścień klas reszt modulo n. Działanie , czyli dodawanie i mnożenie liczb modulo n rozumiemy następująco:

[edytuj] Właściwości

Pierścień 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 jest 0. Elementem przeciwnym do danego elementu x ze względu na dodawanie jest element n-x. Elementem neutralnym mnożenia 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 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 są albo dzielnikami zera albo są odwracalne. Wynik ten się łatwo uogólnia na wszystkie pierścienie skończone. W pierścieniu 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 n jest liczbą pierwszą to mamy do czynienia z ciałem Z_p.

[edytuj] Pierwiastki z 1

W każdym pierścieniu 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:

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 pierwiastkami z 1 jest 2^{3 + 0 − 1 + 1} = 2³ = 8 i są to:

• 
• 
• 
• 
• 
• 
• 
• 

[edytuj] Struktura izomorficzna

Niech przy czym p_i to parami różne liczby pierwsze oraz a_i - liczby naturalne. Wówczas zachodzi:

gdzie to odpowiednio znak sumy prostej pierścieni i skrócony znak sumy prostej pierścieni.

[edytuj] Zastosowania

Pierścienie 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ż

• Ciało Z_p
• Grupa Z_n
• Grupa Z_n^*
• Funkcja Eulera
• Funkcja Carmichaёla
• RSA
• Małe twierdzenie Fermata
• Algorytm Rabina-Millera
• Blum Blum Shub
• Logarytm dyskretny
• Dzielnik zera
• Element odwracalny