ლექცია 20, Number Theory

1. აღწერეთ როგორ მოვახდინოთ ნებისმიერი კოდირებული მესიჯის (m*) დეკოდირება, თუ ვიცით ამის გაკეთება იმ შემთხვევისთვის, როცა m*=1. მითითება: ნახეთ მსჯელობა გვ. 294–ზე.

ორიგინალი მესიჯის აღდგენა შეგვიძლია, თუ დაშიფრულ მესიჯს გავამრავლებთ გასაღების შებრუნებულზე. (ფიფქი ცოტა ცუდად იხატება, გამრავლებას გავს და მის მაგივრად ფ-ს დავწერ)

mფ = m*k (mod p)
 m * k *  k^(−1) =  m (mod p), ვინაიდან k *  k^(−1) = 1

გადავწეროთ:  m = mფ * k^(−1) (mod p).
როგორც ფერმამ დაგვიბარა: k^(-1) = k^(p-2).
 m = mფ * k^(p-2)
მოცემულობის თანახმად, ვიცით, რომ mფ = 1, ანუ m*k = 1 (mod p).
შესაბამისად:
m = k^(p-2).
აქედან გავიგეთ k^(p-2) (m ვიცოდით).
ზოგად mფ-ს ვპოულობთ მისი k^(p-2)-ზე გამრავლებით.
მადლობა ა.აზიზიანს დახმარებისთვის.

დისკრეტულის ლექციების სია

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

ლექცია 21 Number theory, Arithmetic with an arbitrary modulus

1)დაასაბუთეთ, რომ φ(p^k)=p^k-p^(k-1), სადაც p ნებისმიერი მარტივი რიცხვია, ხოლო φ წარმოადგენს ეილერის ფუნქციას. 

ჯერ განვმარტოთ თუ რა არის φ(n), ანუ ეილერის ფუნქცია, ეილერის ფუნქცია n - ისთვის არის 1 დან n - მდე ყველა n - თან თანამარტივი რიცხვის რაოდენობა.

ჯერ 1 დან p^k-ს ჩათვლით სულ p^k რიცხვების სიმრავლე, რომელშიც სულ p^k ელემენტი იქნება. ამ სიმრავლეს ჩვენ უნდა გამოვაკლოთ ყველა ისეთი რიცხვი, რომელიც p^k - სთან თანამარტივი არაა, ეს რიცხვები იქნება:

1p;2p;3p;4p...........p^(k-1)p - ამ სიმრავლეში ელემენტების რაოდენობა იქნება p^(k-1), სულ კი p^k რიცხვი გვაქვს, შესაბამისად სხვაობაში გვექნება φ(p^k)=p^k-p^(k-1);

ლექცია 22 Number theory, RSA encryption

1)გაარჩიეთ RSA ალგორითი 303 გვერდზე და ახსენით რა
განაპირობებს საიდუმლო გასაღების საიდუმლოებას?
RSA ალგორითმი შედგება 4 ეტაპისგან:

1. ვაგენერირებთ ორ დიდ მარტივ რიცხვს p და q.
2. შემდეგ ამ ორ რიცხვს ვამრავლებთ და ვარქმევთ n-ს; n=pq;
3. ვარჩევთ ისეთ მთელ რიცხვს e-ს რომელიც ურთიერთმარტივია φ(n)-თან, შესაბამისად gcd(e,φ(n))=1; ეილერის ფუნქციის თანახმად φ(n)=φ(pq)=φ(p)*φ(q), რადგანაც p და q მარტივი რიცხვებია, შესაბამისად φ(p)=(p-1), იგივეა q-სთვისაც და შესაბამისად φ(n)=(p-1)(q-1) - აქ გავეცით პასუხი მეორე კითხვას; შესაბამისად gcd(e,(p-1)(q-1))=1; შემდეგ ჩვენ ვარქმევთ e - სა და n - ის წყვილს public key-ს, რომლის მფლობელიც შეიძლება იყოს ნებისმიერი ადამიანი.
4. ახლა ვაგენერირებთ ისეთ მთელ რიცხვ d - ს, რომ de = 1 mod(φ(n)); მთელი catch ისაა, რომ de შეიძლება წარმოვადგინოთ, როგორც φ(n)*t+1 სადაც t რაღაც მთელი რიცხვია.

ლექცია 25, Counting

problem 16.14

დავუშვათ 2 იგენტური 52 კარტიანი დასტა არეულია ერთმანეთში. რამდენგვარად შეგვიძლია 2 დასტად დავყოთ.

პასუხი:
104!/2^52. ახლა რატომ. 104! აღნიშნავს თანმიმდევრობას ამ კარტებისა. ვინაიდან გვაქვს 2-2 ერთნაირი კარტი, რომელთა ადგილების გაცვლა არაფერს არ ცვლის, გამოდის, რომ 2^52 ვარიანტია კარტების გადაადგილების ისე, რომ არაფერი არ შეიცვალოს. ჯამში 52 ასეთი წყვილია.

                  -by RatMatch

ლექცია 24, Counting

ამოცანა 12 ცალ დონათზე

გვინდა 12 დონათის ყიდვა. არის 5 სახეობა. რამდენნაირად შეგვიძლია ავირჩიოთ.

ავიღოთ 12 ყუთი და 4 გამომყოფი. გამოდის 16!/(4!*12!)
მოიდთ ამას ცოტა განვავრცობ. 12 დონათი რომ ვიყიდოთ, უნდა შევქმანთ "საზღვრები" ერთი სახის დონათებს შორის. ეს საზღვრები უნდა იყოს 4 ცალი, რომ 12 დონათი 5 ნაწილად დაიყოს. ხოლო ეს ფორმულა გვეუბნება, რამდენი ვარიანტია ამ 4 საზღვრის ჩასმის.

ლექცია 19, რიცხვთა თეორია

1. რიცხვი იდეალურია, თუ იგი ტოლია თავისი გამყოფების (თავისი თავის გარდა) ჯამის. მაგალითად, 6 იდეალურია, რადგან 6 = 1+2+3. ასევე, 28 იდეალურია, რადგან 28 = 1+2+4+7+14. ახსენით, რატომ იქნება 2^(k−1) * (2^k −1) იდეალური, როცა 2^k −1 მარტივია.

თუ 2^k-1 მარტივია, მაშინ 2^(k−1) * (2^k −1)-ის ერთადერთი გამყოფებია:

• 1, 2, 4, ... , 2^(k-1), რაც ჯამში ტოლია 2^k-1 -ის, და~
• 1*(2^k −1), 2*(2^k −1), 4*(2^k −1), ..... , 2^(k-2) * (2^k - 1), რაც ჯამში არის (2^(k-1) - 1) * (2^k - 1)

ამ ორის შეკრებით მიიღება 2^(k−1) * (2^k −1), ანუ რიცხვი იდეალურია.