მოდულარული არითმეტიკა (Modular Arithmetic)

მოდულარული არითმეტიკა (Modular Arithmetic) === საჭირო ფაქტების მოკლე კონსპექტი შეგიძლიათ იპოვოთ [ამ ბმულზე გადასვლით](https://crypto.stanford.edu/~dabo/courses/cs255_winter22/handouts/numth1.pdf). ამ ლექციაზე განვიხილავთ მოდულარულ არითმეტიკას (მიმატებას, გამრავლებას და სხვა ოპერაციებს მოდულით) ალგორითმული თვალსაზრისით. ვიმუშავებთ დიდ რიცხვებთან (მაგალითად, 1024-ბიტიან მთელ რიცხვებთან), ამიტომაც ეფექტური იქნება მხოლოდ ის ალგორითმები, რომელთა მუშაობის დროც პოლინიმიურად დამოკიდებულია რიცხვში ბიტების რაოდენობაზე (ანუ მისი ბიტური ჩანაწერის სიგრძეზე) და არა რიცხვის მნიშნველობაზე. მარტივი მაგალითისთვის, განვიხილოთ რიცხვის სიმარტივის შემმოწმებელი შემდეგი ალგორითმი: ```python def isPrimeNaive(N): for i in range(2, N): if N % i == 0: # if i divides N return False return True ``` ალგორითმი `isPrimeNaive` გადაუყვება ყველა რიცხვს 2-დან (N-1)-მდე და ამოწმებს, არის თუ არა ეს რიცხვი N-ის გამყოფი. თუ გადავცემთ 80-ბიტიან რიცხვს, მას დასჭირდება დაახლოებით $2^{80}$ ოპერაცია პასუხის დასაბრუნებლად. შეგიძლია ეს ალგორითმი გამაუმჯობესოთ შემდეგნაირად: ```python def isPrimeBetter(N): if N % 2 == 0: return False sqrtN = int(sqrt(N)) for i in range(3, sqrtN, 2): if N % i == 0: return False return True ``` გაუმჯობესებული ალგორითმი `isPrimeBetter` ამოწმებს, N კენტია თუ ლუწი, და თუ კენტია, მაშინ გადაუყვება ყველა კენტ რიცხვს 3-დან N-ის კვადრატულ ფესვამდე. 80-ბიტიან რიცხვზე ეს ალგორითმი აბრუნებს პასუხს დაახლოებით $2^{40}$ ოპერაციის შემდეგ, რაც შეიძლება ადეკვატური დრო იყოს ზოგი გამოყენებისთვის. თუმცა 1024-ბიტიანი რიცხვისთვის ისიც სრულიად არაპრაქტიკულია. დღევანდელ ლექციაში ვნახავთ სიმარტივეზე შემოწმების უკეთეს ალგორითმს, და ასევე ამოცანებს, რომლებისთვისაც სწრაფი ალგორითმებს არსებობის არ გვჯერა, ეს რწმება კი იმდენად მტკიცება, რომ მასზე აგებულია საჯარო კრიპტოგრაფიის დიდი ნაწილი (მაგალითად, ინტერნეტ ბანკინგის უსაფრთხოება). მარტივი არითმეტიკული ოპერაციები მოდულით -- ორი $n$-ბიტიანი რიცხვის **მიმატება** და **გამოკლება** საკმაოდ მარტივია $O(n)$ დროში, ხოლო **გამრავლება** მარტივია $O(n^2)$ დროში (სამივე "ქვეშმიწერის" ალგორითმით). გამრავლების უკეთესი ალგორითმებიც ცნობილია, რომელიც დაახლოებით $O(n \log n)$ დროში მუშაობს. **ნაშთიანი გაყოფაც** $O(n^2)$ დროში შეგვიძლია (მაგალითად, ქვეშმიწერით). ახლა განვიხილო ოპერაციები მოდულით. აღვნიშნოთ $\mathbb{Z}_N$-ით სიმრავლე $\{0,1,\dots,N-1\}$, ხოლო $n$ იყოს $N$-ის ბიტური სიგრძე, ანუ $n$ არის დაახლოებით $\log_2{N}$. ცხადია, მიმატება, გამოკლება და გამრავლება მოდულით $N$ ასევე სწრაფად მუშაობს. $\mathbb{Z}_N$-ის ელემენტების სწრაფი **ახარისხებაც** შეგვიძლია: მაგალითად, $x^{53}$-ის გამოსათვლელად, დავაკვირდებით რომ $53_{10} = 101011_{2}$, ამიტომაც $x^{53} = x^1 \cdot x^2 \cdot x^{16} \cdot x^{32}$, ხოლო ხარისხების გამოთვლა $x \to x^2 \to x^4 \to x^8 \to x^{16} \to x^{32}$ მიმდევრობით კვადრატში აყვანით შეგვიძლია, ჯამში $9$ გამრავლების გამოყენებით. **გამოფა მოდულით $N$** ასევე შინაარსიანი ოპერაციაა. ანალოგიისთვის, ნამდვილ რივხვებში გაყოფა განმარტებულია **შებრუნებულის** გამოყენებით: ნულისგან განსხვავებული ყველა ნამდვილი რიცვხვის $a$-სთვის არსებობს რიცხვი $a^{-1}$ ისეთი რომ $a \cdot a^{-1} = 1$. მაგალითად, $3/4$-ის შებრუნებული არის $4/3$. $a$-ზე გაყოფა იგივეა, რაც $a^{-1}$-ზე გამრავლება. $\mathbb{Z}_N$-შიც შეგვიძლია განვმარტოთ $a \in \mathbb{Z}_N$-ის შებრუნებული როგორც ისეთი $a^{-1} \in \mathbb{Z}_N$ რომ $a \cdot a^{-1} = 1 \bmod N$. მაგალითად, $2$-ის შებრუნებული $\mathbb{Z}_7$-ში არის $4$ რადგან $2 \cdot 4 = 8 = 1 \bmod 7$. ნამდვილი რიცხვებისგან განსხვავებით, $\mathbb{Z}_N$-ის არანულოვანი ელემენტები არ არის აუცილებლად შებრუნებადი: მაგალითად, $\mathbb{Z}_{10}$-ში $2$-ს არ აქვს შებრუნებული, რადგან $2 \cdot b \bmod 10$ ლუწია ნებისმიერი $b$-სთვის. უფრო ზოგადად, გვაქვს ასეთი თეორემა: **თეორემა 1.** არანულოვანი $a \in \mathbb{Z}_N$ შებრუნებადია მაშინ და მხოლოდ მაშინ თუკი $a$ და $N$ ურთიერთმატივი რიცხვებია. *დამტკიცება.* თუ $a$ და $N$ ურთიერთმარტივი რიცხვებია, მაშინ, [ბეზუს თეორემით](https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity), არსებობს ისეთი მთელი რიცხვები $b$ და $c$ რომ $a \cdot b + N \cdot c = \gcd(a, N) = 1$. აქედან გამომდინარეობს, რომ $a \cdot b = 1 \bmod N$, ანუ $(b \bmod N)$ არის $a$-ს შებრუნებული. მეორე მიმართულებისთვის, დავუშვათ $\gcd(a, N) = d > 1$. ნებისმიერი $b$-სთვის, $d$ არის ასევე $a \cdot b$-ს და $N$-ის გამყოფი, ამიტომაც $\gcd(a \cdot b, N) \geq d$, ანუ $a \cdot b \neq 1 \mod N$. $\quad \blacksquare$ $\mathbb{Z}_N$-ში ყველა შებრუნებადი ელემენტის სიმრავლე ქმნის ჯგუფს გამრავლების ოპერაციასთან ერთად. ამ ჯგუფს აღვნიშნავთ $\mathbb{Z}_N^{\times}$-ით. მაგალითად, $\mathbb{Z}_{18}^{\times} = \{1, 5, 7, 11, 13, 17\}$. თეორემა 1-ის გამოყენებით დაამტკიცეთ, რომ ნებისმიერი მარტივი რიცხვი $p$-სთვის, $\mathbb{Z}_p$-ს ყველა არანულოვანი ელემენტი შებრუნებადია, ანუ $|\mathbb{Z}_{p}^{\times}| = p-1$.. ბეზუს თეორემა ასევე გვთავაზობს შებრუნებულის გამოთვლის სწრაფ ალგორითმს, რომელსაც [ევკლიდეს გავრცობილი ალგორითმი](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm) ჰქვია: ```python def extendedGCD(a, b): if a == 0: return b, 0, 1 else: gcd, x, y = extendedGCD(b % a, a) return gcd, y - (b // a) * x, x ``` კოდი აღებულია [აქედან](https://www.techiedelight.com/extended-euclidean-algorithm-implementation/), შეგიძლიათ დავალებაშიც გამოიყენოთ. ეკვლიდეს ალგორითმი მუშაობს $O(n^2)$ დროში, ანუ შებრუნებულის პოვნაც სწრაფად შეგვიძლია. ფერმას (მცირე) და ოილერის თეორემები -- **თეორემა 2 (ფერმა).** ნებისმიერი არანულოვანი $x \in \mathbb{Z}_p$-სთვის, $x^{p-1} = 1 \bmod p$. ფერმას თეორემა გვთავაზობს კიდევ ერთ გზას $x$-ის შებრუნებულის გამოსათვლელად როდესაც მოდული $p$ არის მარტივი რიცხვი. კერძოდ, $x^{-1} = x^{p-2}$. დაამტკიცეთ ეს ფაქტი ფერმას თეორების გამოყენებით. ოილერის თეორემის კიდევ ერთი საინტერესო გამოყენებაა სიმარტივეზე შემოწმების შემდეგი ალგორითმი: ```python def isPrimeFermat(N): if N % 2 == 0: return False return pow(2, N-1, N) == 1 # True iff 2^(N - 1) = 1 mod N ``` დააკვირდით, რომ ფერმას თეორემა არ გვაძლებს გარანტიას, რომ ალგორითმი `isPrimeFermat` ყოველთვის სწორი პასუხს აბრუნებს. ფერმას თეორემა ამბობს "თუ $p$ მარტივია, მაშინ $2^{p-1} = 1 \bmod p$", მაგრამ ამის კონტრაპოზიტივი არ არის აუცილებლად მართებული. მეტიც, არსებობს [პსევდომარტივი რიცხვები](https://en.wikipedia.org/wiki/Carmichael_number), რომლებიც გადიან ამ ტესტს, მაგრამ არ არიან მარტივები, მაგალითად $561$ შედგენილია (იყოფა $3$-ზე) და $2^{560} = 1 \bmod 561$. თუმცა ასეთი რიცხვები იშცვიათია, და არსებობს [უკეთესი ალგორითმები](https://en.wikipedia.org/wiki/Primality_test#Miller%E2%80%93Rabin_and_Solovay%E2%80%93Strassen_primality_test), რომლებიც უმკლავდებიან ფსევდომარტივ რიცხვებსაც. ოილერმა განაზოგადა ფერმას მცირე თეორემა ნებისმიერი $N$-ისთვის. ამისთვის მან შემოიღო [ფუნქცია](https://en.wikipedia.org/wiki/Euler%27s_totient_function) $\varphi(N) := |\mathbb{Z}_N^{\times}|$, ანუ $\varphi(N)$ ითვლის $N$-თან ურთიერთმარტივი ელემენტების რაოდენობას $1$-დან $N$-მდე. **თეორემა 3 (ოილერი).** ნებისმიერი არანულოვანი $x \in \mathbb{Z}_N$-სთვის, $x^{\varphi(N)} = 1 \bmod N$. თეორემა 3 არის თეორემა 2-ის განზოგადება, რადგან $\varphi(p) = p-1$ ნებისმიერი მარტივი $p$-სთვის (დაამტკიცეთ ეს ფაქტი). ოილერის თეორემა აქტიურად გამოიყენება კრიპტოგრაფიაში, მაგალითად RSA კრიპტოსისტემაში, რომელსაც გავივლით მომავალ ლექციებში. რთული ამოცანები -- როგორც ვნახეთ, მიმატება-გამოკლების, გამრავლების, შებრუნებულის პოვნისა და ახარისხების სწრაფი ალგორითმები გვაქვს. უფრო ზოგადად, სწრაფი ახარისხება მუშაობს ნებისმიერ ციკლურ ჯგუფში $G = \{g^0, g^1, \dots, g^{N-1}\}$, სადაც $g$ ამ ჯგუფის გენერატორია, ანუ $g^e$-ს გამოთვლა შეგვიძლია $O(\log_2 e)$ გამრავლების გამოყენებით, იმის მიუხედავად, რა ჯგუფი გვაქვს ხელთ (მაგალითად, ელიპტური წირების ჯგუფებისთვისაც მუშაობს). როგორც წინა ლექციაში ვნახეთ, ახარისხების შებრუნებულ ოპერაციას (მოცემული $g^e$-სთვის $e$-ს პოვნას) ეწოდება **დისკრეტული ლოგარითმი**, და გჯვერა, რომ ეს ოპერაცია რთულია, ანუ არ გვაქვს $n$-ის მიმართ პოლინომიური ალგორითმი, რომელიც ითვლის დისკრეტულ ლოგარითმს. $$ \exp: g, e \to g^e \; (\text{easy}) \\ \log: g, g^e \to g \;\;\; (\text{hard}). $$ კიდევ ერთი ამოცანა, რომელიც რთული გვგონია, არის შედგენილი $N$-ისთვის $\varphi(N)$-ის გამოთვლა. ამოცანა მაშინაც რთულად ითვლება, როცა $N = p \cdot q$ არის ორი მარტივი რიცხვის ნამრავლი. სწორედ ასეთი რიცხვები გამოიყენება RSA-ის სისტემაში. დააკვირდით, რომ $N$-ის **ფაქტორიზაცია** (ანუ მარტივ მამრავლებად დაშლა) რომ ვიცოდეთ, $\varphi(N)$-ის გამოთვლა სწრაფად შეგვეძლებოდა. აჩვენეთ, რომ $\varphi(A \cdot B) = \varphi(A) \cdot \varphi(B)$ როდესაც $A$ და $B$ ურთიერთმარტივი რიცხვებია. დაასკვენით, რომ მარტივი $p$-ს და $q$-ს ცოდნის შემთხვევაში, $\varphi(pq)$-ს გამოთვლა სამ სწრად არითმეტიკულ ოპერაციაში შეგვიძლია. ფაქტორიზაციაზეც გვჯერა, რომ რთული ამოცანაა. საინტერესოა, რომ ეს რწმენა ვრცელდება მხოლოდ კლასიკურ კომპიუტერებზე -- [კვანტურ კომპიუტერებს შეუძლიათ როგორც დისკრეტული ლოგარითმის, ასევე ფაქტორიზაციის სწრაფად გამოთვლა](https://en.wikipedia.org/wiki/Shor%27s_algorithm). **მაგალითი 4.** დისკრეტული ლოგარითმის სირთულეზე დაყრდნობით, შეგვიძლია ავაგოთ კოლიზიისგან დაცული ჰეშ ფუნქცია. ამისთვის ავირჩიოთ დიდი ციკლირი ჯგუფი და მისი ორი გენერატორი $g,h$. ჰეშ ფუნქცია განვსაზღვროთ როგორც $h(x,y) = g^x h^y$. აჩვენეთ, რომ ამ ფუნქციაზე კოლიზიის პოვნა იმდენადვე რთულია, როგორც $h$-ის დისკრეტული ლოგარითმის გამოთვლა $g$-ს მიმართ.