Прикладная дискретная математика. Приложение
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



ПДМ. Приложение:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Прикладная дискретная математика. Приложение, 2018, выпуск 11, страницы 25–30
DOI: https://doi.org/10.17223/2226308X/11/8
(Mi pdma386)
 

Теоретические основы прикладной дискретной математики

NFS factorization: new hopes

P. Kirchner

French Institute for Research in Computer Science and Automation, Rocquencourt, France
Список литературы:
Аннотация: We describe new Number Field Sieve techniques. While none is proved (even under heuristics) to work for a concrete family of number fields, we hope such a family exist. If this is the case, we can factor a special integer $n$ in time $L_n(1/3,(16/9)^{1/3})$, which doubles the length of $n$ with respect to SNFS for the same time. This algorithm works by finding a strongly-ambiguous ideal in order to factor the relative discriminant of a prime degree Galois extension. In case this method can be adapted for factoring general numbers, it may reach a complexity $L_n(1/3,(32/9)^{1/3})$. A variant of the same technique for computing number fields of constant degree $d$ would allow multiplying by $d$ the length of the discriminant at the same complexity. We emphasize that for these running times to hold, we need to build highly specific number fields, and there is no evidence it can be done. Finally, we give another technique for finding the maximum order of number fields, and may run as fast as $L_{|\Delta|}(1/3,(16/9)^{1/3})$. This method is likely to work, and can therefore find some square factors in some numbers.
Ключевые слова: integer factorization, number field sieve.
Реферативные базы данных:
Тип публикации: Статья
УДК: 512.772.7
Язык публикации: английский
Образец цитирования: P. Kirchner, “NFS factorization: new hopes”, ПДМ. Приложение, 2018, no. 11, 25–30
Цитирование в формате AMSBIB
\RBibitem{Kir18}
\by P.~Kirchner
\paper NFS factorization: new hopes
\jour ПДМ. Приложение
\yr 2018
\issue 11
\pages 25--30
\mathnet{http://mi.mathnet.ru/pdma386}
\crossref{https://doi.org/10.17223/2226308X/11/8}
\elib{https://elibrary.ru/item.asp?id=35557591}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/pdma386
  • https://www.mathnet.ru/rus/pdma/y2018/i11/p25
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Прикладная дискретная математика. Приложение
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024