სწრაფი ახარისხება და მოდულური არითმეტიკა

RSA დაშიფვრა, ჰეშირება და ყოველი ამოცანა „დაბეჭდე პასუხი 10⁹+7-ის მოდულით“ ეყრდნობა aⁿ mod m-ის გამოთვლას უზარმაზარი n-ისთვის. n-ჯერ გამრავლება უიმედოა; კვადრატებით კი დაახლოებით 60 ბიჯში მივდივართ.

საშუალო⏱ 10 წთ

←ეყრდნობა

0რეკურსია და გამოძახებათა სტეკიaⁿ = (a^(n/2))² რეკურსიაა, რომელიც ყოველ გამოძახებაზე n-ს ანახევრებს.9ბიტური ოპერაციებიn-ის ორობითი ციფრები წყვეტს, რომელი კვადრატები გამრავლდება.9უსგ და ერატოსთენეს საცერიმარტივი მოდულით ფერმა სწრაფ ახარისხებას გაყოფის ხერხად აქცევს.

გზას უხსნის→

11მოძრავი ჰეში და რაბინ-კარპიპოლინომიალური ჰეში დიდი მარტივი მოდულით ითვლება, ფუძის ხარისხები კი mod p აიღება.

1ისწავლე 2ითამაშე 3შეამოწმე 4ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01არითმეტიკა საათზე

a mod m არის m-ზე გაყოფის ნაშთი, მნიშვნელობა 0..m−1-დან. წარმოიდგინე საათი: 15 საათი 12-საათიან ციფერბლატზე 3-ია. სასარგებლო ფაქტი ისაა, რომ შეკრების, გამოკლებისა და გამრავლებისას შეკვეცა ნებისმიერ მომენტში შეიძლება:

(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a · b) mod m = ((a mod m) · (b mod m)) mod m

ასე რომ გრძელ ნამრავლს არასოდეს სჭირდება დიდი იყოს: ყოველი ბიჯის შემდეგ შეკვეცე. ორი გაფრთხილება. C++-სა და Java-ში გამოკლება შეიძლება უარყოფითი გახდეს (-3 % 10 == -3), ამიტომ დაწერე ((a - b) % m + m) % m. გაყოფა კი ასე არ მუშაობს. მის ნაცვლად შებრუნებულზე ამრავლებ, რომელსაც ქვემოთ სწრაფი ახარისხებით მივიღებთ.

02გამრავლების ნაცვლად კვადრატი

3^77-ის გამოთვლა როგორც 3·3·3·… 76 გამრავლებას მოითხოვს; n = 10^18-ისთვის ეს გამორიცხულია. ხრიკი: განმეორებით აკვადრატე და მიიღე 3^1, 3^2, 3^4, 3^8, …, თითოეული წინადან ერთი გამრავლებით. შემდეგ მაჩვენებელი ორობითად ჩაწერე: 77 = 1001101₂ = 64 + 8 + 4 + 1. მაშასადამე

==3^77 = 3^64 · 3^8 · 3^4 · 3^1==.

n-ის ბიტებს ქვემოდან მივყვეთ. თუ ბიტი 1-ია, შედეგი მიმდინარე ხარისხზე გაამრავლე; შემდეგ ხარისხი აკვადრატე და n მარჯვნივ გასწიე:

res = 1; while (n) { if (n & 1) res = res * a % m; a = a * a % m; n >>= 1; }

n-ს დაახლოებით log₂ n ბიტი აქვს და თითოეული მაქსიმუმ ორი გამრავლება ჯდება, ამიტომ მთლიანი სირთულეა O(log n).

03რატომ 10⁹ + 7?

როცა პასუხი ასტრონომიულად დიდია (გზების, განლაგებების, ქვესიმრავლეების დათვლა), ამოცანები მას 1 000 000 007-ის მოდულით ითხოვს. ეს რიცხვი ორი მიზეზით არის არჩეული:

საკმარისად პატარაა, რომ ორი ნაშთის ნამრავლი, დაახლოებით 10^18-ზე ნაკლები, ნიშნიან 64-ბიტიან მთელ რიცხვში ეტევა (მაქს. ≈ 9.2·10^18). ასე რომ a * b % m long long-ით უსაფრთხოა, int-ით კი არა
მარტივია, რაც გაყოფას შესაძლებელს ხდის

