Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
б) Какова вероятность того, что случайный нормированный многочлен над F3 десятой степени разлагается в произведение многочленов степени не выше второй? Какова вероятность того, что случайный нормированный многочлен над F3 степени не выше 10 разлагается в такое произведение?
12. При п > тп ^ 1 обозначим Рр(п,т) вероятность того, что случайный нормированный многочлен над Fp степени не выше п является произведением неприводимых сомножителей степени не выше т.
а) Доказать, что при любых фиксированных п и тп существует Р(п, т) — limp-.cx, Рр(п, т) и 0 < Р(п, т) < 1.
б) Найти точное выражение для Р(п,2).
в) Вычислить Р(п, 2) при всех п ^ 7.
ЛИТЕРАТУРА к §3 ГЛАВЫ IV
1. Adleman L.M. A subexponential algorithm for the discrete logarithm problem with applications to cryptography. — In: Proceedings of the 20th Annual Symposium on the Foundations of Computer Science, 1979, p. 55-60.
2. Adleman L. M., DeMarrais J. A subexponential algorithm for discrete logarithms over all finite fields. — Math. Comput., 1993, v. 61, p. 1-15.
3. Coppersmith D. Fast evaluation of logarithms in fields of characteristic two. — IEEE Trans. Inform. Theory IT-30, 1984, p. 587-594.
4. Coppersmith D., Odlyzko A., Schroeppel R. Discrete logarithms in GF(p). — Algorithmica, 1986, v. 1, p. 1-15.
5. Diffie. W., He.llman M. E. New directions in cryptography. — IEEE Trans. Inform. Theory IT-22, 1976, p. 644-654.
6. ElGamal T. A public key cryptosystem and a signature scheme based on discrete logarithms. — IEEE Trans. Inform. Theory IT-31, 1985, p. 469-472.
7. ElGamal T. A subexponential-time algorithm for computing discrete logarithms over GF(P2). — IEEE Trans. Inform. Theory IT-31, 1985, p. 473-481.
8. Fellows M., Koblitz N. Fixed-parameter complexity and cryptography. — In: Proceedings of the Tenth International Symposium on Applied Algebra, Algebraic Algorithms and Error Correcting Codes (San Juan, Puerto Rico), 1993.
9. Gordon D. Discrete logarithms in GF(p) using the number field sieve. — SIAM J. Discrete Math., 1993, v. 6, p. 124-138.
10. Gordon D., McCurley K. Massively parallel computation of discrete logarithms. — Advances in Cryptology — Crypto '92. Berlin etc.: Springer, 1992.
11. Knuth D. E. The Art of Computer Programming. V. II. Reading etc.: Addison-Wesley, 1973.
12. LaMacchia B., Odlyzko A. Computation of discrete logarithms in prime fields. — Designs, Codes and Cryptography, 1991, v. 1, p. 47-62.
§ 4. ЗАДАЧА О РЮКЗАКЕ
123
13. Маззеу J. L. Logarithms in finite cyclic groups — cryptographic issues. — In: Proceedings of the 4th Benelux Symposium on Information Theory, 1983, p. 17-25.
14. McCurley K. The discrete logarithm problem. — Crypt. Comput. Number Theory, Proc. Symp. Appl. Math., 1990, v. 42, p. 49-74.
15. Odlyzko A.M. Discrete logarithms in finite fields and their cryptographic significance. — In: Advances in Cryptology. Proceedings of Eurocrypt 84. Heidelberg etc.: Springer, 1985, p. 224-314.
16. Wah P. K. S., Wang M. Z. Realization and application of the Massey-Omura lock. — In: Proceedings of the International Zurich Seminar, 1984, p. 175-182.
§ 4. Задача о рюкзаке
В этом разделе мы опишем иной тип криптосистем с открытым ключом, использующих так называемую «задачу о рюкзаке». Представьте себе, что у вас есть большой рюкзак объема V, с которым вы собираетесь идти в долгий поход по диким местам. Имеется большое число предметов (скажем, их к штук) объемов i>j, г = 0,..., к — 1, соответственно, которые можно положить в рюкзак. Предположим, что вы опытный упаковщик рюкзаков и можете заполнить его, не оставляя свободного места. Чтобы взять максимально возможный груз, вам надо определить совокупность предметов, которая полностью заполнит рюкзак. Другими словами, требуется найти такое подмножество IC {1, • • •, к), что Х^'е/ vi = если оно существует. Это общая задача, о рюкзаке. Далее мы предполагаем, что V и все V{ являются натуральными числами. Тогда задача может быть поставлена в следующей форме.
Задача о рюкзаке. Пусть заданы множество {г^} из к натуральных чисел и целое число V. Требуется найти такое ^-разрядное двоичное число п = (Єк-\?к-2 •••SiSob (где Єі Є {0,1} суть значени-я разрядов в двоичной записи числа п), что Yl^=O ?ivi = ^¦> если такое п существует.
Заметим, что, в зависимости от значений набора и числа V, такого решения может не быть вообще, решений может быть несколько или решение будет единственным.
Частным случаем задачи о рюкзаке является задача о рюкзаке с быстрорастущим набором. Это случай, когда величины будучи упорядоченными в порядке возрастания, обладают тем свойством, что каждое число больше суммы всех предыдущих.
Пример 1. Набор {2,3,7,15,31} является быстрорастущим набором.
Известно, что общая задача о рюкзаке относится к классу очень
124
ГЛ. IV. ОТКРЫТЫЙ КЛЮЧ
трудных задач, называемых «NP-полными задачами». Это означает, что она эквивалентна по сложности известной «задаче о коммивояжере». В частности, если верна основная гипотеза теории сложности, в чем уверено большинство специалистов, то не существует алгоритма, который бы решал произвольную задачу о рюкзаке за время, полиномиальное по А; и по log В, где В — граница для значений V и
