Оценки числа решений теоретико-числовых уравнений, используемых в криптографии тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Гречников, Евгений Александрович

• Гречников, Евгений Александрович
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Гречников, Евгений Александрович

Глава 1. Введение.

Глава 2. Неподвижные точки дискретного логарифма

2.1. Формулировки.

2.2. Доказательства

2.3. Численные данные.

Глава 3. Верхняя оценка суммы символов Лежандра.

3.1. Формулировки.

3.2. Доказательства.

Глава 4. Построение многочленов степени 5 с большой суммой символов Лежандра.

4.1. Формулировки.

4.2. Доказательства

Глава 5. Построение эллиптических кривых.

5.1. Введение.

5.2. Метод комплексного умножения.

5.3. Свойства изоморфизма Г2.

5.4. Кольцо целых поля родов.

5.5. Делитель многочлена Ноа*] (ж).

5.6. Оценка коэффициентов многочлена Нр[в, а*]

5.7. Построение рациональных приближений к базису кольца целых

5.8. Вычисление элемента поля родов по приближённому значению

5.9. Время работы.

Список литературы диссертационного исследования кандидат физико-математических наук Гречников, Евгений Александрович, 2012 год

1. Guy R. К. Unsolved Problems in Number Theory. Springer-Verlag, 1994.

2. Zhang W. P. On a problem of Brizolis // Pure Appl. Math. 1995. Vol. 11. P. 1-3.

3. Cobeli C., Zaharescu A. An exponential congruence with solutions in primitive roots // Rev. Roumaine Math. Pures Appl. 1999. Vol. 44. P. 15-22.

4. Campbell M. E. On fixed points for discrete logarithms. Master's thesis, University of California at Berkeley, 2003. URL: http://math.berkeley.edu/~campbell/marithesis.pdf.

5. Череннёв M. А. Некоторые эффективные оценки для числа решений задачи Бризолиса // Современные проблемы математики и механики, t.IV «Математика», выпуск 3. Изд-во Московского университета. 2009. С. 125-129.

6. Черепнёв М. А. Криптографические протоколы. Изд-во механико-математического факультета МГУ, 2006.

7. Holden J. Fixed points and two-cycles of the discrete logarithm // ANTS. 2002. P. 405-415.

8. Holden J., Moree P. Some heuristics and results for small cycles of the discrete logarithm // Mathematics of computation. 2006. Vol. 75. P. 419-449.

9. Bourgain J., Konyagin S. V., Shparlinski I. E. Product sets of rationals, multiplicative translates of subgroups in residue rings, and fixed points of the discrete logarithm // Int. Math. Res. Notices. 2008. no. rnn090.

10. Silverman J. H. The Arithmetic of Elliptic Curves. Springer, 1986.

11. Deuring M. Die Typen der Multiplikatorenringe elliptischer Funktio-nenkorper // Abh. Math. Sem. Hansischen Univ. 1941. Vol. 14. P. 197-272.

12. Waterhouse W. C. Abelian varieties over finite fields // Ann. Sci. Ecole Norm. Sup. 1969. Vol. 2, no. 4. P. 521-560.

13. Koblitz N. Elliptic curve cryptosystems // Mathematics of Computation. 1987. Vol. 48. P. 203-209.

14. Miller V. S. Uses of elliptic curves in cryptography // Advances in Cryp-tology—CRYPTO '85. Vol. 218 of Lecture Notes in Computer Science. Springer-Verlag, 1986. P. 417-426.

15. Atkin A. O. L., Morain F. Elliptic curves and primality proving // Mathematics of Computation. 1993. Vol. 61, no. 203. P. 29-68.

16. Lay G.-J., Zimmer H. G. Constructing elliptic curves with given group order over large finite fields // ANTS / Ed. by L. M. Adleman, M.-D. A. Huang. Vol. 877 of Lecture Notes in Computer Science. Springer, 1994. P. 250-263.

17. Enge A., Morain F. Comparing invariants for class fields of imaginary quadratic fields // Algorithmic Number Theory — ANTS-V (Berlin). Vol. 2369 of Lecture Notes in Computer Science. Springer-Verlag, 2002. P. 252-266.

18. Baier H. Efficient algorithms for generating elliptic curves over finite fields suitable for use in cryptography. Master's thesis, Department of Computer Science, Technical University of Darmstadt, 2002.

19. Enge A., Schertz R. Constructing elliptic curves over finite fields using double eta-quotients // Journal de Theorie des Nombres de Bordeaux. 2004. Vol. 16, no. 3. P. 555-568.

20. Konstantinou E., Kontogeorgis A., Stamatiou Y. C., Zaroliagis C. D. On the Efficient Generation of Prime-Order Elliptic Curves //J. Cryptology. 2010. Vol. 23, no. 3. P. 477-503.

