20 citations · 48 across the 12 of their papers we have counts for
13 papers
Multi-target hyperbolic sieves and elliptic trace obstructions
Pantelimon Stănică, Erik Mulder, Markus Hittmeir
Let be a product of two primes, and let be an odd prime not dividing . For , the set \[ H_a(N;\ell)=\{ax+Nx^{-1}:x\in\mathbb F_\ell^*\} \] co…
Deterministic methods for finding elements of large multiplicative order
David Harvey, Markus Hittmeir
We revisit the problem of rigorously and deterministically finding elements of large order in the multiplicative group of integers modulo a natural number . Solving this problem…
Fine-grained deterministic hardness of the shortest vector problem
Markus Hittmeir
Let - be the decision version of the shortest vector problem in the -norm with approximation factor , let be the lattice rank and $0<\varepsilo…
Smooth Subsum Search: A heuristic for practical integer factorization
Markus Hittmeir
The two currently fastest general-purpose integer factorization algorithms are the Quadratic Sieve and the Number Field Sieve. Both techniques are used to find so-called smooth val…
Integer factorization as subset-sum problem
Markus Hittmeir
This paper elaborates on a sieving technique that has first been applied in 2018 for improving bounds on deterministic integer factorization. We will generalize the sieve in order…
A deterministic algorithm for finding -power divisors
David Harvey, Markus Hittmeir
Building on work of Boneh, Durfee and Howgrave-Graham, we present a deterministic algorithm that provably finds all integers such that in time …
A log-log speedup for exponent one-fifth deterministic integer factorisation
David Harvey, Markus Hittmeir
Building on techniques recently introduced by the second author, and further developed by the first author, we show that a positive integer may be rigorously and deterministica…
A time-space tradeoff for Lehman's deterministic integer factorization method
Markus Hittmeir
Fermat's well-known factorization algorithm is based on finding a representation of natural numbers as the difference of squares. In 1895, Lawrence generalized this idea and ap…
A reduction of integer factorization to modular tetration
Markus Hittmeir
Let . For the -th iterate of the exponential function , also known as tetration, we write \[ ^k a:=a^{a^{.^{.^{.^{a}}}}}. \] In this paper, we…
A babystep-giantstep method for faster deterministic integer factorization
Markus Hittmeir
In 1977, Strassen presented a deterministic and rigorous algorithm for solving the problem of computing the prime factorization of natural numbers . His method is based on fast…
Computational aspects of rational residuosity
Markus Hittmeir
In this paper, we consider an extension of Jacobi's symbol, the so called rational -th power residue symbol. In Section 3, we prove a novel generalization of Zolotarev's lemma…
Deterministic factorization of sums and differences of powers
Markus Hittmeir
Let be fixed and coprime such that , and let be any number of the form , . We will generalize a result of Bostan, Gaudry an…
Digit Polynomials and their application to integer factorization
Markus Hittmeir
This paper presents the concept of digit polynomials, which leads to a deterministic and unconditional integer factorization algorithm with the runtime complexity $\mathcal{O}(N^{1…