WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 3 | 4 ||

«ИНФОРМАЦИОННАЯ БЕЗОПАСНОСТЬ: КРИПТОГРАФИЯ Институт проблем информационной безопасности МГУ О. Н. ВАСИЛЕНКО ТЕОРЕТИКО-ЧИСЛОВЫЕ АЛГОРИТМЫ В КРИПТОГРАФИИ МЦНМО, 2003 УДК 511+519.719.2 Издание осуществлено ...»

-- [ Страница 5 ] --

a1, a2,...] = lim [a0;

a1,..., an]. (6) n Дроби pn qn = [a0;

a1,..., an] называются подходящими дробями / к бесконечной непрерывной дроби. Они обладают теми же свойствами, что и подходящие дроби к конечной непрерывной дроби;

в частности, легко видеть, что предел (6) существует.

Теорема 12. Любое действительное иррациональное число единственным образом представимо в виде бесконечной непре рывной дроби = [a0;

a1, a2...].

Замечание 13. Разложение числа R в непрерывную дробь мож но получить с помощью следующего алгоритма. Пусть = [ ] + { }.

Положим a0 = [ ], r1 = 1 { }, = a0 + 1 r1. За тем r1 = [r1] + = / / 1 {r1} / = a1 + 1 r2 и так далее. После (k + 1)-го вычисления целой части и пе / реворачивания дробной части получим = a0 +.

a1 +... + ak-1 + rk Если = a b Q, то этот процесс эквивалентен алгоритму Евклида для / \ чисел a и b. Если же R Q, то этот процесс будет бесконечным.

Для некоторых иррациональных чисел разложение в непрерывную дробь периодично: дробь = [a0;

a1,..., ak-1, ak,..., ak+T] пери — одическая, если ak,..., ak+T периодически повторяются. Например, 5 = [2;

4] = [2;

4, 4, 4,...].

Приложение \ Теорема 14 (Эйлер Лагранж). Число R Q раскладывает — ся в периодическую непрерывную дробь тогда и только тогда, когда является квадратичной иррациональностью, т. е. кор нем уравнения ax2 + bx + c = 0, где a N, b, c Z.

Теперь мы опишем несколько модификаций алгоритма Евклида и обобщенного алгоритма Евклида. В этих алгоритмах мы стремимся к экономии операций деления, поскольку деление целых чисел много кратной точности отнимает много времени. Деление же на 2 по сути не является делением, а всего лишь сдвигом двоичной записи числа в машинном представлении.

Бинарный алгоритм.

На входе алгоритма заданы числа a, b N, a b. На выхо де d = НОД(a, b).

1 шаг. Присвоить r остаток от деления a на b. За тем a := b, b := r.

2 шаг. Если b = 0, то выдать a и закончить работу. Иначе k := 0, и затем, пока a и b оба четные, выполнять:

k := k + 1, a := a 2, (7) / b := b 2.

/ (После этого 2k идет в НОД(a, b), оставшаяся часть НОД будет нечет ной.) 3 шаг. Сейчас по крайней мере одно из чисел a и b нечетно. Если a четное, то делать присвоения a := a 2 до тех пор, пока a не станет / нечетным. То же для b.

4 шаг. Сейчас a и b оба нечетны. Присвоить t := (a - b) 2. Если / t = 0, то выдать 2ka и закончить работу.

5 шаг. До тех пор, пока t четное, делать t := t 2.

/ 6 шаг. Сейчас t нечетное, t = 0. Если t > 0, то a := t. Если t < 0, то b := -t. Идти на 4 шаг.

Конец алгоритма.

Замечание 15. Анализ сложности алгоритма см. в [25, гл. 4.5.2].

Алгоритм Лемера.

На входе u, v N, u v (u, v целые числа многократной точно — сти). На выходе d = НОД(u, v). Вспомогательные переменные: t, w — многократной точности, u, v, A, B, C, D, T, q однократной точно — сти, p-значные. То есть длина записи числа, не превосходящая p, считается однократной точностью;

запись числа в системе счисления — с основа нием b N.

300 Приложение 1 шаг. (Начальная установка.) 1) Если v однократной точности (в частности, v = 0), то приме — няем алгоритм Евклида к u и v и на ходим d, после чего заканчиваем работу.

2) Если запись u в системе счисления с основанием b занима ет k1 порций по p разрядов, а запись v k2 порций по p разрядов, — и k1 > k2, то выполняем одно деление многократной точности с остат ком u = tv + w, и затем присваиваем u := v, v := w. (Эвристически по сле этого u и v будут примерно одинаковой величины.) 3) В заносим число, записываемое p старшими цифрами u;

то же для v и v. За тем A := 1, B := 0, C := 0, D := 1.

2 шаг. (Проверка окончания.) Сейчас = 0, v = 0, u v. Если = 0, но u + A = 0 или u + B = 0 (это возможно, поскольку данные переменные однократной точности;

например, если = bp - 1, A = 1, — то + A = 0), то перейти на 4 шаг. Аналогично, если v = 0, но v C = + u + A или v + D = 0, то также перейти на 4 шаг. Иначе находим q :=.

v + C u + B Если q =, то перейти на 4 шаг.

v + D 3 шаг. Выполняем вычисления:

- qC, - qD, - qv, T := A T := B T := A := C, B := D, := v, C := T, D := T, v T.

:= Если v = 0, перейти на 4 шаг. Иначе перейти на 2 шаг.

4 шаг. Если B = 0, то произвести деление многократной точности с оста тком u на v: u = wv + t, 0 t v - 1. Затем u := v, v := t, и пе рейти на 1-й ша г. Если же B = 0, то вычислить с помощью арифметики многократной точности t := Au + Bv, w := Cu + Dv, затем присвоить u := t, v := w. Перейти на 1 шаг.

Конец алгоритма.

Обобщенный бинарный алгоритм.

На входе алгоритма заданы a, b N, a b. На выходе d = = НОД(a, b) N и числа u, v Z такие, что au + bv = d. Используют ся вспомогательные переменные многократной точности v1, v3, t1, t и две булевы переменные f1, f2.

Приложение 1 шаг. (Одноразовое уменьшение размера.) Если a < b, то поменять местами a и b и присвоить f1 := 1. Иначе f1 := 0. Если b = 0, то выдать (u, v, d) = (1, 0, a) при f1 = 0, и (u, v, d) = (0, 1, a) при f1 = 1;

закон чить работу. Иначе поделить с остатком a = bq + r, 0 r < b, и присво ить a := b, b := r.

2 шаг. (Вычисление степеней двойки.) Если b = 0, то выдать (u, v, d) = (0, 1, a) при f1 = 0, (u, v, d) = (1, 0, a) при f1 = 1 и за кончить работу. Иначе k := 0, и до тех пор, пока a и b оба четные, выполнять:

k := k + 1, a := a 2, / b := b 2.

/ 3 шаг. (Инициализация.) Если b четно, то поменять местами a и b и присвоить f2 := 1. Иначе f2 := 0. Далее, u := 1, d := a, v1 := 0, v3 := b.

Если a нечетно, то t1 := 0, t3 := -b, и перейти на 5 шаг. Иначе t1 := (b + 1) 2, t3 := a 2.

/ / 4 шаг (Удаление лишних двоек.) Если t3 четно, то присвоить t3 := t3 2, t1 := t1 2, если t1 четно, / / t3 := t3 2, t1 := (t1 + b) 2, если t1 нечетно, / / и вернуться на 4 шаг.

5 шаг. (Петля.) Если t3 > 0, то u := t1, d := t3;

ина че v1 := b - t1, v3 := -t3.

6 шаг. (Вычитание.) Присвоить t1 := u - v1, t3 := d - v3.

Если t1 < 0, то t1 := t1 + b. Если t3 = 0, то перейти на 4-й ша г.

7 шаг. (Окончание.) Присвоить v := (d - au) b, d := 2kd. Если / f2 = 1, то поменять u и v местами. Присвоить u := u - vq. Выдать (u, v, d) при f1 = 1, (v, u, d) при f1 = 0.

Конец алгоритма.

