ძირითადი მასალა
კურსი: კომპიუტერული მეცნიერება > თემა 2
გაკვეთილი 5: მოდულარული არითმეტიკა- ნაშთის ოპერატორი
- ნაშთის გამოწვევა
- სადარობა
- კონგრუენტულობის დამოკიდებულება
- ტოლობის დამოკიდებულებები
- ბეზუს თეორემა
- მოდულარული შეკრება და გამოკლება
- მოდულარული გამოწვევა (შეკრება და გამოკლება)
- სწრაფი მოდულარული ახარისხება
- სწრაფი მოდულარული ახარისხება
- მოდულარული შებრუნებულები
© 2024 Khan Academyგამოყენების პირობებიკონფიდენციალურობის პოლიტიკაშენიშვნა ქუქი-ჩანაწერებზე
სწრაფი მოდულარული ახარისხება
როგორ ვიპოვოთ A^B mod C სწრაფად, თუ B არის 2-ის ხარისხი?
მოდულური გამრავლების წესების გამოყენებით:
ანუ, A^2 mod C = (A * A) mod C = ((A mod C) * (A mod C)) mod C
შეგვიძლია, ამის გამოყენებით სწრაფად გამოვთვალოთ 7^256 mod 13
7^1 mod 13 = 7
7^2 mod 13 = (7^1 *7^1) mod 13 = (7^1 mod 13 * 7^1 mod 13) mod 13
7^2 mod 13 = (7^1 *7^1) mod 13 = (7^1 mod 13 * 7^1 mod 13) mod 13
შეგვიძლია, 7^1 mod 13-ზე მიღებული შედეგი ჩავსვათ ამ განტოლებაში.
7^2 mod 13 = (7 *7) mod 13 = 49 mod 13 = 10
7^2 mod 13 = 10
7^2 mod 13 = 10
7^4 mod 13 = (7^2 *7^2) mod 13 = (7^2 mod 13 * 7^2 mod 13) mod 13
შეგვიძლია, 7^2 mod 13-ზე მიღებული შედეგი ჩავსვათ ამ განტოლებაში.
7^4 mod 13 = (10 * 10) mod 13 = 100 mod 13 = 9
7^4 mod 13 = 9
7^4 mod 13 = 9
7^8 mod 13 = (7^4 * 7^4) mod 13 = (7^4 mod 13 * 7^4 mod 13) mod 13
შეგვიძლია, 7^4 mod 13-ზე მიღებული შედეგი ჩავსვათ ამ განტოლებაში.
7^8 mod 13 = (9 * 9) mod 13 = 81 mod 13 = 3
7^8 mod 13 = 3
7^8 mod 13 = 3
ვაგრძელებთ ამ გზით, წინა შედეგებს ვსვამთ ჩვენს განტოლებებში.
...5 იტერაციის შემდეგ ვიღებთ:
7^256 mod 13 = (7^128 * 7^128) mod 13 = (7^128 mod 13 * 7^128 mod 13) mod 13
7^256 mod 13 = (3 * 3) mod 13 = 9 mod 13 = 9
7^256 mod 13 = 9
7^256 mod 13 = (3 * 3) mod 13 = 9 mod 13 = 9
7^256 mod 13 = 9
ამან მოგვცა A^B mod C-ს სწრაფად გამოთვლის მეთოდი, თუკი მოცემულია, რომ B არის 2-ის ხარისხი.
თუმცა, აგრეთვე გვესაჭიროება მეთოდი სწრაფი მოდულარული ახარისხებისათვის, როდესაც B არ არის 2-ის ხარისხი.
როგორ ვიპოვოთ A^B mod C სწრაფად ნებისმიერი B-ისთვის ?
ნაბიჯი 1: დავყოთ B ორის ხარისხებად მისი ორობითში ჩაწერით
დავიწყოთ ყველაზე მარჯვენა ციფრით, ვთქვათ k=0 და თითოეული ციფრისთვის:
- თუ ციფრი არის 1, გვჭირდება ნაწილი 2^k-სთვის, სხვა შემთხვევაში არ გვჭირდება
- k-ს დავამატოთ 1 და გადავინაცვლოთ შემდეგ მარცხენა ციფრზე
ნაბიჯი 2: გამოთვალეთ ნაშთი C-ზე ორის ხარისხებისთვის ≤ B
5^1 mod 19 = 5
5^2 mod 19 = (5^1 * 5^1) mod 19 = (5^1 mod 19 * 5^1 mod 19) mod 19
5^2 mod 19 = (5 * 5) mod 19 = 25 mod 19
5^2 mod 19 = 6
5^2 mod 19 = (5 * 5) mod 19 = 25 mod 19
5^2 mod 19 = 6
5^4 mod 19 = (5^2 * 5^2) mod 19 = (5^2 mod 19 * 5^2 mod 19) mod 19
5^4 mod 19 = (6 * 6) mod 19 = 36 mod 19
5^4 mod 19 = 17
5^4 mod 19 = (6 * 6) mod 19 = 36 mod 19
5^4 mod 19 = 17
5^8 mod 19 = (5^4 * 5^4) mod 19 = (5^4 mod 19 * 5^4 mod 19) mod 19
5^8 mod 19 = (17 * 17) mod 19 = 289 mod 19
5^8 mod 19 = 4
5^8 mod 19 = (17 * 17) mod 19 = 289 mod 19
5^8 mod 19 = 4
5^16 mod 19 = (5^8 * 5^8) mod 19 = (5^8 mod 19 * 5^8 mod 19) mod 19
5^16 mod 19 = (4 * 4) mod 19 = 16 mod 19
5^16 mod 19 = 16
5^16 mod 19 = (4 * 4) mod 19 = 16 mod 19
5^16 mod 19 = 16
5^32 mod 19 = (5^16 * 5^16) mod 19 = (5^16 mod 19 * 5^16 mod 19) mod 19
5^32 mod 19 = (16 * 16) mod 19 = 256 mod 19
5^32 mod 19 = 9
5^32 mod 19 = (16 * 16) mod 19 = 256 mod 19
5^32 mod 19 = 9
5^64 mod 19 = (5^32 * 5^32) mod 19 = (5^32 mod 19 * 5^32 mod 19) mod 19
5^64 mod 19 = (9 * 9) mod 19 = 81 mod 19
5^64 mod 19 = 5
5^64 mod 19 = (9 * 9) mod 19 = 81 mod 19
5^64 mod 19 = 5
ნაბიჯი 3: გამოიყენეთ მოდულარული გამრავლების თვისებები, რათა გააერთიანოთ C-ს ნაშთის გამოთვლილი მნიშვნელობები
5^117 mod 19 = ( 5^1 * 5^4 * 5^16 * 5^32 * 5^64) mod 19
5^117 mod 19 = ( 5^1 mod 19 * 5^4 mod 19 * 5^16 mod 19 * 5^32 mod 19 * 5^64 mod 19) mod 19
5^117 mod 19 = ( 5 * 17 * 16 * 9 * 5 ) mod 19
5^117 mod 19 = 61200 mod 19 = 1
5^117 mod 19 = 1
5^117 mod 19 = ( 5^1 mod 19 * 5^4 mod 19 * 5^16 mod 19 * 5^32 mod 19 * 5^64 mod 19) mod 19
5^117 mod 19 = ( 5 * 17 * 16 * 9 * 5 ) mod 19
5^117 mod 19 = 61200 mod 19 = 1
5^117 mod 19 = 1
ჩანიშვნები:
არსებობს ოპტიმიზაციას სხვა ტექნიკებიც, მაგრამ ისინი ამ სტატიის პროგრამის ფარგლებს გარეთაა. უნდა აღინიშნოს, რომ როდესაც ვასრულებთ მოდულურ ახარისხებას კრიპტოგრაფიაში, არც ისე იშვიათია მაჩვენებლების გამოყენება B > 1000 ბიტისთვის.
გსურთ, შეუერთდეთ დისკუსიას?
პოსტები ჯერ არ არის.