Artykuł w czasopiśmie
Brak miniatury
Licencja
CC-BYCC-BY - Uznanie autorstwa
 

Integer factoring and compositeness witnesses

Uproszczony widok
cris.lastimport.scopus2024-02-12T20:17:21Z
dc.abstract.enAbstractWe describe a reduction of the problem of factorization of integersn≤xin polynomial-time (logx)M+O(1)to computing Euler’s totient function, with exceptions of at mostxO(1/M)composite integers that cannot be factored at all, and at mostxexp$\begin{array}{} \displaystyle \left(-\frac{c_M(\log\log x)^3}{(\log\log\log x)^2}\right) \end{array}$integers that cannot be factored completely. The problem of factoring square-free integersnis similarly reduced to that of computing a multipleDofϕ(n), whereD≪ exp((logx)O(1)), with the exception of at mostxO(1/M)integers that cannot be factored at all, in particularO(x1/M) integers of the formn=pqthat cannot be factored.
dc.affiliationUniwersytet Warszawski
dc.contributor.authorRadziejewski, Maciej
dc.contributor.authorPomykała, Jacek
dc.date.accessioned2024-01-25T04:20:07Z
dc.date.available2024-01-25T04:20:07Z
dc.date.copyright2020-08-20
dc.date.issued2020
dc.description.accesstimeAT_PUBLICATION
dc.description.financePublikacja bezkosztowa
dc.description.number1
dc.description.versionORIGINAL_AUTHOR
dc.description.volume14
dc.identifier.doi10.1515/JMC-2019-0023
dc.identifier.issn1862-2976
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/109400
dc.identifier.weblinkhttps://www.degruyter.com/document/doi/10.1515/jmc-2019-0023/html
dc.languageeng
dc.pbn.affiliationmathemathics
dc.relation.ispartofJournal of Mathematical Cryptology
dc.relation.pages346-358
dc.rightsCC-BY
dc.sciencecloudnosend
dc.titleInteger factoring and compositeness witnesses
dc.typeJournalArticle
dspace.entity.typePublication