Мы закончим наше Приложение описанием двух методов возведе ния в степень. Пусть G какая-либо мультипликативная группа, g G, — n N. Мы хотим найти h = gn G. Пусть n = bk2k + bk-12k-1 +...

... + b12 + b0 есть двоичное представление n, т. е. bi {0;

1}, bk = 1.

302 Приложение j 1 способ. Сначала находим элементы hj = g2, j = 0, 1,..., k;

при этом h0 = g, hj+1 := hj · hj. За тем на ходим h = hj.

j : bj= Для нахождения h этим способом требуется не более чем 2k + 1 = = O(log n) операций умножения в группе G.

2 способ. Находим последовательно k h = gb 2j-1+bk-12j-2+...+bk-j+1, j = 1, 2,..., k + 1.

j k В начале 1 = g = gb. Далее, если мы уже нашли h, то h := h · h, j j+1 j j если bk-j = 0;

j+1 := j · j · g, если bk-j = 1. В конце h = h = gn.

k+ Здесь также нужно O(log n) операций умножения в группе G.

Преимущество второго способа перед первым заключается в сле j дующем. Пусть мы хотим найти 510000 Z. Степени 52 быстро растут.

В первом способе мы возводим в квадрат и затем перемножаем боль шие числа. Во втором способе при нахождении h мы перемножаем j+ большие числа h · h, но домножаем на g = 5 (при bk-j = 1), т. е. на ма j j ленькое число. В этом заключается существенная экономия.

Описанные способы называются бинарными методами возведе ния в степень.

Литература [1] Акритас А. Основы компьютерной алгебры с приложениями.

М.: Мир, 1994.

[2] Алексеев В. Б. Сложность умножения матриц. Обзор Кибер // нетич. сборн. 1988. Вып. 25. С. 189 236.

— [3] Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черёмушкин А. В.

Основы криптографии. М.: Гелиос АРВ, 2002. 2-е изд.

[4] Анохин М. И., Варновский Н. П., Сидельников В. М., Ящен ко В. В. Криптография в банковском деле. М.: МИФИ, 1997.

[5] Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вы числительных алгоритмов. М.: Мир, 1979.

[6] Березин И. С., Жидков Н. П. Методы вычислений. Т. 1. М.: На ука, 1966.

[7] Берлекэмп Э. Алгебраическая теория кодирования. М.: Мир, 1971.

[8] БоревичЗ. И., ШафаревичИ. Р. Теория чисел. М.: Наука, 1985.

[9] Ван дер Варден Б. Л. Алгебра. М.: Наука, 1976.

[10] Василенко О. Н. Современные способы проверки простоты чи сел. Обзор Кибернетич. сборн. 1988. Вып. 25. С. 162 188.

// — [11] Василенко О. Н. Некоторые алгоритмы построения больших простых чисел Вестн. Моск. ун-та. Сер. 1. Матем. Механ.

// 1997. № 5. С. 62 64.

— [12] Василенко О. Н. О некоторых свойствах чисел Ферма Вестн.

// Моск. ун-та. Сер. 1. Матем. Механ. 1998. № 5. С. 56 58.

— [13] Василенко О. Н. Об алгоритме Миллера Рабина Вестн.

— // Моск. ун-та. Сер. 1. Матем. Механ. 2000. № 2. С. 41 42.

— [14] Василенко О. Н. О дискретном логарифмировании в некоторых группах Вестн. Моск. ун-та. Сер. 1. Матем. Механ. 2000. № 5.

// С. 53 55.

— [15] Василенко О. Н. О дискретном логарифмировании по состав ному модулю IV Международная конференция Современные // « проблемы теории чисел и ее приложения. Тула, 10 15 сентяб » — ря, 2001 Тезисы докладов. С. 35 36.

/ — [16] Василенко О. Н. Об одном применении тригонометрических сумм для проверки простоты чисел Вестн. Моск. ун-та. Сер.

// 1. Матем. Механ. 2001. № 5. С. 49 51.

— 304 Литература [17] Василенко О. Н. Применение круговых полей в криптосистемах RSA IV Международная конференция Современные пробле // « мы теории чисел и ее приложения. Тула, 10-15 сентября, » / Тезисы докладов. С 36 37.

— [18] Виноградов И. М. Основы теории чисел. М.: Наука, 1972.

[19] Гантмахер Ф. Р. Теория матриц. М., 1954.

[20] Гашков С. Б. Упрощенное обоснование вероятностного теста Миллера-Рабина для проверки простоты чисел Дискретная // математика. 1998. Т. 10 (4). С. 35 38.

— [21] Григорьев Д. Ю. Разложение многочленов над конечным полем и решение систем алгебраических уравнений Зап. науч. семин.

// ЛОМИ АН СССР. 1984. № 137. С. 20–79.

[22] Дэвенпорт Дж., Сирэ И., Турнье Э. Компьютерная алгебра. М.:

Мир, 1991.

[23] Карацуба А. А., Офман Ю. П. Умножение многозначных чисел на автоматах ДАН СССР. 1961. Т. 145 (2). С. 293 294.

// — [24] Касселс Дж. Введение в геометрию чисел. М.: Мир, 1965.

[25] Кнут Д. Искусство программирования. Т. 2. Получисленные ал горитмы. Вильямс: М. СПб. Киев, 2000. 3-е изда ние.

— — [26] Коновальцев И. В. Об одном алгоритме решения систем линеных уравнений в конечных полях Проблемы кибернетики. 1967.

// Вып. 19. С. 269 274.

— [27] Кострикин А. И. Введение в алгебру. М.: Наука, 1977.

[28] Лемеш А. Н. О -низких числах Тезисы докл. 12 междунар.

// конф. Проблемы теоретической кибернетики. Часть II. Ниж.

« » Новг., 1999. С. 135.

[29] Ленг С. Введение в теорию диофантовых приближений. М.: Мир, 1970.

[30] Ленг С. Эллиптические функции. М.: Наука, 1984.

[31] Лидл Р., Нидеррайтер Г. Конечные поля. T. 1, 2. М.: Мир, 1988.

[32] Матюхин Д. В. Об асимптотической сложности дискретного ло гарифмирования в поле GF(p) Дискретная математика. 2002.

// Т. 15 (1). С. 28 49.

— [33] Матюхин Д. В., Мурашов Н. Н. Модификация метода реше та числового поля для дискретного логарифмирования в поле GF(p) Обозр. прикл. и промышл. матем. 2000. Т. 7 (2).

// C. 387 389, — [34] Нечаев В. И. Сложность дискретного логарифма Научные тру // ды МГПУ. 1994. С. 46–49.

Литература [35] Нечаев В. И. К вопросу о сложности детерминированного алго ритмадля дискретного логарифма Мат. заметки. 1994. Т. 55 (2).

// С. 91 101.

— [36] Нечаев В. И. Элементы криптографии. М.: Высшая школа, 1999.

[37] Ноден П., Китте К. Алгебраическая алгоритмика. М.: Мир, 1999.

[38] Панкратьев Е. В. Компьютерная алгебра. Факторизация мно гочленов. М.: Изд-во МГУ, 1988.

[39] Тоом А. Л. О сложности схемы из функциональных элемен тов, реализующей умножение целых чисел ДАН СССР. 1963.

// Т. 150 (3). С. 496 498.

— [40] Уильямс Х. Проверка чисел на простоту с помощью вычисли тельных машин Кибернетич. сборн. 1986. Вып. 23. С. 51 99.

// — [41] Хинчин А. Я. Цепные дроби. М.: Наука, 1978.

[42] Чебышев П. Л. Полное собрание сочинений. Т. 1. Теория чисел.

Изд-во АН СССР, 1946.

[43] Чистов А. Л. Алгоритм полиномиальной сложности для раз ложения многочленов и нахождения компонент многообразия в субэкспоненциальное время Зап. науч. семин. ЛОМИ АН // СССР. 1984. № 137. С. 124 188.

— [44] Adleman L. A subexponential algorithm for the discrete logarithm problem with applications to cryptography Proc. 20th Ann. IEEE // Symp. Found. Comput. Sci. 1979. P. 55 60.

