• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Arytmetyka modularna



    Podstrony: 1 [2] [3] [4]
    Przeczytaj także...
    Liczba pierwsza – liczba naturalna większa od 1, która ma dokładnie dwa dzielniki naturalne: jedynkę i siebie samą, np. R {displaystyle R} jest pierścieniem z dzieleniem (algebrą łączną z dzieleniem) wtedy i tylko wtedy, gdy R ∗ = R ∖ { 0 } {displaystyle R^{*}=Rsetminus {0}} ; w przeciwnym razie zbiór R ∗ {displaystyle R^{*}} jest mniejszy, np. Z ∗ = { 1 , − 1 } {displaystyle mathbb {Z} ^{*}={1,-1}} ;

    Arytmetyka modularna, arytmetyka reszt – system liczb całkowitych, w którym liczby „zawijają się” po osiągnięciu pewnej wartości nazywanej modułem, często określanej terminem modulo (skracane mod). Pierwszy pełny wykład arytmetyki reszt przedstawił Carl Friedrich Gauss w Disquisitiones Arithmeticae („Badania arytmetyczne”, 1801).

    RSA – jeden z pierwszych i obecnie najpopularniejszych asymetrycznych algorytmów kryptograficznych z kluczem publicznym, zaprojektowany w 1977 przez Rona Rivesta, Adi Shamira oraz Leonarda Adlemana. Pierwszy algorytm, który może być stosowany zarówno do szyfrowania jak i do podpisów cyfrowych. Bezpieczeństwo szyfrowania opiera się na trudności faktoryzacji dużych liczb złożonych. Jego nazwa pochodzi od pierwszych liter nazwisk jego twórców.Liczba przeciwna do danej liczby a , {displaystyle a,;} to taka liczba − a , {displaystyle -a,;} że zachodzi:

    Arytmetyka modularna pojawia się wszędzie tam, gdzie występuje powtarzalność i cykliczność; dotyczy ona samego mierzenia czasu i jako taka jest podstawą działania kalendarza (zob. dalej). Ponadto korzysta się z niej w teorii liczb, teorii grup, kryptografii, informatyce, przy tworzeniu sum kontrolnych, a nawet przy tworzeniu wzorów. Zasada działania szyfru RSA oraz Test Millera-Rabina opierają się na własnościach mnożenia w arytmetyce modularnej liczb całkowitych o module wyrażającym się dużą liczbą pierwszą.

    Kongruencja a. przystawanie – relacja równoważności określona w danym systemie algebraicznym. Jedną z najbardziej znanych kongruencji jest przystawanie liczb całkowitych.Łączność – jedna z własności działań dwuargumentowych, czyli np. operatorów arytmetycznych. Pojęcie to występuje w dwóch znaczeniach.

    Motywacja[]

     Zapoznaj się również z: zegar.
    Wskazania zegara 12-godzinnego jako przykład zastosowania arytmetyki modularnej.

    Przykładem może być zegar 24-godzinny, w którym doba podzielona jest na 24 godziny numerowane od 0 do 23. Każdej z nich można jednoznacznie przyporządkować okres w ciągu doby, który minął od godziny 0:00 do tej właśnie godziny – np. godzinie 7:00 można przyporządkować okres 7 godzin – można sobie wyobrażać, że w pewnym momencie ustawiono minutnik na 7 godzin. W ten sposób jeśli zegar wskazuje godzinę 20:00, to znaczy, że od godziny 0:00 minęło 20 godzin; podobnie jeśli zegar wskazuje godzinę 8:00, to oznacza, że godzina 0:00 była dokładnie 8 godzin temu.

    Teoria grup – dział algebry, uważany za dość autonomiczną dziedzinę matematyki (w szczególności teoria grup abelowych, czyli przemiennych), który bada własności struktur algebraicznych nazywanych grupami, czyli zbiorów z wyróżnionym łącznym dwuargumentowym działaniem wewnętrznym mającym element neutralny i w którym każdy element jest odwracalny.Skończenie generowana grupa przemienna – w algebrze abstrakcyjnej grupa przemienna (abelowa), której zbiór generatorów jest skończony. W szczególności, każda skończona grupa abelowa jest skończenie generowana.

    Jeżeli weźmie się jednak pod uwagę okresy dłuższe niż jedna doba, to wspomniane przyporządkowanie nie jest jedynym możliwym: jeśli teraz jest godzina 0:00, to godzinę 4:00 zegar będzie wskazywać tak po 4 godzinach, jak i po 28 godzinach – ogólnie będzie on wskazywał tę samą godzinę po upływie dowolnej liczby pełnych dób (wielokrotności 24 godzin), czyli: wskazania zegara 24-godzinnego powtarzają się co 24 godziny.

    Jądro – dla danej struktury algebraicznej homomorficzny przeciwobraz elementu neutralnego. Dla danego homomorfizmu f {displaystyle f} jego jądro oznacza się zwykle ker  f {displaystyle {mbox{ker }}f} (od ang. kernel)Grupa – jedna ze struktur algebraicznych: zbiór niepusty, na którym określono pewne łączne działanie dwuargumentowe wewnętrzne, dla którego istnieje element odwrotny do każdego elementu oraz element neutralny. Można powiedzieć, że grupą jest monoid, w którym każdy element ma element odwrotny. Dział matematyki badający własności grup nazywa się teorią grup.

    Obserwacje dotyczące wskazań zegara po dwóch okresach umożliwiają określenie wskazania zegara po upływie czasu równego sumie długości tych okresów: jeżeli zegar wskazywał godzinę 0:00 i upłynęło 19 godzin (wskazuje więc on godzinę 19:00), a następnie kolejne 8 godzin (zegar nastawiony na 0:00 wskazywałby po tym czasie godzinę 8:00), to zegar nie będzie wskazywał godziny „27:00”, lecz godzinę 3:00 – tak, jak gdyby od 0:00 minęły tylko 3 godziny.

    Czas – skalarna (w klasycznym ujęciu) wielkość fizyczna określająca kolejność zdarzeń oraz odstępy między zdarzeniami zachodzącymi w tym samym miejscu. Pojęcie to było również przedmiotem rozważań filozoficznych.Podzbiór – pewna „część” danego zbioru, czyli dla danego zbioru, nazywanego nadzbiorem, zbiór składający się z pewnej liczby jego elementów, np. żadnego, jednego, wszystkich. Pierwszy przypadek nazywa się podzbiorem pustym, drugi – podzbiorem jednoelementowym lub singletonem, trzeci – podzbiorem niewłaściwym.

    Można więc wprowadzić następujące dodawanie wskazań zegara: sumą dwóch godzin jest godzina, którą wskazywałby zegar po upływie okresu od 0:00 do pierwszej z godzin powiększonego o okres, który upłynąłby od 0:00 do drugiej z godzin. Oznacza to, że jeżeli okres jest niemniejszy niż 24 godziny, to zegar wskazywać będzie godzinę równą temu okresowi pomniejszonemu o okres 24 godzin. W ten sposób sumą godzin 12:00 i 21:00 jest godzina 9:00 (a nie 33:00). Cofaniu zegara odpowiadałyby „ujemne” okresy, tym zaś „ujemne” wskazania zegara: okresowi −7 godzin (7 godzin wstecz) odpowiada wskazanie zegara sprzed 7 godzin, gdy wskazuje on w tym momencie godzinę 0:00 – na zegarze 24-godzinnym jest to godzina 17:00. Dlatego też różnicą godzin 3:00 i 4:00 jest godzina 23:00 (a nie −1:00).

    Tydzień – pozaukładowa jednostka czasu, okres 7 dni. Ta miara czasu związana jest z fazami Księżyca i odpowiada mniej więcej 1/4 miesiąca. Znany już był Babilończykom w drugim tysiącleciu p.n.e. Tydzień został wprowadzony do urzędowego kalendarza Cesarstwa Rzymskiego w 321 r. n.e., a później został przyjęty w średniowiecznym kalendarzu kościelnym.Twierdzenie o dzieleniu z resztą – twierdzenie matematyczne mówiące o możliwości przedstawienia danej liczby całkowitej, dzielnej, w postaci sumy iloczynu ilorazu przez (niezerowy) dzielnik oraz reszty. Innymi słowy twierdzenie mówi, ile razy (iloraz) dana liczba (dzielnik) mieści się w całości w innej (dzielna) oraz jaka część (reszta) tej liczby nie została wydzielona. Stosuje się także skróconą wersję nazwy: twierdzenie o dzieleniu.

    Upływ czasu liczy się więc zgodnie z arytmetyką liczb całkowitych, z kolei wskazania zegara są zgodne z arytmetyką modularną o module 24: mierzenie czasu na zegarze rozpoczyna się o godzinie 0:00 „zerując się” po osiągnięciu 24:00, z kolei gdy wskazówka zegara cofa się mijając godzinę 0:00, zegar wskazuje godzinę wcześniejszą niż 24:00.

    Pierwiastek pierwotny modulo n {displaystyle n;} to taka liczba, że jej potęgi dają wszystkie możliwe reszty modulo n {displaystyle n;} , które są względnie pierwsze z n {displaystyle n;} .Kryptologia (z gr. κρυπτός – kryptos – "ukryty" i λόγος – logos – "słowo") – dziedzina wiedzy o przekazywaniu informacji w sposób zabezpieczony przed niepowołanym dostępem. Współcześnie kryptologia jest uznawana za gałąź zarówno matematyki, jak i informatyki; ponadto jest blisko związana z teorią informacji, inżynierią oraz bezpieczeństwem komputerowym.

    W ten sam sposób można rozpatrywać obliczenia na dniach tygodnia (wykonywane modulo 7) lub na miesiącach (modulo 12). Prawa działań na liczbach takie jak liczba nieparzysta + liczba parzysta = liczba nieparzysta (zob. parzystość liczb) dają się opisać za pomocą arytmetyki modulo 2.

    Rząd – w teorii grup pojęcie oddające intuicję „rozmiaru” (w sensie „rzędu wielkości”) danej grupy i ułatwiające przy tym opis jej podgrup; w szczególności rzędem elementu nazywa się rząd („rozmiar”) najmniejszej (pod)grupy zawierającej ten element.Rozdzielność działań jest własnością pierścienia (a więc i ciała) określającą powiązanie dwóch operatorów: addytywnego (nazywanego zwykle dodawaniem) i multiplikatywnego (zwykle mnożenie).


    Podstrony: 1 [2] [3] [4]



    w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Warto wiedzieć że... beta

    Logarytm dyskretny elementu b {displaystyle b} przy podstawie a {displaystyle a} w danej grupie skończonej – liczba całkowita c {displaystyle c} , dla której zachodzi równość (w notacji multiplikatywnej):
    Potęgowanie – działanie dwuargumentowe będące uogólnieniem wielokrotnego mnożenia elementu przez siebie. Potęgowany element nazywa się podstawą, zaś liczba mnożeń, zapisywana zwykle w indeksie górnym po prawej stronie podstawy, nosi nazwę wykładnika. Wynik potęgowania to potęga elementu.
    Homomorfizm – funkcja odwzorowująca jedną algebrę ogólną (czyli strukturę algebraiczną taką jak grupa, pierścień czy przestrzeń wektorowa) w drugą, zachowująca przy tym odpowiadające sobie operacje. Jest to podstawowe narzędzie w badaniu i porównywaniu algebr.
    Podział, rozbicie, partycja zbioru – w matematyce rodzina niepustych, rozłącznych podzbiorów danego zbioru dająca w sumie cały zbiór.
    Liczby całkowite – liczby naturalne dodatnie N + = { 1 , 2 , 3 , … } {displaystyle mathbb {N} _{+}={1,2,3,dots }} oraz liczby przeciwne do nich { − 1 , − 2 , − 3 , … } {displaystyle {-1,-2,-3,dots }} , a także liczba zero. Uogólnieniem liczb całkowitych są liczby wymierne i tym samym liczby rzeczywiste, szczególnym przypadkiem liczb całkowitych są: liczby naturalne.
    Relacja równoważności – zwrotna, symetryczna i przechodnia relacja dwuargumentowa określona na pewnym zbiorze utożsamiająca ze sobą w pewien sposób jego elementy, co ustanawia podział tego zbioru na rozłączne podzbiory według tej relacji. Podobnie każdy podział zbioru niesie ze sobą informację o pewnej relacji równoważności.
    Działanie lub operacja – w matematyce i logice przyporządkowanie jednemu lub większej liczbie elementów nazywanych argumentami lub operandami elementu nazywanego wynikiem. Badaniem działań w ogólności zajmuje się dział nazywany algebrą uniwersalną, zbiory z choć jednym określonym na nim działaniem algebraicznym nazywa się algebrami ogólnymi (często krótko: algebrami), samą rodzinę działań określa się nazwą „sygnatura”.

    Reklama

    Czas generowania strony: 0.06 sek.