Rambler's Top100 Service
Поиск   
 
Обратите внимание!   BOAI: наука должна быть открытой Обратите внимание!
 
  Наука >> Математика >> Алгебра, математическая логика и теория чисел | Книги
 Написать комментарий  Добавить новое сообщение
Next: Литература к главе 4 Up: 4. Алгоритмические проблемы теории Previous: 4.8. Дискретное логарифмирование Contents: Содержание

4.9. Заключение

Мы затронули в этой главе лишь небольшую часть вопросов, связанных с теоретико-числовыми алгоритмами и оценками их сложности. Мы не описывали перспективные исследования, связанные с распространением алгоритмов решета на поля алгебраических чисел (решето числового поля), и использование их для разложения целых чисел на множители или решения задачи дискретного логарифмирования, см. [20]. Именно с помощью этих алгоритмов достигнуты теоретические оценки сложности разложения на множители

\begin{displaymath}\exp(c(\ln N)^{1/3}(\ln\ln N)^{2/3}).\end{displaymath}

Не были затронуты эллиптические кривые, т.е. определенные с точностью до обратимого множителя пропорциональности множества точек

\begin{displaymath}
E_{a,b}=\{(x,y,z)\in(\ZZ/m\ZZ)^3\vert y^2z=x^3+axz^2+bz^3\},
\end{displaymath}

обладающие групповой структурой. С их помощью удалось построить весьма эффективные алгоритмы разложения чисел на множители и проверки целых чисел на простоту. В отличие от мультипликативной группы $ (\ZZ/m\ZZ)^*$ порядок группы $ E_{a,b} $ при одном и том же $ m$ меняется в зависимости от целых параметров $ a$, $ b$. Это оказывается весьма существенным, например, при разложении чисел $ m$ на множители. Мы отсылаем читателей за подробностями использования эллиптических кривых к статье [21].




Написать комментарий
 Copyright © 2000-2015, РОО "Мир Науки и Культуры". ISSN 1684-9876 Rambler's Top100 Яндекс цитирования