— [45] Adleman L. The function field sieve Proceedings of ANTS-I.

// 1994. (Lect. Notes in Comput. Sci.;

V. 877). P. 108 121.

— [46] Adleman L., Pomerance C., Rumely R. S. Ondistinguishingprime numbers from composite numbers Ann. Math. 1983. V. 117.

// P. 173 206.

— [47] Adleman L., Huang M.-D. A. Primality testing and abelian varietes over finite fields. 1992. (Lect. Notes in Math.;

V. 1512).

[48] Adleman L., McCurley K. Open problems in number theoretic complexity Proceedings of ANTS-I. 1994. (Lect. Notes in // Comput. Sci.;

V. 877). P. 291 322.

— [49] Adleman L. M., Manders K., Miller G. L. On taking roots in finite fields Proc. 18th Ann. Symp. Found. Comput. Sci. 1977.

// P. 175 178.

— [50] Agrawal M., Kayal N., Saxena N. PRIMES is in P. Preprint, August 2002.

[51] Alford W. R., Granville A., Pomerance C. There are infinitely many Carmichael numbers Ann. Math. 1994. V. 140. P. 703 722.

// — 20 О. Н. Василенко 306 Литература [52] Alford W. R., Granville A., Pomerance C. On the difficulty of finding reliable witnesses (invited talk) Proceedings of ANTS // I. 1994. (Lect. Notes in Comput. Sci.;

V. 877). P. 1 16.

— [53] Alt H. Square rooting is as difficult as multiplication Computing.

// 1979. V. 21. P. 221 232.

— [54] Ankeny N. C. The least quadratic non-residue Ann. Math. 1952.

// V. 55. P. 65 72.

— [55] Apostol T. M. Introduction to analytic number theory. Springer Verlag, 1997.

[56] Atkin A. O. L., Morain F. Elliptic curves and primality proving // Math. Comp. 1993. V. 61 (203). P. 29 67.

— [57] Atkin A. O. L., Morain F. Finding suitable curves for elliptic method of factoring Math. Comp. 1993. V. 60 (201). P. 399 405.

// — [58] Atkins D., Graff M., Lenstra A. K., Leyland P. C. The magic words are squeamish ossifrage Advances in cryptology // — ASIACRYPT’94 (Wollongong, 1994). 1995. (Lecture Notes in Computer Science;

V. 917). P. 263 277.

— [59] Bach E., Shallit J. Factoring with cyclotomic polynomials Math.

// Comp. 1989. V. 52 (185). P. 201 219.

— [60] Bach E., Shallit J. Algorithmic number theory. V. 1. MIT Press, 1996.

[61] Baker R. C., Harman G. The Brun Titchmarsh theorem on — average Proc. Conf. in Honour of Heini Halberstam. V. 1. 1996.

// P. 39 103.

— [62] Ben-Or M. Probabilistic algorithms in finite fields Proc. 22nd // Ann. IEEE Symp. Found. Comput. Sci. 1981. P. 394 398.

— [63] Berlekamp E. R. Factoring polynomials over finite fields Bell // System Tech. J. 1967. V. 46. P. 1853 1859.

— [64] Bernstein D. J. Detecting perfect powers in essentially linear time // Math. Comp. 1998. V. 67 (223). P. 1253 1283.

— [65] Blake I. F., Seroussi G., Smart N. P. Elliptic curves in cryptography. Cambridge University Press, 1999.

[66] Boender H., te Riele H. J. J. Factoring integers with large prime variations of the quadratic sieve CWI Report NM-R9513. 1995.

/ [67] Borodin A. B., Munro I. The computational complexity of algebraic and numeric problems. N. Y.: American Elsevier, 1975.

[68] Bosma W., van der Hulst M. P. Faster primality testing (extended abstract) Advances in Cryptology EuroCrypt’89 Jean // — / Jacques Quisquater and Joos Vandewalle, editors. Berlin: Springer Verlag, 1989. (Lect. Notes in Comput. Sci.;

V. 434). P. 652 656.

— Литература [69] Bosselaerts A., Govaerts R., Vandewalle J. Comparison of three modular reduction functions Advances in Cryptology // — Crypto’93 Douglas R. Stinson, editor. Berlin: Springer-Verlag, / 1993. (Lect. Notes in Comput. Sci.;

V. 773). P. 175 186.

— [70] Brassard G., Monet S., Zuffelato D. Algorithmes pour l’arithmetique des tres grands entiers Techniques and Science // Informatique. 1986. V. 5. P. 89 102.

— [71] Brent R. P. An improved Monte Carlo factorization algorithm // BIT. 1980. V. 20. P. 176 184.

— [72] Brent R. P. Some integer factorization algorithms using elliptic curves Austral. Comput. Sci. Comm. 1986. V. 8. P. 149 163.

// — [73] Brent R. P. Factorization of the tenth Fermat number Math.

// Comp. 1999. V. 68. P. 429 451.

— [74] Brent R. P. Some parallel algorithms for integer factorisation // Lect. Notes in Comput. Sci. 1999. V. 1685. P. 1 22.

— [75] Brent R. P., Pollard J. M. Factorization of the eighth Fermat number Math. Comp. 1981. V. 36. P. 627 630.

// — [76] Brentjes A. J. Multidimensional continued fraction algorithms.

Amsterdam, 1981. (Mathematical Centre Tracts;

V. 145).

[77] Bressoud D. M. Factorization and primality testing. Springer Verlag, 1989.

[78] Brillhart J. Anote on finding depencensies over GF(2) Utilitas // Math. 1989. V. 36. P. 211 213.

— [79] Brillhart J., Morrison M. A. A method of factoring and the factorization of F7 Math. Comp. 1975. V. 29. P. 183 205.

// — [80] Brillhart J., Tonascia J., Weinberger P. Onthe Fermat quotient // Computers in number theory. London, N. Y.: Acad. Press, 1971.

P. 213 222.

— [81] Buchberger B., Winkler F. Grbner bases and applications.

Cambridge Univ. Press, 1998. (London Math. Soc. Lecture Notes Series;

V. 251).

[82] Buchmann J., Jacobson M. J., Teske E. On some computational problems in finite abelian groups Math. Comp. 1997. V. 66 (220).

// P. 1663 1687.

— [83] Buchmann J., Weber D. Discrete logarithms: Recent progress // Proc. Internat Conf. on Coding Theory, Cryptography and Related Areas, Guanajuato. Springer-Verlag, 2000. P. 42 56.

— [84] Buell D. A. Binary quadratic forms: classical theory and modern computations. Springer-Verlag, 1989.

20* 308 Литература [85] Cantor D. G., Zassenhaus H. A new algorithm for factoring polynomials over finite fields Math. Comp. 1981. V. 36.

// P. 587 592.

— [86] Caron T. R., Silverman R. D. Parallel implementation of the quadratic sieve. J. Supercomputing. 1988. V. 1. P. 273 290.

— [87] Cavallar S., Dodson B., Lenstra A. K., Leyland P. C., Lioen W. M., Montgomery P. L., Murphy B., te Riele H. J. J., Zimmerman P. Factorization of RSA-140 using the number field sieve CWI Report MAS-R9925, September 1999.

/ [88] Cavallar S., Lioen W. M., te Riele H. J. J., Dodson B., Lenstra A. K., Montgomery P. L., Murphy B. et al. Factorization of 512-bit RSA-modulus CWI Report MAS-R0007, February / 2000.

[89] Cohen H. A course in computational algebraic number theory.

Springer-Verlag, 1993.

[90] Cohen H., Lenstra H. W. Primality testing and Jacobi sums // Math. Comp. 1984. V. 42 (165). P. 297 330.

— [91] Comba P. G. Experiments in fast multiplication of integers / Technical Report G320-2158, IBM, Cambridge Scientific Center, February 1989.

[92] Comba P. G. Exponentiation cryptosystems on IBM PC IBM // Systems J. 1990. V. 29 (4). P. 29 37.

— [93] Contini S. Factoring integers with the self initializing quadratic sieve Master’s thesis. Univ. Georgia, 1997.