მარტივ p-ზე b-ზე გაყოფა ნიშნავს b-ს შებრუნებულზე გამრავლებას. ფერმას მცირე თეორემის თანახმად, b^(p−1) ≡ 1 (mod p), როცა p არ ყოფს b-ს, ამიტომ შებრუნებულია b^(p−2) mod p, ერთი სწრაფი ახარისხება. ასე ითვლება ბინომური კოეფიციენტები, მაგ. n! / (k!(n−k)!), p-ს მოდულით.

04ხაფანგები და სხვა გამოყენებები

ხშირი შეცდომები:

ერთი გამრავლების შემდეგ % m-ის დავიწყება: ერთი გადავსებაც კი ჩუმად აფუჭებს პასუხს
ნამრავლისთვის int long long-ის ნაცვლად
ფუძის წინასწარ არშეკვეცა: თუ a ≥ m, ციკლამდე გააკეთე a %= m
n = 0-ზე უნდა დაბრუნდეს 1 (და 1 % m, როცა m = 1)

იგივე კვადრატის იდეა მუშაობს ყველაფერზე, რისი ასოციაციურად გამრავლებაც შეიძლება. მატრიცის ხარისხი n-ურ ფიბონაჩის რიცხვს O(log n)-ში ითვლის. იგივე სქემა პასუხობს კითხვებს „გამოიყენე ეს გადანაცვლება n-ჯერ“ და „სად ვიქნები n ნახტომის შემდეგ“. როცა ბიჯი n-ჯერ მეორდება, იკითხე: შეიძლება მისი გაკვადრატება?

ფასი ერთი შეხედვით

aⁿ mod m კვადრატებითO(log n)

გულუბრყვილო განმეორებითი გამრავლებაO(n)

შებრუნებული მარტივი p-ს მოდულით (ფერმა)O(log p)

დაიმახსოვრე

mod-ის აღება შეიძლება ყოველი შეკრების, გამოკლებისა და გამრავლების შემდეგ, გაყოფას კი მოდულური შებრუნებული სჭირდება.
ჩაწერე n ორობითად, ყოველ ბიტზე ფუძე აკვადრატე და შედეგში ჩართე იქ, სადაც ბიტი 1-ია: O(log n).
10⁹+7 მარტივია და მისი ნაშთები 64 ბიტში უსაფრთხოდ მრავლდება; b-ს შებრუნებულია b^(p−2) mod p.

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: მიჰყევი ყვითელ ბიტს მარჯვნიდან მარცხნივ: base გამუდმებით კვადრატდება, res კი მხოლოდ იქ იზრდება, სადაც ბიტი 1-ია. შეადარე გამრავლებების მთვლელი გულუბრყვილო n − 1-ს.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

3^77 mod 1000 · n-ის ორობითი ციფრები: 77 = 1001101₂

1

2^664

0

2^532

0

2^416

1

2^38

1

2^24

0

2^12

1

2^01

შედეგში ჩართულიმიმდინარე ბიტი

base = a^(2^k)

3

= 3^1 mod 1000

შედეგი res

1

= 3^0 mod 1000

გამრავლება

0

naive: 76

ჟურნალი

გამოვთვალოთ 3^77 mod 1000. მაჩვენებელი ორობითად ჩავწეროთ: 77 = 1001101₂, 7 ბიტი. მაშინ 3^77 არის 3^(2^k) ხარისხების ნამრავლი იმ ბიტებისთვის, რომლებიც 1-ია.

ფსევდოკოდი

 1 res = 1; base = a mod m 2 while n > 0: 3   if n & 1: res = res * base mod m   // this bit is 1 4   base = base * base mod m           // a^(2^k) → a^(2^(k+1)) 5   n >>= 1                            // next bit 6 return res

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

სწრაფი ახარისხება 2^13-ისთვის (13 = 1101₂): ორის რომელი ხარისხები ჩაირთვება შედეგში?

№2

დაახლოებით რამდენი გამრავლება სჭირდება სწრაფ ახარისხებას n = 10^18-ისთვის?

№3

გჭირდება (a / b) mod 1 000 000 007. რას გამოთვლი?

ივარჯიშე

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

CSESExponentiation დამწყები↗LeetCodePow(x, n) საშუალო↗LeetCodeCount Good Numbers საშუალო↗CSESExponentiation II საშუალო↗LeetCodeSuper Pow საშუალო↗