Artykuł w czasopiśmie
Brak miniatury
Licencja
Dostęp zamkniętyDeterministic Integer Factorization with Oracles for Euler’s Totient Function
| cris.lastimport.scopus | 2024-02-12T20:44:03Z |
| dc.abstract.en | In this paper, we construct deterministic factorization algorithms for natural numbers N under the assumption that the prime power decomposition of Euler’s totient function φ (N ) is known. Their runtime complexities depend on the number ω (N ) of distinct prime divisors of N , and we present efficient methods for relatively small values of ω (N ) as well as for its large values. One of our main goals is to establish an asymptotic expression with explicit remainder term O (x /A ) for the number of positive integers N ≤ x composed of s distinct prime factors that can be factored nontrivially in deterministic time t = t (x ), provided that the prime power decomposition of φ (N ) is known. We obtain it for A = A (x ) = x 1–ɛ , where ɛ = ɛ (s ) > 0 is sufficiently small and t = t (x ) is a polynomial in log x of degree d = d (ɛ ). An analogous bound is deduced under the assumption of the oracle providing the decomposition of orders of elements in ℤ N * . |
| dc.affiliation | Uniwersytet Warszawski |
| dc.contributor.author | Pomykała, Jacek |
| dc.contributor.author | Hittmeir, Markus |
| dc.date.accessioned | 2024-01-24T21:43:02Z |
| dc.date.available | 2024-01-24T21:43:02Z |
| dc.date.issued | 2020 |
| dc.description.finance | Publikacja bezkosztowa |
| dc.description.number | 1 |
| dc.description.volume | 172 |
| dc.identifier.doi | 10.3233/FI-2020-1891 |
| dc.identifier.issn | 0169-2968 |
| dc.identifier.uri | https://repozytorium.uw.edu.pl//handle/item/104720 |
| dc.identifier.weblink | https://content.iospress.com/download?id=10.3233/FI-2020-1891 |
| dc.language | eng |
| dc.pbn.affiliation | mathemathics |
| dc.relation.ispartof | Fundamenta Informaticae |
| dc.relation.pages | 39-51 |
| dc.rights | ClosedAccess |
| dc.sciencecloud | nosend |
| dc.subject.en | Factorization |
| dc.subject.en | Totient Function |
| dc.subject.en | Deterministic Reduction |
| dc.title | Deterministic Integer Factorization with Oracles for Euler’s Totient Function |
| dc.type | JournalArticle |
| dspace.entity.type | Publication |