/ [94] Cook S. A. On the minimum computation time of functions / Doctoral thesis. Harvard University, Cambridge, Mass., 1966.

[95] Coppersmith D. Fast evaluation of discrete logarithms in fields of characteristic two. IEEE Trans Inform. Theory. 1984. V. 30 (4).

// P. 587 594.

— [96] Coppersmith D. Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm Math. Comp. 1994. V. 62 (205).

// P. 333 350.

— [97] Coppersmith D., Odlyzko A., Schroeppel R. Discrete logarithms in GF(p) Algorithmica. 1986. V. 1. P. 1 15.

// — [98] Coppersmith D., Winograd S. On the asymptotic complexity of matrix multiplication SIAM J. Comput. 1982. V. 11. P. 472 492.

// — [99] Couvreur C., Quisquater J. J. An introduction to fast generation of large primes Philips J. Res. 1982. V. 37. P. 231 264. Errata in:

// — 1983. V. 38. P. 77.

Литература [100] Cox D., Little J., O’Shea D. Ideals, verietes and algorithms. N. Y.:

Springer-Verlag, 1992. (Undergraduate Texts in Mathematics).

[101] Crandall R., Pomerance C. Prime numbers: a computational perspective. Springer-Verlag, 2001.

[102] de Weger B. Algorithms for Diophantine equations Dissertation.

/ Centrum voor Wiskunde en Informatica, Amsterdam, 1988.

[103] Denny T., Mller V. On the reduction of composed relations from the number field sieve Proceedings of ANTS-II. 1996. (Lect.

// Notes in Comput. Sci.;

V. 1122). P. 75 90.

— [104] Denny T. F. Lsen groer dnnbesetzter Gleichungssysteme ber endlichen Primkrpern Dissertation. Universitt des Saarlandes, / Saarbrcken, 1997.

[105] Diaz A., Hitz M., Kaltofen E., Lobo A. Process scheduling in DSC and the large sparce linear systems challenge Lect. Notes // in Comput. Sci. 1993. V. 722. P. 66 80.

— [106] Dixon B., Lenstra A. K. Massively parallel elliptic curve factoring // Lect. Notes in Comput. Sci. V. 658. 1993. P. 183 193.

— [107] Dodson B., Lenstra A. K. NFS with four large primes: an explosive experiment Advances in Cryptology Crypto’95. 1995. (Lect.

// — Notes in Comput. Sci.;

V. 963). P. 372 385.

— [108] ElGamal T. A subexponential-time algorithm for computing discrete logarithms over GF(p2) IEEE Trans. Inform. Theory.

// 1985. V. 31. P. 473 481.

— [109] ElGamal T. On computing logarithm over finite fields Advances // in cryptology CRYPTO’85 (Santa Barbara, Calif., 1985). 1986.

— (Lect. Notes in Comput. Sci.;

V. 218). P. 396 402.

— [110] Elkenbracht-Huizing M. An implementation of the number field sieve Experimental Mathematics. 1996. V. 5. P. 231 253.

// — [111] Elkenbracht-Huizing M. A multiple polynomial general number field sieve Proceedings of ANTS-II. 1996. (Lect. Notes in // Comput. Sci.;

V. 1122). P. 99 114.

— [112] Elkenbracht-Huizing M. Factoring integers with the number field sieve PhD thesis. Leiden Univ., 1997.

/ [113] Elkies N. D. Elliptic and modular curves over finite fields and related computaional issues Computational perspectives in number // theory: Proc. of a Conf. in Honor of A. O. L. Atkin J. T. Teitelbaum / and D. A. Buell, editors. 1998. (Amer. Math. Soc. Inf. Press;

V. 7).

P. 21 76.

— [114] Ernvall R., Mtsankla T. On the p-divisibility of Fermat quotients Math. Comp. 1997. V. 66 (219). P. 1353 1365.

// — 310 Литература [115] Fagin B. S. Large integers multiplication on massively parallel processors Proc. Frontiers’90: Third Symp. on the Frontiers of // Massively Parallel Computation. IEEE Press, 1990. P. 38 42.

— [116] Ferguson H. R. P. A short proof of the existence of vector Eucledian algorithm Proc. Amer. Math. Soc. 1986. V. 97. P. 8 10.

// — [117] Ferguson H. R. P. A non-inductive GL(n, 2) algorithm that constructs integral linear relations for n Z-linearly dependent real numbers J. Algorithms. 1987. V. 8 (1). P. 131 142.

// — [118] Ferguson H. R. P., Bailey D. H., Arno S. Analysis of integer relation finding algorithm Math. Comp. 1999. V. 68 (225). P. 351 369.

// — [119] Ferguson H. R. P., Forcade R. W. Generalization of the Eucledian algorithm for real numbers to all dimensions higher than two // Bull. Amer. Math. Soc. (N. S.). 1979. V. 1. P. 912 914.

— [120] Ferguson H. R. P., Forcade R. W. Multidimensional Eucledian algorithms J. Reine Angew. Math. 1982. V. 334. P. 171 181.

// — [121] Fincke U., Pohst M. Improved methods for calculating vectors of short length in a lattice, including acomplexity analysis Math.

// Comp. 1985. V. 44. P. 463 471.

— [122] Fleischmann P. Connections between the algorithms of Berlekamp and Niederraiter for factoring polynomials over Fq Linear Algebra // and Applications. 1993. V. 192. P. 101 108.

— [123] Fouvry E. Theoreme de Brun-Titchmarsh: application an theoreme de Fermat Invent. Math. 1985. V. 79. P. 383 407.

// — [124] Garner H. The residue number system IRE Transactions on // Electronic Computers. 1959. V. 8. P. 140 147.

— [125] Gianni P., Mora T. Algebraic solution of systems of polynomial equations using Grbner bases Applied algebra, algebraic // algorithms and error-correcting codes (Menorca, 1987). 1989.

(Lect. Notes in Comput. Sci.;

V. 356). P. 247 257.

— [126] Goldwasser S., Kilian J. Almost all primes can be quickly certified Proc. 18-th Ann. ACM Symp. on Theory of Computing.

// 1986. P. 316 329.

— [127] Gordon D. Discrete logarithms in GF(p) using the number field sieve SIAM J. Disc. Math. 1993. V. 6. P. 124 138.

// — [128] Gordon D. M., McCurley K. S. Massively parallel computation of discrete logarithms Advances in Cryptology Crypto’ // — / Ernest F. Brickell, editor. Berlin: Springer-Verlag, 1993. (Lect.

Notes in Comput. Sci.;

V. 740). P. 312 323.

— Литература [129] Hastad J., Just B., Lagarias J. C., Schnorr C. P. Polynomial time algorithms for finding integer relations among real numbers // SIAM J. Comput. 1989. V. 18. P. 859 881.

— [130] Hellman M. E., Reyneri J. M. Fast computation of discrete logarithms in GF(q) Advances in Cryptology CRYPTO’82.

// — N. Y.: Plenum Press, 1983. P. 3 13.

— [131] Herlestam T., Johannesson R. On computing logarithms over GF(2p) BIT. 1981. V. 21. P. 326 336.

// — [132] Hong S. M., Oh S. Y., Yoon H. New modular multiplication algorithms for fast modular exponentiation Lect. Notes in // Comput. Sci. 1996. V. 1070. P. 166 177.

— [133] Izu T., Kogure J., Noro M., Yokoyama K. Efficient implementation of Schoof’s algorithm Advances in cryptology ASIACRYPT’ // — (Beijing). 1998. (Lect. Notes in Comput. Sci.;

V. 1514). P. 66 79.

— [134] Joux A., Lercier R. Improvements to the general number field sieve for discrete logarithms in prime fields. Preprint.

http://www.medicis.polytechnique.fr/~lercier.

[135] Joux A., Lercier R. Discrete logarithms in GF(p) e-mail to the / NMBRTHRY mailing list, January 2001.

http://listserv.nodak.edu/archives/nmbrthry.html.

[136] Joux A., Lercier R. Discrete logarithms in GF(p) e-mail to the / NMBRTHRY mailing list, April 2001.

