{ "cells": [ { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "# Modulska aritmetika\n", "\n", "## Predloga in testi\n", "Predloga in testi so na voljo v datoteki [modulska_aritmetika.zip](https://github.com/programiranje-SKG/naloge-daljse/blob/main/04_modulska_aritmetika/modulska_aritmetika.zip?raw=true).\n", "\n", "## Uvod\n", "Za podano praštevilo $p$, imenovano modul, definirajmo množico $Z_p = \\{0, 1, ... , p-1\\}$. Za\n", "števila iz te množice sta operaciji *modulskega seštevanja* ($\\oplus$) in modulskega množenja ($\\otimes$)\n", "definirani takole: \n", "\n", "$$a \\oplus b = (a + b) \\; mod \\; p \\\\\n", "a \\otimes b = a b \\; mod \\; p$$\n", "\n", "Zapis $s \\; mod \\; t$ predstavlja ostanek pri deljenju števila $s$ s številom $t$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "Modulska *nasprotna vrednost* števila $a$ je število $\\bar{a}$, za katero velja $a \\oplus \\bar{a} = 0$. Modulska *obratna vrednost* števila $a \\neq 0$ je število $a^*$, za katero velja $a \\otimes a^* = 1$. Sedaj lahko definiramo tudi operaciji *modulskega odštevanja* ($ \\ominus $) in modulskega deljenja ($\\oslash$):\n", "\n", "$$a \\ominus b = a \\oplus \\bar{b} \\\\\n", "a \\oslash b = a \\otimes b^* \\; (pri \\; pogoju \\; b \\neq 0) $$\n" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "\n", "Na primer, elementi množice $Z_7$ se med sabo modulsko seštevajo, odštevajo, množijo in\n", "delijo takole:\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "
Modulska vsota
Modulska razlika
\n", "\n", "| $\\oplus$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | \n", "|---|---|---|---|---|---|---|---|\n", "| **0** | 0 | 1 | 2 | 3 | 4 | 5 | 6 |\n", "| **1** | 1 | 2 | 3 | 4 | 5 | 6 | 0 |\n", "| **2** | 2 | 3 | 4 | 5 | 6 | 0 | 1 |\n", "| **3** | 3 | 4 | 5 | 6 | 0 | 1 | 2 |\n", "| **4** | 4 | 5 | 6 | 0 | 1 | 2 | 3 |\n", "| **5** | 5 | 6 | 0 | 1 | 2 | 3 | 4 |\n", "| **6** | 6 | 0 | 1 | 2 | 3 | 4 | 5 |\n", "\n", "\n", "\n", "\n", "| $\\ominus$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | \n", "|---|---|---|---|---|---|---|---|\n", "| **0** | 0 | 6 | 5 | 4 | 3 | 2 | 1 |\n", "| **1** | 1 | 0 | 6 | 5 | 4 | 3 | 2 |\n", "| **2** | 2 | 1 | 0 | 6 | 5 | 4 | 3 |\n", "| **3** | 3 | 2 | 1 | 0 | 6 | 5 | 4 |\n", "| **4** | 4 | 3 | 2 | 1 | 0 | 6 | 5 |\n", "| **5** | 5 | 4 | 3 | 2 | 1 | 0 | 6 |\n", "| **6** | 6 | 5 | 4 | 3 | 2 | 1 | 0 |\n", "\n", "\n", "
Modulski zmnožek
Modulski količnik
\n", "\n", "| $\\otimes$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | \n", "|---|---|---|---|---|---|---|---|\n", "| **0** | 0 | 0 | 0 | 0 | 0 | 0 | 0 |\n", "| **1** | 0 | 1 | 2 | 3 | 4 | 5 | 6 |\n", "| **2** | 0 | 2 | 4 | 6 | 1 | 3 | 5 |\n", "| **3** | 0 | 3 | 6 | 2 | 5 | 1 | 4 |\n", "| **4** | 0 | 4 | 1 | 5 | 2 | 6 | 3 |\n", "| **5** | 0 | 5 | 3 | 1 | 6 | 4 | 2 |\n", "| **6** | 0 | 6 | 5 | 4 | 3 | 2 | 1 |\n", "\n", "\n", "\n", "\n", "\n", "\n", "| $\\oslash$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | \n", "|---|---|---|---|---|---|---|---|\n", "| **0** | - | 0 | 0 | 0 | 0 | 0 | 0 |\n", "| **1** | - | 1 | 4 | 5 | 2 | 3 | 6 |\n", "| **2** | - | 2 | 1 | 3 | 4 | 6 | 5 |\n", "| **3** | - | 3 | 5 | 1 | 6 | 2 | 4 |\n", "| **4** | - | 4 | 2 | 6 | 1 | 5 | 3 |\n", "| **5** | - | 5 | 6 | 4 | 3 | 1 | 2 |\n", "| **6** | - | 6 | 3 | 2 | 5 | 4 | 1 |\n", "\n", "
\n", "\n" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "*Modulska potenca* $mpow(a, t)$, pri čemer je $a \\in Z_p$, $t$ pa je lahko *poljubno* celo število, je definirana takole:\n", "\n", "$$mpow(a, t) = \n", " \\begin{cases}\n", " 1 & pri \\; t=0 \\\\\n", " a \\otimes mpow(a,t-1) & pri \\; t > 0 \\\\\n", " mpow(a, -t)^* & pri \\; t < 0 \\\\\n", " \\end{cases}\n", "\n", "$$\n", "\n", "Na primer, pri $p = 7$ velja:\n", "- $mpow(5,0) = 1$\n", "- $mpow(5,1) = 5$\n", "- $mpow(5,2) = 5 \\otimes 5 = 4$\n", "- $mpow(5,3) = 5 \\otimes 5 \\otimes 5 = 6$\n", "- $mpow(5,-1) = 5^* = 3$\n", "- $mpow(5,-2) = (5 \\otimes 5)^* = 4^* = 2$" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "\n", "Definirajmo še modulski *kvadratni koren* (msqrt): \n", "\n", "$$ msqrt(a) = \\{b \\in Z_p \\; | \\; b \\otimes b = a\\}$$\n", "\n", "Za razliko od običajnega kvadratnega korena modulski ni enolično določen, zato ga definiramo kot množico vseh števil, ki pri modulskem množenju s samim seboj dajo podano\n", "število. \n", "\n", "Na primer, pri $p=7$ velja: \n", "- $msqrt(0)=\\{0\\}$\n", "- $msqrt(1)=\\{1,6\\}$\n", "- $msqrt(2)=\\{3,4\\}$\n", "- $msqrt(3)= \\emptyset$\n", "- $msqrt(4)=\\{2,5\\}$\n", "- $msqrt(5)= \\emptyset$\n", "- $msqrt(6)= \\emptyset$" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "\n", "Število $n \\in Z_p$ je *multiplikativni generator* množice $Z_p$ , če je množica\n", "\n", "$$\n", "P(n) = \\{mpow(n,i) \\; | \\; i \\in \\{0,1, \\dots, p-1 \\}\\}\n", "$$\n", "\n", "enaka množici $Z_p\\ \\{0\\} = \\{1,2, \\dots,p-1 \\}$. \n", "\n", "Na primer, pri $p=7$ velja:\n", "- $P(0) = \\{0\\}$\n", "- $P(1) = \\{1\\}$\n", "- $P(2) = \\{1,2,4\\}$\n", "- $P(3) = \\{1,2,3,4,5,6\\}$\n", "- $P(4) = \\{1,2,4\\}$\n", "- $P(5) = \\{1,2,3,4,5,6\\}$\n", "- $P(6) = \\{1,6\\}$\n", "\n", "Multiplikativna generatorja množice $Z_7$ sta torej števili 3 in 5." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "## Predloga in rešitve\n", "\n", "Najprej si prenesi predlogo za reševanje, jo ekstrahiraj in odpri v najljubšem IDEju. Kasneje se bodo tukaj pojavile tudi rešitve.\n", "\n", "[predloga.zip](https://github.com/programiranje-SKG/naloge-daljse/raw/main/04_modulska_aritmetika/modulska_aritmetika.zip)\n", "\n", "Če ne maraš predlog, lahko seveda rešuješ tudi samostojno in funkcije testiraš s primeri iz teh navodil." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "## Naloge\n", "\n", "V razredu `Zp`, čigar objekt predstavlja množico $Z_p$ za podani modul $p$ implementirajte sledeče metode:\n", "\n", "### Vsota\n", "\n", "Definiratje metodo `vsota(self, prvo, drugo)`, ki vrne modulsko vsoto števil `prvo` in `drugo` v okviru množice, ki jo predstavlja trenutni objekt. Obe števili sta iz intervala $[0, p-1]$, kjer je $p$ modul množice trenutnega objekta.\n", "\n", "### Zmnožek\n", "Metoda `zmnozek(self, prvo, drugo)` vrne modulski zmnožek števil `prvo` in `drugo` v okviru množice, ki jo predstavlja trenutni objekt. Obe števili sta iz intervala $[0, p-1]$, kjer je $p$ modul množice trenutnega objekta.\n", "\n", "### Nasprotno\n", "Metoda `nasprotno(self, stevilo)` vrne modulsko nasprotno vrednost števila `stevilo`.Število je iz intervala $[0, p-1]$, kjer je $p$ modul množice trenutnega objekta.\n", "\n", "### Razlika\n", "Metoda `razlika(self, prvo, drugo)` vrne modulsko razliko števil `prvo` in `drugo` v okviru množice, ki jo predstavlja trenutni objekt. Obe števili sta iz intervala $[0, p-1]$, kjer je $p$ modul množice trenutnega objekta.\n", "\n", "### Obratno\n", "Metoda `obratno(self, stevilo)` vrne modulsko obratno vrednost števila `stevilo`. Število se nahaja na intervalu $[1, p - 1]$, kjer je $p$ modul množice trenutnega objekta.\n", "\n", "### Količnik\n", "Metoda `kolicnik(self, prvo, drugo)` vrne modulski količnik števil `prvo` in `drugo`. Parameter `prvo` se nahaja v intervalu $[0, p - 1]$, parameter `drugo` pa v intervalu $[1, p - 1]$.\n", "\n", "### Potenca\n", "Metoda `potenca(self, stevilo, eksponent)` vrne modulsko potenco števila `stevilo` na število `eksponent`. Parameter `eksponent` se nahaja v intervalu $[-10^3, 10^3]$. Parameter 'stevilo' se nahaja v intervalu $[1, p-1]$.\n", "\n", "### Število kvadratnih korenov\n", "\n", "Metoda `stevilo_kvadratnih_korenov(self, stevilo)` vrne moč množice (število elementov) modulskih kvadratnih korenov števila `stevilo`, torej število števil $b$ iz intervala $[0, p-1]$, za katera je produkt $b \\otimes b$ enak številu $stevilo$.\n", "\n", "### Je potenca\n", "\n", "Pomožna metoda. `je_potenca(self, osnova, iskani_rezultat)` preveri, če je `iskani_rezultat` potenca števila `osnova` v množici, ki jo predstavlja trenutni objekt.\n", "\n", "### Je multiplikativni generator\n", "\n", "Metoda `je_multiplikativni_generator(self, stevilo)` vrne `True` natanko v primeru, če je število `stevilo` multiplikativni generator množice, ki jo predstavlja trenutni objekt. Parameter `stevilo` se nahaja v intervalu $[1, p - 1]$.\n", "\n", "Pri implementaciji si lahko pomagaš s funkcijo `je_potenca(osnova, iskani_rezultat)`.\n", "\n", "## Namig\n", "Kako bi učinkovito izračunali potenco $a^e$ (oziroma njeno modulsko različico), kjer je eksponent $e$ veliko pozitivno celo število? Če je $e$ sod, se nam $a^e$ splača izračunati kot $(a^{e/2})^2$ , saj lahko potenco $a^{e/2}$ izračunamo na enak način kot potenco $a^e$, le eksponent je za polovico manjši. Lahko podoben trik uporabimo tudi pri lihih eksponentih?" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python", "version": "3.10.6 (main, Nov 14 2022, 16:10:14) [GCC 11.3.0]" }, "orig_nbformat": 4, "vscode": { "interpreter": { "hash": "e7370f93d1d0cde622a1f8e1c04877d8463912d04d973331ad4851f04de6915a" } } }, "nbformat": 4, "nbformat_minor": 2 }