Prikladnaya Diskretnaya Matematika. Supplement
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Prikl. Diskr. Mat. Suppl.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Prikl. Diskr. Mat. Suppl., 2018, Issue 11, Pages 25–30 (Mi pdma386)  

Theoretical Foundations of Applied Discrete Mathematics

NFS factorization: new hopes

P. Kirchner

French Institute for Research in Computer Science and Automation, Rocquencourt, France

Abstract: 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.

Keywords: integer factorization, number field sieve.

DOI: https://doi.org/10.17223/2226308X/11/8

Full text: PDF file (667 kB)
References: PDF file   HTML file

UDC: 512.772.7
Language:

Citation: P. Kirchner, “NFS factorization: new hopes”, Prikl. Diskr. Mat. Suppl., 2018, no. 11, 25–30

Citation in format AMSBIB
\Bibitem{Kir18}
\by P.~Kirchner
\paper NFS factorization: new hopes
\jour Prikl. Diskr. Mat. Suppl.
\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}


Linking options:
  • http://mi.mathnet.ru/eng/pdma386
  • http://mi.mathnet.ru/eng/pdma/y2018/i11/p25

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Prikladnaya Diskretnaya Matematika. Supplement
    Number of views:
    This page:113
    Full text:27
    References:14

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2022