http://listserv.nodak.edu/archives/nmbrthry.html.

[137] Kaltofen E. Polynomial factorization 1987 1991 LATIN’ — // (So Paulo, 1992). 1992. (Lect. Notes in Comput. Sci.;

V. 583).

P. 294 313.

— [138] Kaltofen E. Analysis of Coppersmith’s block Wiedemann algorithm for the parallel solution of sparce linear systems Applied algebra, // algebraic algorithms and error-correcting codes (San Juan, PR, 1993). 1993. (Lect. Notes in Comput. Sci.;

V. 673). P. 195 212.

— [139] Kaltofen E., Lobo A. Factoring high-degree polynomials by the black box Berlekamp algorithm Proceedings of ISSAC’94. ACM // Press, 1994. P. 90 98.

— [140] Kaltofen E., Sanders B. D. On Wiedemann’s method of solving sparce linear systems Applied algebra, algebraic algorithms and // error-correcting codes (New Orleans, LA, 1991). 1991. (Lect. Notes in Comput. Sci.;

V. 539). P. 29 38.

— [141] Kaltofen E., Shoup V. Fast polynomial factorization over high algebraic extensions of finite fields Proceedings of ISSAC’97.

// ACM Press, 1997. P. 184 188.

— 312 Литература [142] Kaltofen E., Shoup V. Subquadratic-time factoring of polynomials over finite fields Math. Comp. 1998. V. 67 (223). P. 1179 1197.

// — [143] Kannan R., Lenstra A. K., Lovasz L. Polynomial factorization and nonrandomness of bits of algebraic and some transcendental numbers Math. Comp. 1988. V. 50 (181). P. 235 250.

// — [144] Koblitz N. A course in number theory and cryptography. Springer Verlag, 1987.

[145] Koblitz N. Elliptic curve cryptosystems Math. Comp. 1987. V. 48.

// P. 203 209.

— [146] Koblitz N. Algebraic aspects of cryptography. Springer-Verlag, 1998.

[147] Konyagin S., Shparlinski I. Linear complexity of discrete logarithm. Preprint, December 2000.

[148] Konyagin S. V., Pomerance C. On primes recognizable in deterministic polynomial time Algorithms and combinatorics.

// Springer-Verlag, 1997. (The mathematics of Paul Erds;

V. 1).

P. 176 198.

— [149] LaMacchia B. Basis reduction algorithms and subset sum problems Thesis. MIT Artifical Intelligence Lab., 1991.

/ [150] LaMacchia B., Odlyzko A. Solving large sparse linear systems over finite fields Advances in Cryptology CRYPTO’90. 1990.

// — (Lecture Notes in Computer Science;

V. 537). P. 109 133.

— [151] LaMacchia B. A., Odlyzko A. M. Computation of discrete logarithm in prime fields Des. Codes Cryptogr. 1991. V. 1.

// P. 47 62.

— [152] Lambert R. Computational aspects of discrete logarithms PhD / thesis. Univ. of Waterloo, Dept. Electrical Comp. Eng., 1996.

[153] Lanczos C. Solution of systems of linear equations by minimized iterations J. Res. Nat. Bur. Standards. 1952. V. 49. P. 33 53.

// — [154] Lay G.-J., Zimmer H. G. Constructing elliptic curves with given group order over large finite fields Algorithmic number theory // (Ithaca, NY, 1994). 1994. (Lect. Notes in Comput. Sci.;

V. 877).

P. 250 263.

— [155] Lazard D. Resolution des systems d’equations algebraiques // Theor. Comput. Sci. 1981. V. 15. P. 77 110.

— [156] Lazard D. Ideal basis and primary decomposition: case of two variables J. Symb. Comput. 1985. V. 1. P. 261 270.

// — [157] Lazard D. Solving zero-dimensional algebraic systems J. Symb.

// Comput. 1992. V. 13. P. 117 131.

— Литература [158] Lehman R. S. Factoring large integers Math. Comp. 1974. V. 28.

// P. 637 646.

— [159] Lenstra A. K., Lenstra H. W., editors. The development of the number field sieve. 1993. (Lecture Notes in Mathematics;

V. 1554).

[160] Lenstra A. K., Lenstra H. W., Lovsz L. Factoring polynomials with rational coefficients Math. Ann. 1982. V. 261. P. 515 534.

// — [161] Lenstra A. K., Lenstra H. W., Manasse M. S., Pollard J. M. The number field sieve Proc. 22nd ACM Symposium on Theory of // Computing. 1990. P. 564 572.

— [162] Lenstra A. K., Lenstra H. W., Manasse M. S., Pollard J. M. The factorization of the ninth Fermat number Math. Comp. 1993.

// V. 61 (203). P. 319 349.

— [163] Lenstra A. K., Manasse M. S. Factoring with two large primes // Math. Comp. 1994. V. 63. P. 785 798.

— [164] Lenstra H. W. Primality testing algorithms (after Adleman, Rumely and Williams) Bourbaki Seminar. V. 1980 81. 1981. (Lect. Notes // / in Math.;

V. 901). P. 243 257.

— [165] Lenstra H. W. Divisors in residue classes Math. Comp. 1984.

// V. 42 (165). P. 331 340.

— [166] Lenstra H. W. Elliptic curves and number-theoretic algorithms // International Congress of Mathematicians. 1986. P. 99 120.

— [167] Lenstra H. W. Factoring integers with elliptic curves Ann. Math.

// 1987. V. 126. P. 649 673.

— [168] Lenstra H. W. Finding isomorphisms between finite fields Math.

// Comp. 1991. V. 56 (193). P. 329 347.

— [169] Lenstra H. W., Pomerance C. A rigorous time bound for factoring integers J. Amer. Math. Soc. 1992. V. 5 (3). P. 483 516.

// — [170] Lerch M. Zur Theorie des Fermatischen Quotienten ap-1 - = q(a) Math. Ann. 1905. V. 60. P. 471 490.

// — p [171] Lercier R. Algorithmique des courbes dans les corps finis These.

/ L’Ecole Polytechnique, Laboratoire D’Informatique, CNRC, Paris, 1997.

[172] Li T. Y. Solving polynomial systems Math. Intelligencer. 1987.

// V. 9. P. 33 39.

— [173] Lovorn Bender R. Rigorous, subexponential algorithms for discrete logarithms in GF(p2) SIAM J. Discrete Math., to appear.

// 314 Литература [174] Lovorn Bender R., Pomerance C. Rigorous discrete logarithm computations in finite fields via smooth polynomials // Computational perspectives in number theory (Chicago, 1995).

Amer. Math. Soc., 1998. (AMS IS Stud. Adv. Math.;

V. 7).

/ P. 221 232.

— [175] Massey J. L. Shift-register synthesis and BCH decoding IEEE // Trans. Inform. Theory. 1969. V. 15. P. 122 127.

— [176] McCurley K. S. The discrete logarithm problem Cryptology and // computational number theory (Boulder, CO, 1989). Amer. Math.

Soc., 1990. (Proc. of Symp. Appl. Math.;

V. 42). P. 49 74.

— [177] McCurley K. S. Odds and ends from cryptology and computational number theory Cryptology and computational number theory // (Boulder, CO, 1989). Amer. Math. Soc., 1990. (Proc. of Symp.

Appl. Math.;

V. 42). P. 145 166.

— [178] McKee J. Speeding Fermat’s factoring method Math. Comp.

// 1999. V. 68 (228). P. 1729 1737.

— [179] Menezes A. Elliptic curve public key cryptosystems. Kluwer Acad.

Publ., 1993.

[180] Menezes A., Van Oorschot P. C., Vanstone S. A. Handbook of applied cryptography. CRC Press, 1997.

[181] Menezes A., Qu M., Vanstone S. IEEE P1363 Standard, Part 4:

Elliptic curve systems, 1995.

[182] Menezes A. J., Vanstone S. A., Zuccherato R. J. Counting points m on elliptic curves over F2 Math. Comp. 1993. V. 60 (201).

// P. 407 420.

— [183] Mignotte M. An inequality about factors of polynomials Math.

