ლექცია 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)-ზე გამრავლებით.
მადლობა ა.აზიზიანს დახმარებისთვის.

2)როგორ შეიძლება ამ თავში აღწერილი კოდის გატეხვა, თუ ხელში ჩაგვივარდა ერთი მესიჯი როგორც ღია, ასევე კოდირებული ფორმით. (ამას ეწოდება known-plaintext attack.)

ამოცანის პერიფრაზირება რომ მოვახდინოთ, ვიცით mფ და m და უნდა ვიპოვოთ k:

mფ = m*k (mod p);

ორივე მხარე გავამრავლოთ m^(p-2)-ზე:

m^(p-2)*mფ = m^(p-2) * m*k (mod p);

m^(p-2) * m*k = m^(p-1) * k (mod p);

m^(p-1) * k = k (ფერმას თეორემა).

მივიღეთ k, რაც გვაძლევს საშუალებას გავიგოთ k^(p-2) და მესიჯები ვტეხოთ და ვტეხოთ.

P.S. ფერმას თეორემაა: k^(p-1) = 1 (mod p)

3) Problem 14.5

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

4) Problem 14.6

ა)რატომ არის რომ: ათობითში ჩაწერილი რიცხვი იყოფა ცხრაზე მაშინ და მხოლოდ მაშინ, როცა მისი ციფრების ჯამი იყოფა ცხრაზე. მითითება 10 = 1 (mod 9).

ვინაიდან 10 = 1 (mod 9) ჭეშმარიტია, ასევე ჭეშმარიტია: 10^k = 1^k = 1 (mod 9)
ახლა ზოგადი რიცხვი ჩავწეროთ ათობით ფორმაში (ფრჩხილებში რაც წერია, ინდექსია):

d(k)*10^k + d(k-1)*10^(k-1)+ ........ + d(0)

აქედან გამომდინარეობს:

d(k)*10^k + d(k-1)*10^(k-1)+ ........ + d(0) = d(k) + d(k-1) + ..... + d(0)   (mod 9)

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

წყარო - http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2010/lecture-notes/MIT6_042JS10_lec22_sol.pdf

ბ)
ავიღოთ რაიმე დიდი რიცხვი, მაგალითად 37273761261. შევკრიბოთ მისი ციფრები, ოღონდ ყოველი მეორე დავწეროთ მინუსით:

3 - 7 + 2 - 7 + 3 - 7 + 6 - 1 + 2 - 6 + 1

ახსენით, რატომ იქნება თავდაპირველი რიცხვი 11-ის ჯერადი მაშინ და მხოლოდ მაშინ, თუ ეს რიცხვიც იქნება 11-ის ჯერადი

10 = -1 (mod 11),  10^k = (-1)^k (mod 11)

დავწეროთ ზოგადი რიცხვი ათობითში (ის რიცხვი უბრალოდ მაგალითისთვის იყო):

d(k)*10^k + d(k-1)*10^(k-1)+ ........ + d(0)

შესაბამისად:

d(k)*10^k + d(k-1)*10^(k-1)+ ........ + d(0) = d(k)*(-1)^k + d(k-1)*(-1)^k +......+d(0)*(-1)^0 (mod 11)

ეს იგივეა, რაც:

d(k) - d(k-1) +......- d(1) + d(0) (mod 11).

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

წყარო - იგივე

5) Problem 14.10

იპოვეთ 13-ის შებრუნებული 1-დან 22-მდე 23-ის მოდულით, pulverizer-ის გამოყენებით.

gcd(23, 13) = 13*x + 23*t

 pulverizer-ის გამოყენებისას ყოველ ჯერზე ვინიშნავთ a - q*b-ს (ნახეთ გვერდი 282). 

 a            b         rem          a-q*b

23          13        10          23 - 1*13;

13          10        3;           13 - 1*10 =  13 - 1*(23 - 1*13) = 13 - 23 + 13 = -23 + 2* 13;

10          3          1;           10 - 3*3 =  23 - 1*13 - 3*(-23 + 2* 13) = 23 - 13 + 3*23 - 6*13=4*23 -7*13

3            1          0;

გამოვიდა, რომ gcd(23, 13) = 13*x + 23*t = 4*23 -7*13 = 1.

შესაბამისად, x=-7-ს.

13*(-7) = -91

მართლაც -91 = 1 (mod 9), მაგრამ -7 ხომ 1-სა და 22-ს შორის არაა. ამიტომ 13*x + 23*t ტოლობას დავუმატოთ და გამოვაკლოთ 13*23

13*x + 13*23 + 23*t - 13*23. ამით ჩვენ ტოლობის მნიშვნელობა არ შეგვიცვლია.

13(x+23) + 23(t-13)

გამოვიდა, რომ x+23-იც არის 13-ის შებრუნებული. x+23=-7+23 = 16, რაც უკვე საზღვრებშია :)

რატომღაც მგონია რომ ასეთი მოვა. არ ვიცი რატომ.

ბ) იგივე უნდა გავაკეთოთ, ოღონდ ფერმას თეორემით

ფერმას თეორემა:

k^(p-1) = 1 (mod p)

აქედან გამომდინარეობს:

k^(p-2)*k = 1 (mod p)

k^(p-2) = k^(-1) (mod p)

ჩვენს შმეთხვევაში k = 13, p = 23.

13^21 = k^(-1) (mod 23)

სწრაფი ახარისხებით (ყველგან mod 23):

13^2 = 169 = 8

13^4 = (13^2)^2 = 8^2 = 64 = 18

13^8 = (13^4)^2 = 18^2 = 324 = 2

13^16 = 2^2 = 4

13^21 = 13^16*13^4*13 = 4*18*13 = 936 = 16

და პასუხია 16. როგორი უცნაურიც არ უნდა იყოს, წინა ამოცანის პასუხს დაემთხვა :)