21. Степанов С. А. О числе точек гиперэллиптической кривой над простым конечным полем // Известия АН СССР. Серия математическая. 1969. Т. 33, № 5. С. 1171-1181.

22. Коробов Н. М. Оценка сумм символов Лежандра // Доклады АН СССР. 1971. Т. 196, № 4. С. 764-767.

23. Митькин Д. А. Уточнение оценки для суммы символов Лежандра от многочленов нечётной степени // Чебышевский сборник. 2005. Т. 6, № 3. С. 123-126.

24. Черепнёв М. А. Криптографические протоколы. М.: МГУ, 2006.

25. Konyagin S. V., Shparlinski I. E. Character sums with exponential functions and their applications. Cambridge University Press, 1999.

26. Hardy G. H., Wright E. M. An introduction to the theory of numbers. Oxford University Press, 1979.

27. Ramanujan S. Highly composite numbers. Annotated and with a foreword by Jean-Louis Nicolas and Guy Robin // Ramanujan J. 1997. Vol. 1, no. 2. P. 119-153.

28. Weil A. Sur les courbes algébriques et les variétés qui s'en déduisent. Paris: Hermann et Cie., 1948.

29. Weil A. Variétés abéliennes et courbes algébriques. Paris: Hermann et Cie., 1948.

30. Serre J.-P. Sur le nombre des points rationnels d'une courbe algébrique sur un corps fini // C.R. Acad. Sei. Paris Sér. I Math. 1983. Vol. 296. P. 397-402.

31. Brewer В. W. On certain character sums // Trans. Amer. Math. Soc. 1961. Vol. 99. P. 241-245.

32. Lenstra H. W. Factoring integers with elliptic curves // Annals of Mathematics. 1987. Vol. 126. P. 649-673.

33. Cox D. A. Primes of the form x2 + ny2. New York: Wiley, 1989.

34. Weber H. Lehrbuch der Algebra. 3rd edition. New York: Chelsea Publishing Company, 1908. Vol. 3.

35. Ленг С. Эллиптические функции. Москва: Наука, Главная редакция физико-математической литературы, 1984.

36. Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. М.: Мир, 1987.

37. Cornacchia G. Su di un metodo per la risoluzione in numeri interi dell' equazione Y^h=vCh,xn~hyh = P // Giornale di Matematiche di Battaglini. 1908. no. 46. P. 33-90.

38. Schertz R. Weber's class invariants revisited // Journal de Theorie des Nombres de Bordeaux. 2002. Vol. 14, no. 1. P. 325-343.

39. Cohn H. Introduction to the construction of class fields. Cambridge University Press, 1985.

40. Ленг С. Алгебраические числа. М.: Мир, 1966.

41. Enge A. The complexity of class polynomial computation via floating point approximations // Mathematics of Computation. 2009. Vol. 78, no. 266. P. 1089-1107.

42. Brisebarre N., Philibert G. Effective lower and upper bounds for the Fourier coefficients of powers of the modular invariant j // Journal of the Ramanujan Mathematical Society. 2005. Vol. 20. P. 255-282.

43. Brentjes A. J. Multi-dimensional continued fraction algorithms. Amsterdam: Mathematisch Centrum, 1981.

44. Peck L. G. Simultaneous rational approximations to algebraic numbers // Bull. Amer. Math. Soc. 1961. Vol. 67. P. 197-201.

45. Хинчин А. Я. Цепные дроби. M.: Наука, 1978.

46. Венков Б. А. Элементарная теория чисел. ОНТИ НКТП СССР, 1937.

47. Enge A. The CM software, 0.1 edition. 2009. URL: http://www.multiprecision.org/index.php?prog=cm&page=home.

48. LiDIA-Group. LiDlA — A library for computational number theory. 2001. URL: http://www.cdc.informatik.tu-darmstadt.de/TI/LiDIA/.Работы автора по теме диссертации

49. Гречников Е. А. Двусторонние оценки числа неподвижных точек дискретного логарифма // Вестник Московского университета. Серия 1. Математика. Механика. 2012. № 3. С. 3-8.

50. Гречников Е. А. Метод комплексного умножения для построения эллиптических кривых и его оптимизации // Прикладная дискретная математика. 2011. Т. 13, № 3. С. 17-54.

51. Гречников Е. А. Оценка суммы символов Лежандра // Матем. заметки. 2010. Т. 88, № 6. С. 859-866.

52. Гречников Е. А. Суммы символов Лежандра от многочленов степени 5 // Современные проблемы математики и механики, t.IV «Математика», выпуск 3. Изд-во Московского университета. 2009. С. 136-145.