// Comp. 1974. V. 28. P. 1153 1157.

— [184] Mihailescu P. Cyclotomic primality proving recent — developments Proceedings of ANTS-III. 1998. (Lect. Notes in // Comput. Sci.;

V. 1423). P. 95 110.

— [185] Mihailescu P. Cyclotomy of rings and primality testing PhD / thesis. Swiss Federal Institute of Technology, Zrich, 1998.

[186] Mihailescu P. Fast generation of provable primes using search in arithmetic progressions. Preprint, 1998.

[187] Miller G. L. Riemann’s hypothesis and tests for primality // J. Comput. and Syst. Sci. 1976. V. 13. P. 300 317. [Перевод:

— Кибернетический сборник. 1986. Вып. 23. С. 31 50.] — [188] Miller V. Use of elliptic curves in cryptography Advances in // cryptology CRYPTO’85 (Santa Barbara, Calif., 1985). 1986.

— (Lecture Notes in Comput. Sci.;

V. 218). P. 417 426.

— Литература [189] Miyaji A. Elliptic curves over Fp suitable for cryptosystems // Advances in cryptology AUSCRYPT’92 (Gold Coast, 1992).

— 1993. (Lect. Notes in Comput. Sci.;

V. 718). P. 479 471.

— [190] Monier L. Evaluation and comparision of two efficient probabilistic primality testing algorithms Theor. Comput. Sci. 1980. V. 12.

// P. 97 108.

— [191] Montgomery P. L. Modular multiplication without trial division // Math. Comp. 1985. V. 44 (170). P. 519 521.

— [192] Montgomery P. L. Speeding the Pollard and elliptic curve methods of factorization Math. Comp. 1987. V. 48 (177). P. 243 264.

// — [193] Montgomery P. L. A block Lanczos algorithm for finding dependencies over GF(2) Advances in Cryptology // — EuroCrypt’95 Louis C. Guillou and Jean-Jacques Quisquater, / editors. Berlin: Springer-Verlag, 1995. (Lect. Notes in Comput.

Sci.;

V. 921). P. 106 120.

— [194] Montgomery P. L., Silverman R. D. A FFT-extension to the p - factoring algorithm Math. Comp. 1990. V. 54 (190). P. 839 854.

// — [195] Morain F. Atkin’s test: news from the front. Preprint.

[196] Morain F. Elliptic curves, primality proving and some titanic primes. Preprint.

[197] Morain F. Solving equations of small degree modulo large primes.

Preprint.

[198] Morain F. Distributed primality proving and the primality of (23539 + 1) 3. Preprint, 1990.

/ [199] Morain F. Primality proving using elliptic curves: an update // Proceedings of ANTS-III. 1998. (Lect. Notes in Comput. Sci.;

V. 1423). P. 111 127.

— [200] Morain F., Olivos J. Speeding up the computations on an elliptic curve using addition-subtraction chains Inform. Theor. et Appl.

// 1990. V. 24. P. 531 544.

— [201] Mullen G. L., White D. A polynomial representation for logarithms in GF(q) Acta Arithm. 1986. V. 47. P. 255 261.

// — [202] Mller V. Ein Algorithmus zur Bestimmung der Punktzahl elliptischer Kurvenber endlichen Krpern der Characteristic grssen drei PhD thesis, Universitt des Saarlandes, 1995.

/ [203] Murphy B. A. Modelling the yield of number field sieve polynomials Proceedings of ANTS-III. 1998. (Lect. Notes in // Comput. Sci.;

V. 1423). P. 137 150.

— 316 Литература [204] Murphy B. A. Polynomial selection for the number field sieve integer factorisation algorithm PhD thesis. Australian National / University, July 1999.

[205] Murphy B. A., Brent R. P. On quadratic polynomials for the number field sieve Austral. Comput. Sci. Comm. 1998. V. 20. P. 199 213.

// — [206] Niederreiter H. A new efficient factorization algorithm for polynomials over small finite fields Appl. Algebra Engrg. Comm.

// Comput. 1993. V. 4. P. 81 87.

— [207] Niederreiter H., Gttfert R. Factorization of polynomials over finite fields and characteristic sequences J. Symbolic Computation.

// 1993. V. 16 (5). P. 401 412.

— [208] Odlyzko A. Discrete logarithms and smooth polynomials // Contemp. Math. 1994. V. 168. P. 269 278.

— [209] Odlyzko A. Discrete logarithms: the past and the future Designs, // Codes and Cryptography. 2000. V. 19. P. 129 145.

— [210] Odlyzko A. M. Discrete logarithms in finite fields and their cryptographic significance Advances in Cryptology: Proceedings // of EuroCrypt’84 Thomas Beth, Norbert Cot, and Ingemar / Ingemarsson, editors. Berlin: Springer-Verlag, 1984. (Lect. Notes in Comput. Sci.;

V. 209). P. 224 316.

— [211] Odlyzko A. M. The future of integer factorization CryptoBytes.

// 1995. V. 1 (2). P. 5 12.

— [212] Parkinson D., Wunderlich M. A compact algorithm for Gaussian elimination over GF(2) implemented on highly parallel computers // Parallel Computing. 1984. V. 1. P. 65 73.

— [213] Peralta R. Implementation of the hypercube multiple polynomial sieve. Preprint.

[214] Plaisted D. A. Fast verification, testing and generation of large primes Theoret. Comp. Sci. 1979. V. 9. P. 1 16. Errata in: 1981.

// — V. 14. P. 345.

[215] Pohlig S., Hellman M. An improved algorithm for computing logarithms over GF(p) and its cryptographic significance IEEE // Trans. Inform. Theory. 1978. V. 24. P. 106 110.

— [216] Pohst M. A modification of the LLL-reduction algorithm // J. Symb. Comp. 1987. V. 4. P. 123 128.

— [217] Pohst M., Zassenhaus H. Algorithmic algebraic number theory.

Cambridge University Press, 1989.

[218] Pollard J. M. Theorems on factorization and primality testing // Proc. Cambridge Phil. Soc. 1974. V. 76. P. 521 528.

— Литература [219] Pollard J. M. A Monte Carlo method for factorization BIT. 1975.

// V. 15. P. 331 334.

— [220] Pollard J. M. Monte Carlo methods for index computation (mod p) Math. Comp. 1978. V. 32 (143). P. 918 924.

// — [221] Pomerance C. Analysis and comparision of some integer factoring algorithms Computational methods in number theory.

// V. 1 H. W. Lenstra and R. Tijdeman, editors. Amsterdam, 1982.

/ P. 89 139.

— [222] Pomerance C. The quadratic sieve factoring algorithm Advances // in cryptology (Paris, 1984). 1985. (Lecture Notes in Comput. Sci.;

V. 209). P. 169 183.

— [223] Pomerance C. Fast, rigorous factorization and discrete logarithms Discrete Algorithms and complexity A. Nozaki // / D. S. Johnson, T. Nishizeki and H. S. Wilf, editors. Orlando: Acad.

Press, 1987. P. 119 144.

— [224] Pomerance C. Very short primality proofs Math. Comp. 1987.

// V. 48 (177). P. 315 322.

— [225] Pomerance C. Factoring Proc. of Symp. Appl. Math. 1990. V. 42.

// P. 24 47.

— [226] Pomerance C. The number field sieve Proc. of Symp. Appl. Math.

// 1994. V. 48. P. 465 480.

— [227] Pomerance C. A tale of two sieves Notices Amer. Math. Soc.

// 1996. V. 43. P. 1473 1485.

— [228] Pomerance C., Selfridge J. L., Wagstaff S. S. The pseudoprimes to 2.5 · 109 Math. Comp. 1980. V. 36 (151). P. 1003 1026.

// — [229] Pomerance C., Smith J. W., Tuler R. A pipeline architecture for factoring large integers with the quadratic sieve algorithm SIAM // J. Comput. 1988. V. 17 (2). P. 387 403.

— [230] Rabin M. Probabilistic algorithms for testing primality J. Number // Theory. 1980. V. 12. P. 128 138.

