ძირითადი მასალა

კომპიუტერული მეცნიერება

კურსი: კომპიუტერული მეცნიერება > თემა 2

გაკვეთილი 5: მოდულარული არითმეტიკა

მოდულარული შებრუნებულები

Google–ის საკლასო ოთახი

რა არის შებრუნებული?

გავიხსენოთ, რომ რიცხვი გამრავლებული მის შებრუნებულზე უდრის 1-ს. ელემენტარული არითმეტიკიდან ვიცით, რომ:

A რიცხვის შებრუნებული არის 1/A, რადგან A * 1/A = 1 (ანუ, 5-ის შებრუნებული არის 1/5)
0-ის გარდა ყველა რიცხვს გააჩნია შებრუნებული
რიცხვის გამრავლება A-ს შებრუნებულზე იგივეა, რაც A-ს გაყოფა (ანუ, 10/5 არის იგივე, რაც 10* 1/5)

რა არის მოდულური შებრუნებული?

მოდულარულ არითმეტიკაში არ გვაქვს გაყოფის ოპერაცია. თუმცა, გვაქვს მოდულარული შებრუნებულები.

A (mod C)-ს მოდულარული შებრუნებული არის A^-1
(A * A^-1) ≡ 1 (mod C) იგივეა, რაც (A * A^-1) mod C = 1
მხოლოდ C-ს თანამარტივ რიცხვებს (რიცხვებს, რომლებიც არ იზიარებენ მარტივ გამყოფებს C-სთან) აქვთ მოდულარული შებრუნებული (mod C)

როგორ ვიპოვოთ მოდულური შებრუნებული

პირდაპირი მეთოდი A (mod C)-ს მოდულარული შებრუნებულის საპოვნელად არის:

ნაბიჯი 1. გამოთვალეთ A * B mod C, B-ს მნიშვნელობებისთვის 0-იდან C-1-მდე

ნაბიჯი 2. A mod C-ს მოდულარული შებრუნებული არის B მნიშვნელობა, რომელიც შემდეგ გამოსახულებას ხდის ჭეშმარიტს: A * B mod C = 1

აღვნიშნოთ, რომ წევრ B mod C-ს შეუძლია მხოლოდ მთელი რიცხვების მნიშვნელობების მიღება 0-იდან C-1-მდე, ასე რომ, B-ს უფრო დიდი მნიშვნელობებისთვის შემოწმება ზედმეტია.

მაგალითი: A=3, C=7

ნაბიჯი 1. გამოთვალეთ A * B mod C, B-ს მნიშვნელობებისთვის 0-იდან C-1-მდე

3 * 0 ≡ 0 (mod 7)

3 * 1 ≡ 3 (mod 7)

3 * 2 ≡ 6 (mod 7)

3 * 3 ≡ 9 ≡ 2 (mod 7)

3 * 4 ≡ 12 ≡ 5 (mod 7)

3 * 5 ≡ 15 (mod 7) ≡ 1 (mod 7) <------ ვიპოვეთ შებრუნებული!

3 * 6 ≡ 18 (mod 7) ≡ 4 (mod 7)

ნაბიჯი 2. A mod C-ს მოდულარული შებრუნებული არის B მნიშვნელობა, რომელიც ხდის შემდეგ გამოსახულებას ჭეშმარიტს: A * B mod C = 1

5 არის 3 mod 7-ის მოდულარული შებრუნებული, რადგან 5*3 mod 7 = 1

მარტივია!

გავაკეთოთ კიდევ ერთი მაგალითი, სადაც არ ვპოულობთ შებრუნებულს.

მაგალითი: A=2 C=6

**ნაბიჯი 1. გამოთვალეთ A * B mod C, B-ს მნიშვნელობებისთვის 0-იდან C-1-მდე**

2 * 0 ≡ 0 (mod 6)

2 * 1 ≡ 2 (mod 6)

2 * 2 ≡ 4 (mod 6)

2 * 3 ≡ 6 ≡ 0 (mod 6)

2 * 4 ≡ 8 ≡ 2 (mod 6)

2 * 5 ≡ 10 ≡ 4 (mod 6)

ნაბიჯი 2. A mod C-ს მოდულარული შებრუნებული არის B მნიშვნელობა, რომელიც ხდის შემდეგ გამოსახულებას ჭეშმარიტს: A * B mod C = 1

B-ს არც ერთი მნიშვნელობა არ ხდის შემდეგ გამოსახულებას ჭეშმარიტს: A * B mod C = 1. ასე რომ, A-ს არ გააჩნია არცერთი მოდულური შებრუნებული (mod 6).
ეს იმიტომ, რომ 2 არ არის 6-ის თანამარტივი (ისინი იზიარებენ მარტივ მამრავლ 2-ს).

ეს მეთოდი ნელი ჩანს...

არსებობს გაცილებით უფრო სწრაფი მეთოდი A (mod C)-ს შებრუნებულის საპოვნელად, რომელსაც განვიხილავთ შემდეგ სტატიებში ევკლიდეს განზოგადებულ ალგორითმზე.

გსურთ, შეუერთდეთ დისკუსიას?

შესვლა

დავალაგოთ:

პოსტები ჯერ არ არის.

გესმით ინგლისური? დააწკაპუნეთ აქ და გაეცანით განხილვას ხანის აკადემიის ინგლისურენოვან გვერდზე.