If you're seeing this message, it means we're having trouble loading external resources on our website.

თუ ვებფილტრს იყენებთ, დარწმუნდით, რომ *.kastatic.org და *.kasandbox.org დომენები არ არის დაბლოკილი.

ძირითადი მასალა
მიმდინარე დრო:0:00მთლიანი ხანგრძლივობა:7:09

ვიდეოს აღწერა

ჩვენი მიზანია, რამდენიმე ინსტრუქციის განმარტება, რომლებსაც შეუძლია დამტკიცება არის თუ არა შეყვანილი მთელი რიცხვი შედგენილია თუ მარტივი, სიზუსტის ძალიან მაღალი მაჩვენებლით, რომელიც შეგვიძლია განვმარტოთ. მისი გამოყენება ნაყოფიერი უნდა იყოს, რაც ნიშნავს იმას რომ მისი გამოყენება ნებისმიერ მანქანაზე სწრაფად უნდა ხდებოდეს და თუ რიცხვის სიგრძე გაიზრდება, მთელი რიცხვი n-ის სიგრძე, ის მაინც სწრაფად უნდა მუშაობდეს. აქამდე ვისწავლეთ, რომ მინიმალური დაკმაყოფილებისთვის აუცილებელია რაიმე კანონზომიერება, რომელსაც ყველა მარტივი რიცხვი აკმაყოფილებს და ძალიან ცოტა შედგენილი რიცხვი. თუმცა, წინა ვიდეოში ფერმას თეორემის მცირე ვიზუალური დამონსტრაცია გავაკეთეთ, რომელმაც ძალიან საინტერესო წესი მოგვაწოდა. მოცემული გვაქვს მარტივი რიცხვი p და რაიმე სხვა მთელი რიცხვი a, რომელიც p-ზე ნაკლებია. უკვე ვიცით, რომ p იყოფა a ხარიხად p-სა და a-ს სხვაობაზე. ჩვენ ამას ვწერთ როგორც a ხარისხად p უდრის a mod p. რადგანაც, p-ს და a-ს საერთო გამყოფები არ ჰყავთ, ვინადიან p მარტივია, შეგვიძლია გამოვიყენოთ გაბათილების წესი და ზოგჯერ დავინახავთ მის ასეთ ჩანაწერს a ხარისხად (p-1) უდრის 1 mod p. დაიმახსოვრეთ, ამის გაკეთება მხოლოდ იმიტომ, რომ a-სა და p-ს უდიდესი საერთო გამყოფი უდრის 1-ს. აქ უბრალოდ შევქმენი დემო, რომელიც საშუალებას გვაძლევს ვნახოთ ამ ტოლობის მუშაობა. შენიშნეთ, თუ p მარტივია, პასუხი ყოველთვის უდრის 1-ს, მიუხედავად იმისა თუ რა არის a. თუ შედგენილი რიცხვია p, პასუხი ყოველთვის 1-ის ტოლი არ იქნება. ყოველ ჯერზე როდესაც პასუხი 1-ს არ უდრის ჩვენ ვიღებთ 'შემადგენელ მოწმეს'. ეს არის მტკიცებულება რომ ჩვენს მიერ შეყვანილი p არ არის მარტივი. და ეს არის ამ ტესტის აზრი. სანამ უფრო ღრმად ჩავალთ, მოდი, ცოტათი უკან დავბრუნდეთ და ავაწყოთ ეს ტესტი, იმ ნიმუშის გამოყენებით, რომელიც განახეთ. ჩვენი ტესტი იწყებს რაიმე მთელი რიცხვით, დავარქვათ p, რომელიც შეგვყავს. შემდეგ ჩვენ ვაგენერირებთ რაიმე შემთხვევით მთელ რიცხვს - a-ს, რომელიც ნაკლებია p-ზე. ახლა შეგვიძლია ვიკითხოთ, 'უდიდესი საერთო გამყოფია a-სა და p-ს არის თუ არა 1?' თუ არა, თუ უდიდესი საერთო გამყოფი a-სა და p-ს 1-ზე მეტია, მაშინ მათ აქვთ საერთო მარტივი მამრავლი, და ჩვენ დავამტკიცეთ, რომ p შედგენილია - რადგანაც ის მამრავლებად იშლება. ჩვენი ალგორითმი გვეტყვის, რომ იგი შედგენილია. მაგრამ თუ პასუხია - კი, მაშინ შეგვიძლია დავსვათ მთავარი კითხვა 'a ხარისხად p-ს გამოკლებული 1 mod p უდრის თუ არა 1-ს?' თუ არა, ჩვენ გვყავს მოწმე იმისა, რომ p შედგენილია. თუ ასეა მაშინ, შეგვიძლია ვთქვათ 'p შედგენილია.' სხვა შემთხვევაში, თუ იგი უტოლდება 1-ს, ჩვენი რიცხვი მარტივი უნდა იყოს. მე კოდში ჩავწერე ეს ინტრუქციები ერთ მხარეს გვაქვს ფერმას ტესტი მეორე მხარეს კი არსებული გაყოფადობის ტესტი. იგი იმისთვის გვჭირდება, რომ ყოველთვის დავრწმუნდეთ ტესტის სისწორეში. ერთი შეხედვით, იგი თითქოს მუშაობს. თუმცა, მე პრობლემა აღმოვაჩინე. მე შევიყვანე რიცხვი 511, ფერმას ტესტმა კი აჩვენა, რომ ის მარტივია. გაყოფადობის ტესტი კი ამბობს რომ ის შედგენილია. 511 ფერმას ტესტის აზრით მარტივია. მაგრამ ეს ასე არ არის. მოდი, დავუბრუნდეთ ჩვენს ტოლობას, და ვნახოთ რა მოხდა. ასეთ შემთხვევებს ვეძახით 'ფსევდო-მარტივს'. იგი შედგენილი რიცხვია. არიან კონკრეტული a რიცხვები, რომლებიც შეგვიძლია ავირჩიოთ და პასუხი 1 იქნება. ისევ შეცდომაა. a რიცხვებს, რომლებიც შედგენილ რიცხვს გვაძლევენ - 1-ის გატოლებით, დავარქვათ 'სულელები'. რადგანაც ისინი გვასულელებენ და გვაფიქრებინებენ, რომ რიცხვი მარტივია. მაგრამ, თუ ავირჩევთ განსხვავებულ a-ს, ბევრ შედგენილ მოწმეს ვიპოვით სულელების მაგივრად. იქნებ შეგვიძლია, რომ ცოტათი უკან დავიხიოთ და გამოვიყენოთ იგივე ლოგიკა, რომელსაც გაყოფადობის ტესტის დროს ვიყენებდით, სადაც უბრალოდ ვიმეორებდით ექსპერიმენტს რამდენჯერმე და ვაგენერირებდით ახალ შემთხვევით a-ს ყოველი ჯერისთვის. და ვიმედოვნოთ, რომ ყოველ ჯერზე სულელს არ ავირჩევთ. ახლა დამტკიცებულია რომ სულელების რაოდენობა უნდა იყოფოდეს მთლიან ზომაზე იმ ჯგუფის რომლიდანაც მათ ვარჩევთ. რაც ნიშნავს რომ, მაქსიმუმ ნახევარი ამ ელემენტების, შეიძლება იყოს სულელი. რადგანაც ვირჩევთ შემთხვევით, შედგენილი მოწმის, რომლის პოვნაც გვინდა, პოვნის შანსი, მინიმუმ ნახევარია. t ცდების შემდეგ, მოწმის პოვნის ალბათობა შედგენილი რიცხვისთვის მაქსიმუმ 1/(2 ხარისხად t)-ს ტოლია. შესაბამისად, 20 ცდის შემდეგ შეცდომის ალბათობა იგივეა, რაც ერთი მილიონში. ამ შემთხვევაში ძალიან უიღბლოები უნდა ვიყოთ a-ს გენერირებაში. და ყოველ ჯერზე სულელს უნდა ვირჩევდეთ. თუ დაუფიქრდებით, მიხვდებით თუ რამდენად მნიშვნელოვანია ეს. ახლა, შეგვიძლია ვნახოთ ჩვენი ტესტი მოქმედებაში, ცდების გაზრდილი რაოდენობით. როგორც ჩანს, იდეალურად მუშაობს. შენიშნეთ, რომ ყველაზე ცუდ შემთხვევაში, ანუ როდესაც ჩვენს ალგორითმს მარტივ რიცხვს ვაწოდებთ, იქნება სამუშაოს მაქსიმუმი გასაკეთებელი. ფერმას ტესტი გაცილებით ეფექტურია ვიდრე გაყოფადობის ტესტი. განსაკუთრებით იმიტომ, რომ ბიჯების რაოდენობა არ არის დამოკიდებული შეყვანილი რიცხვის სიდიდეზე. ეს არის მთავარი განსხვავება. ჩვენ ვუთითებთ ცდების რაოდენაბას, სულ ეს არის და ეს. აღარ მოგვიწევს ნერვიულობა იმაზე, რომ ჩვენი ალგორითმი მილიონობით ცდას ჩაატარებს, როგორც წინაზე გვიწევდა. ვგულისხმობ, რომ ეს კვინტესენციურად გამოყენებული მათემატიკაა. ჩვენ ვიღებთ ვინმეს მიერ აღმოჩენილ ნიმუშს და ვინახავთ გამოსათვლელი ციკლების უზარმაზარ რაოდენობას. თუმცა, შეცდომის ერთი, ძალიან მცირე შანსი მაინც არსებობს ამ სისტებაში. შეგიძლიათ იპოვოთ?