— [231] Ribenboim P. The book of prime number records. Springer-Verlag, 1988.

[232] Ribenboim P. The new book of prime number records. Springer Verlag, 1996.

[233] Riesel H. Prime numbers and computer methods for factorization.

Birkhauser, 1985. (Progr. in Math.;

V. 57).

[234] Riesel H. Some soluble cases of the discrete logarithm problem // BIT. 1988. V. 28 (4). P. 839 851.

— 318 Литература [235] Satoh T., Araki K. Fermat quotients and polynomial time discrete log algorithm for anomalous elliptic curves Comment. Math.

// Univ. Sancti Pauli. 1998. V. 47. P. 81 92.

— [236] Schirokauer O. Discrete logarithms and local units. Phil. Trans.

R. Soc. Lond. A. 1993. V. 345. P. 409 423.

— [237] Schirokauer O. Using number fields to compute discrete logarithms in finite fields Math. Comp. 2000. V. 69. P. 1267 1283.

// — [238] Schirokauer O., Weber D., Denny T. Discrete logarithms: the effectiveness of the index calculus method Proceedings of ANTS // II. 1996. (Lect. Notes in Comput. Sci.;

V. 1122). P. 337 362.

— [239] Schnorr C. P. A more efficient algorithm for lattice basis reduction J. Algorithms. 1988. V. 9. P. 47 62.

// — [240] Schnorr C. P., Euchner M. Lattice basis reduction: improved practical algorithms and solving subset sum problems // Fundamentals of computation theory (Gosen, 1991). 1991. (Lect.

Notes in Comput. Sci.;

V. 529). P. 68 85.

— [241] Schnorr C. P., Lenstra H. W. A Monte-Carlo factoring algorithm with linear storage Math. Comp. 1984. V. 43. P. 289 312.

// — [242] Schnhage A. The fundamental theorem of algebra in terms of computational complexity Preliminary report, 1982. Math.

/ Institute Univ. Tbingen.

[243] Schnhage A., Grotfeld A. F. W., Vetter E. Fast algorithms:

a multitape Turing mashine implementation. Mannheim: BI Wissenschaftsverlag, 1994.

[244] Schoof R. Elliptic curves over finite fields and the computation of square roots modp Math. Comp. 1985. V. 44. P. 483 494.

// — [245] Schoof R. Counting points on elliptic curves over finite fields // J. Theorie des Nombres des Bordeaux. 1995. V. 7. P. 219 254.

— [246] Sedgewick R., Szymanski T. G., Yao A. C. The complexity of finding cycles in periodic functions SIAM J. Comput. 1982.

// V. 11 (2). P. 376 390.

— [247] Semaev I. A. An algorithm for evaluation of discrete logarithms in some nonprime finite fields Math. Comp. 1998. V. 67.

// P. 1679 1689.

— [248] Shanks D. Class number, a theory of factorization and genera // Proc. Symp. Pure Math. V. 20. Providence, R. I.: AMS, 1971.

P. 415 440.

— [249] Shoup V. The deterministic complexity of factoring polynomials over finite fields Inform. Process. Lett. 1990. V. 33 (5).

// P. 261 267.

— Литература [250] Shoup V. New algorithm for finding irreducible polynomials over finite fields Math. Comp. 1990. V. 54. P. 435 447.

// — [251] Shoup V. Searching for primitive roots in finite fields Math.

// Comp. 1992. V. 58 (197). P. 369 380.

— [252] Shoup V. Fast construction of irreducible polynomials over finite fields J. Symbolic Comput. 1994. V. 17 (5). P. 371 391.

// — [253] Shoup V. A new polynomial factorization algorithm and its implementation J. Symbolic Comput. 1995. V. 20. P. 364 397.

// — [254] Shoup V. Lower bounds for discrete logarithms and related problems Advances in Cryptology EuroCrypt’97 Walter // — / Fumy, editor. Berlin: Springer-Verlag, 1997. (Lect. Notes in Comput. Sci.;

V. 1233). P. 256 266.

— [255] Shparlinski I. E. Number theoretic methods in cryptography:

Complexity lower bounds. Birkhuser, 1999.

[256] Silverman J. H. The arithmetic of elliptic curves, Springer-Verlag, 1986. (Graduate Texts in Mathematics;

V. 106).

[257] Silverman J. H. Advanced topics in the arithmetic of elliptic curves.

Springer-Verlag, 1994. (Graduate Texts in Mathematics;

V. 151).

[258] Silverman R. D. The multiple polynomial quadratic sieve Math.

// Comp. 1987. V. 48 (177). P. 329 339.

— [259] Silverman R. D. Fast generation of random strong RSA primes.

Preprint. RSA Laboratories, 1997.

[260] Silverman R. D., Wagstaff S. S. A practical analysis of the elliptic curve factoring algorithm Math. Comp. 1993. V. 61. P. 445 462.

// — [261] Solinas J. A. An improved algorithm for arithmetic on a family of elliptic curves Advances in Cryptology Crypto’97 Burt // — / Kaliski, editor. Berlin: Springer-Verlag, 1997. (Lecture Notes in Computer Science;

V. 1294). P. 357 371.

— [262] Solovay R., Strassen V. A fast Monte-carlo test for primality // SIAM J. Comput. 1977. V. 6. P. 84 85. Errata in: 1978. V. 7.

— P. 117.

[263] Stewart I., Tall D. Algebraic number theory. London N. Y.:

— Chapman and Hall, 1986.

[264] Strassen V. Einige Resultate ber Berechnungskomplexitt // Jahresber. Deutsch. Math.-Verein. 1976 77. V. 78. P. 1 8.

/ — [265] te Riele H. 227-digit SNFS factorization.

ftp://ftp.cwi.nl/pub/herman/SNFSgiants/SNFS-227, January 2002.

320 Литература [266] te Riele H. J. J., Lioen W., Winter D. Factoring with the quadratic sieve on large vector computers Belgian J. Comp. Appl. Math.

// 1989. V. 27. P. 267 278.

— [267] Teske E. Speeding up Pollard’s rho method for computing discrete logarithms Proceedings of ANTS-III. 1998. (Lect. Notes in // Comput. Sci.;

V. 1423). P. 541 554.

— [268] Teske E. Square root algorithms for the discrete logarithm problem (a survey). Preprint, January 2001.

[269] Thom E. Computation of discrete logarithms in GF(2607) // Advances in Cryptology AsiaCrypt’2001. 2001. (Lect. Notes in — Comput. Sci.;

V. 2248). P. 107 124.

— [270] Thom E. Discrete logarithms in GF(2607). e-mail to the NMBRTHRY mailing list, February 2002.

http://listserv.nodak.edu/archives/nmbrthry.html.

[271] Turk J. W. M. Fast arithmetic operations on numbers and polynomials Computational methods in number theory.

// V. 2 H. W. Lenstra and R. Tijdeman, editors. Amsterdam, 1982.

/ P. 43 54.

— [272] von zur Gathen J., Shoup V. Computing Frobenius maps and factoring polynomials Comput. Complexity. 1992. V. 2.

// P. 187 224.

— [273] Voorhoeve M. Factorization algorithms of exponential order // Computational methods in number theory. V. 1 H. W. Lenstra and / R. Tijdeman, editors. Amsterdam, 1982. P. 79 88.

— [274] Weber D. An implementation of the general number field sieve to compute discrete logarithms modp Advances in Cryptology // — EuroCrypt’95 Louis C. Guillou and Jean-Jacques Quisquater, / editors. Berlin: Springer-Verlag, 1995. (Lecture Notes in Computer Science;

V. 921). P. 95 105.

— [275] Weber D. Computing discrete logarithms with the general number field sieve Proceedings of ANTS-II. 1996. (Lect. Notes in // Comput. Sci.;

V. 1122). P. 391 404.

— [276] Weber D. On the computation of discrete logarithms in finite prime fields PhD thesis. Univ. des Saarlandes, Saarbrcken, 1997.

/ [277] Weber D. Computing discrete logarithms with quadratic number rings Advances in Cryptology EUROCRYPT’98. Springer // — Verlag, 1998. (Lect. Notes in Comput. Sci.;

