67369 Str072

140    4. Kinom publiczno

(a)    Udowodnij, żc dla ustalonych n i m granica P(n, m) = lim P_p(n_t ^ istnieje i jest zawarta ściśle między 0 i 1.

(b)    Znajdź wzór na P(n, 2).

(c)    Oblicz P(n, 2) dla wszystkich n < 7.

Bibliografia

1.    Adlemnn I M A subaponentiaJ algorithm for ihe discrcle logaritbm problem with Applications to cryplography. Proc. 20th Annual Symposium on ihe Foundation* of Computer Science, 1979, s. 55-60.

2.    Adlcman L.M., DcMarrais J.: "A subcxponcntial algorithm for discrele logarilhms ovcr alt finitc ficlds. Math. Comp., 1993, 61, s. 1-15.

3.    Coppersmith DFast cvaluation oT logarilhms in ficlds of characteristic two. IEEE Transactions on Information Theory IT-30,1984, s. 587-594.

4.    Coppersmith D.. Odlyzko A., Schrocppcl R.: Discrele logarilhms in GP(p). Algorithmica, 1986,1, i. M5.

5.    Diffie W., Hdlman M.E.: New dircctions in cryplography. IEEE Transactions on Information Theory IT-22, 1976, s. 644-654.

6.    ElGamal T.: A public kcy eryptosystem and a signaturc scheme based on discrete logarilhms. IEEE Transactions on Information Theory IT-31,1985, s. 469-472.

7.    ElGamal T.: A subexponential-timc algorithm for compuling discrele logarilhms over GP(p²). IEEE Transactions on Information Theory IT-31, 1985, s. 473-481.

8.    Fellows M., Koblitz N.: Fixed-parameler complexity and cryplography. Proc. Tenth Intern. Symp. Appl. Algebra, Algebraic Algorithms and Error Correcting Codes (San Juan, Puerto Rico), 1993.

9.    Gordon D.: Discrete logarilhms m GP(p) using the number field sieve. SIAM J. Discrete Math., 1993, 6, s. 124-138.

10.    Gordon D., McCurley K.: Massivcly parallel compulation of discrele logarilhms. Adoances in Cryptology - Crypto '92, Springer-Verlag 1993.

11.    Knuth D.E.: The Art of Computer Programming. T.2, Addison-Wesley 1973.

12.    LaMacchia B., Odlyzko A.: Compulation of discrele logarilhms in prime ficlds. Designs, Codes and Cryplography, 1991,1, s. 47-62.

13.    Massey J.L.: Logarilhms in Anitę cydic groups - cryptographic issues. Proc. 4th Benelux Symposium on Information Theory, 1983, s. 17-25.

14.    McCurley K.: The discrete logarithm problem. Cryptology and Computational Number Theory, Proc. Symp. Appl. Math., 1990, 42, s. 49-74.

15.    Odlyzko A.M.: Discrele logarithms in Anile ficlds and their cryptographic significance. Adoances in Cryptology, Proceedings of Eurocrypt 84, Springer-Verlag 1985, s. 224-314.

16.    Wah P.K.S., Wang M.Z.: Realization and application of the Massey-Omura lock. Proc. International Zurich Seminar, 1984, s. 175-182.

4.4. Pakowanie plecaka

W tym podrozdziale opiszemy inny rodzaj systemu kryptograficznego z publicznym kluczem, oparty na tzw. „problemie pakowania plecaka”. Przypuśćmy, że mamy duży plecak, który mamy zapakować przed długą wędrówką po bezdrożach. Mamy wielką liczbę przedmiotów (powiedzmy k przedmiotów) o objętościach v_t, i == 0, ..., k — 1, które mamy zapakować do plecaka o cal-

, _oWitcj pojemności V. Załóżmy następnie, że mamy duże doświadczenie w pakowaniu plecaka i zawsze potrafimy tak go zapakować, że nie pozostanie na-_wct odrobina wolnego miejsca. Chcemy wziąć jak najwięcej bagaży, więc musimy wybrać pewien podzbiór naszego zbioru k przedmiotów tak, by wybrane przedmioty dokładnie wypełniły plecak. Inaczej mówiąc, chcemy znaleźć taki podzbiór / c {1,k], by £t?_f = V, jeśli tylko taki podzbiór istnieje. Jest to

ki

ogólny problem pakowania plecaka. Załóżmy następnie, że V i wszystkie v_t są liczbami całkowitymi dodatnimi. Ten problem możemy równoważnie sformułować w następujący sposób:

Problem pakowania plecaka. Dla danego k-elementowego zbioru {oj liczb całkowitych dodatnich i danej liczby całkowitej V znajdźmy k-bitową liczbę n = (fi*_ |^_₂... e₁c₀)₂ (gdzie e,e{0,1} są cyframi dwójkowymi liczby »)

jt-i

taką, że £ fi, u, = P, o ile taka liczba n istnieje.

1=0

Zauważmy, że ten problem może nie mieć rozwiązania n, może mieć wiele rozwiązań lub też może mieć tylko jedno rozwiązanie, w zależności od ciągu {oj i liczby V.

Szczególnym przypadkiem problemu pakowania plecaka jest tzw. łatwy problem pakowania plecaka. Mamy z nim do czynienia wtedy, kiedy liczby v_it uporządkowane rosnąco, tworzą ciąg superrosnący, tzn. mają tę własność, że każda liczba jest większa od sumy wszystkich wcześniejszych o_{.

Przykład 1. Ciąg pięciu liczb {2,3,7,15, 31} jest ciągiem superrosnącym.

Wiadomo, że ogólny problem pakowania plecaka znajduje się w klasie bardzo trudnych problemów, zwanych problemami „NP-zupełnymi”. To oznacza, że jest on równoważny, jeśli chodzi o stopień trudności, ze słynnym „problemem komiwojażera”. W szczególności, jeśli najważniejsze przypuszczenie teorii złożoności jest prawdziwe, w co prawie każdy wierzy, to nie istnieje żaden algorytm rozwiązujący problem pakowania plecaka w czasie wielomianowym względem k i log B, gdzie B jest ograniczeniem wielkości V i liczb v_t.

Natomiast łatwy problem pakowania plecaka jest znacznie prostszy do rozwiązania. Mianowicie przeglądamy liczby d,, począwszy od największej, tak długo, aż natrafimy na pierwszą liczbę nie większą biż V. Wtedy dołączamy i do naszego zbioru I (czyli przyjmujemy fi, = 1), zastępujemy V przez V-v_t i dalej przeglądamy listę u,, aż znów znajdziemy liczbę nie większą od tej różnicy. Kontynuując to postępowanie, dojdziemy w końcu do zbioru liczb v_it których sumą jest V_y lub też osiągniemy moment, w którym liczba V - £ u, jest

ki

mniejsza od wszystkich pozostałych liczb v, i wtedy problem nie ma rozwiązania. Zapiszemy teraz ten algorytm w postaci bardziej sformalizowanej, którą łatwo można przekształcić w program komputerowy.