V. 1403). P. 171 183.

— [278] Weber D., Denny T. The solution of McCurley’s discrete log challenge Advances in Cryptology CRYPTO’98. Springer // — Verlag, 1998. (Lect. Notes in Comput. Sci.;

V. 1462). P. 458 471.

— Литература [279] Weber K. An experiment in high-precision arithmetic on shared memory multiprocessors ACM SIGSAM Bull. 1990. V. 24 (2).

// P. 22 44.

— [280] Western A. E., Miller J. C. P. Tables of indices and primitive roots.

Cambridge University Press, 1968. (Royal Society Mathematical Tables;

V. 9).

[281] Wiedemann D. H. Solving sparce linear equations over finite fields IEEE Trans. Inform. Theory. 1986. V. 32 (1). P. 54 62.

// — [282] Williams H. C. Some algorithms for solving xq N (mod p) // Proc. 3rd South East Conf. on Combinatorics, Graph Theory and Computing. 1972. P. 451 462.

— [283] Williams H. C. Ap + 1 method of factoring Math. Comp. 1982.

// V. 39 (159). P. 225 234.

— [284] Williams H. C. Factoring on a computer Math. Intell. 1984.

// V. 6 (3). P. 29 36.

— [285] Williams H. C., Wunderlich M. C. On the parallel generation of the residues for the continued fraction factoring algorithm Math.

// Comp. 1987. V. 48 (177). P. 405 423.

— [286] Wu H. Efficient computations in finite fields with cryptographic significance PhD thesis. Univ. of Waterloo, Waterloo, Ontario, / Canada, 1998.

[287] Wu H. Montgomery multiplier and squarer in GF(2n) Technical / report, Univ. of Waterloo, The Centre for applied cryptographic research, May 2000.

[288] Wu H. On computation of polynomial modular reduction Technical / report, Univ. of Waterloo, The Centre for applied cryptographic research, June 2000.

[289] Wu H. On modular reduction Technical report, Univ. of Waterloo, / The Centre for applied cryptographic research, June 2000.

[290] Zayer J. Factorisieren mit dem Number Field Sieve PhD thesis, / Universitt der Saarlandes, 1995.

[291] Zierler N. A conversion algorithm for logarithms on GF(2n) // J. Pure and Appl. Algebra. 1974. V. 4. P. 353 356.

— [292] Zuras D. On squaring and multiplying large integers Proceedings // of 11th IEEE Symp. Comp. Arith. IEEE Press, 1993. P. 260 271.

— 21 О. Н. Василенко Предметный указатель (P + 1)-метод Уильямса 74 Голдвассер Килиана — — (P - 1)-метод Полларда 60 детерминированный проверки — -низкое число 147 простоты чисел -метод Полларда 62 Диксона — -метод Полларда для дискретно- Евклида — го логарифмирования Евклида обобщенный — B-гладкое число квадратичного решета — B-степенно-гладкое число Копперсмита — f-разлагающий многочлен Копперсмита Винограда — — j-инвариант Копперсмита Одлыжко — — — Шреппеля LLL-алгоритм с глубокой встав Лазара — кой Ланцоша — факторизации многочленов — Ланцоша блочный — целочисленный — Лемера — MLLL-алгоритм Поста Ленстры — Ленстры Коена — — А Ленстры Померанса — — Адамара неравенство Монтгомери — алгоритм index-calculus нахождения коротких векторов — Адлемана — решетки Адлемана Померанса — — — нахождения линейной зависи — Румели мости Адлемана Хуанга — — нахождения минимального — Аткина Морейна — — многочлена Бен-Ора — нахождения порядка элемента Берлекэмпа 173 — — Берлекэмпа Месси — — обобщенный бинарный бинарный 299 — — Полига Хеллмана Бриллхарта Моррисона 83 — — — — вероятностный проверки полиномиальный — — неприводимости 181 Полларда Штрассена — — Видемана 287 построения LLL-приведенного — — Гарнера 270 базиса — Предметный указатель решения f(x) = 0 в GF(p) 162 преобразование Фурье 1-го ти — — решета числового поля 93 па — согласования 130 2-го типа — ——— Тонелли Шэнкса 167 дискретный логарифм — — Тоома Кука — — длина входа Фергюсона Форкейда — — дробь n-членная непрерывная Ферма 57 бесконечная непрерывная — — Шенхаге Штрассена — — непрерывная — Шермана Лемана — — периодическая — Шнорра Ленстры — — подходящая — Штрассена — цепная — Шуфа — Е Эль Гамаля — единица поля Б З базис LLL-приведенный задача дискретного логарифмиро вполне приведенный — вания Грёбнера — приведенный по Минковскому — К каноническое разложение нату решетки — рального числа бесконечно удаленная точка Кармайкла числа бинарная квадратичная форма квадратичный вычет быстрое преобразование Фурье закон взаимности Гаусса — невычет — быстрый столбик « » китайская теорема об остатках Крылова последовательность В вектор нормализованный Л возведение в степень по Монтго Лежандра символ мери лемма Гаусса высота алгебраического числа логарифм дискретный Г М гауссово исключение метод SQUFOF структурированное —— возведения в степень — Грама матрица Кантора Цассенхауза — — Грама Шмидта процесс ортого — Карацубы — нализации пробных делений — Д Шэнкса — дискретное логарифмирование 129 многочлен деления 21* 324 Предметный указатель минимальный 232 для дискретного лога — ——— примитивный 217 рифмирования — Эратосфена множество дискретное 186 — С Н символ Лежандра ноль кривой Якоби — норма многочлена система вычетов полная О приведенная —— операция сложения на эллиптиче сложность алгоритма ской кривой полиномиальная — определитель решетки субэкспоненциальная — основная теорема арифметики экспоненциальная — сравнение П степень алгебраического числа первообразный корень подъем квадратичный стратегия EAS линейный — LP — полиномиальная сложность PS — полиномиальный алгоритм субэкспоненциальная сложность Полларда (P - 1)-метод сумма Якоби -метод — Т полная система вычетов теорема Дирихле о единицах последовательность Крылова китайская об остатках — Пратта сертификат Ламе — приведение по Монтгомери Ферма малая — приведенная система вычетов Хассе — просеивание Шенхаге Штрассена — — простое число Эйлера — простой идеал Эйлера Лагранжа — — первой степени —— тест Миллера Рабина — процесс ортогонализации Соловея Штрассена — — Р У разложение Холецкого умножение по Монтгомери разрешимость уравнения дискрет ного логарифмирования Ф расширенная гипотеза Римана факторная база результант 179 Фробениуса отображение решетка 186 функция Кармайкла 33, решето числового поля 93 Эйлера — Предметный указатель Х строго псевдопростое — Холецкого разложение 201 Ферма — числовой характер Ч частное Ферма 146 Ш число B-гладкое 9, 96 Широкауера аддитивный характер B-степенно-гладкое 9 — алгебраическое — Э евклидово простое — Эйлера критерий Люка — экспоненциальная сложность Мерсенна — эллиптическая кривая начальное простое — Эратосфена решето сопряженное алгебраическое — 232 Я Софи Жермен 56 Якоби символ — Олег Николаевич Василенко Теоретико-числовые алгоритмы в криптографии Редактор Т. Л. Коробкова Издательство Московского Центра непрерывного математического образования Лицензия ИД № 01335 от 24.03.2000 г.

Подписано в печать 07.10.2003 г. Формат 60 90. Бумага офсетная № 1.

/ Печать офсетная. Усл. печ. л. 20.5. Тираж 1000 экз. Заказ №.

МЦНМО 119002, Москва, Большой Власьевский пер., Отпечатано во ФГУП Производственно-издательский комбинат ВИНИТИ.

« » 140010, г. Люберцы Московской обл., Октябрьский пр-т, 403. Тел. 554 21 Книги издательства МЦНМО можно приобрести в магазине Математическая книга, « » Большой Власьевский пер., д. 11. Тел. 241 72 85. E-mail:biblio@mccme.ru

Pages:     | 1 |   ...   | 3 | 4 ||



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.