Markus Hittmeir
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Markus Hittmeir has a total of 6 co-authors. Here are the top co-authors by number of shared publications:
- Rudolf Mayer
SBA Research, Vienna, Austria
7 shared publications Andreas Ekelhart
4 shared publications- Andreas Ekelhart
SBA Research, Austria
2 shared publications - Alicja Karlowicz
SBA Research, Austria
1 shared publication - David Harvey
School of Mathematics and Statistics, University of New South Wales, Sydney NSW 2052, Australia
1 shared publication Jacek Pomykała
Institute of Mathematics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland
1 shared publication
Latest Publications
- 29 December 2023
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 35 (08) , 949-974
Smooth Subsum Search A Heuristic for Practical Integer Factorization
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 values of certain polynomials, i.e., values that factor completely over a set of small primes (the factor base). As the names of the methods suggest, a sieving procedure is used for the task of quickly identifying smooth values among the candidates in a certain range. While the Number Field Sieve is asymptotically faster, the Quadratic Sieve is still considered the most efficient factorization technique for numbers up to around 100 digits. In this paper, we challenge the Quadratic Sieve by presenting a novel approach based on representing smoothness candidates as sums that are always divisible by several of the primes in the factor base. The resulting values are generally smaller than those considered in the Quadratic Sieve, increasing the likelihood of them being smooth. Using the fastest implementations of the Self-initializing Quadratic Sieve in Python as benchmarks, a Python implementation of our approach runs consistently 5 to 7 times faster for numbers with 45–100 digits, and around 10 times faster for numbers with 30–40 digits. We discuss several avenues for further improvements and applications of the technique.
- 29 December 2023
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 35 (08) , 949-974
Smooth Subsum Search A Heuristic for Practical Integer Factorization
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 values of certain polynomials, i.e., values that factor completely over a set of small primes (the factor base). As the names of the methods suggest, a sieving procedure is used for the task of quickly identifying smooth values among the candidates in a certain range. While the Number Field Sieve is asymptotically faster, the Quadratic Sieve is still considered the most efficient factorization technique for numbers up to around 100 digits. In this paper, we challenge the Quadratic Sieve by presenting a novel approach based on representing smoothness candidates as sums that are always divisible by several of the primes in the factor base. The resulting values are generally smaller than those considered in the Quadratic Sieve, increasing the likelihood of them being smooth. Using the fastest implementations of the Self-initializing Quadratic Sieve in Python as benchmarks, a Python implementation of our approach runs consistently 5 to 7 times faster for numbers with 45–100 digits, and around 10 times faster for numbers with 30–40 digits. We discuss several avenues for further improvements and applications of the technique.
- Open Access
- 17 October 2023
- Published by Elsevier in Computers & Security
- Vol. 136
Distance-based linkage of personal microbiome records for identification and its privacy implications
- 17 October 2023
- Published by Elsevier in Computers & Security
- Vol. 136
Open AccessDistance-based linkage of personal microbiome records for identification and its privacy implications
- Open Access
- 29 August 2023
- Published by Association for Computing Machinery (ACM)
- p. 1-11
k-Anonymity on Metagenomic Features in Microbiome Databases
- 29 August 2023
- Published by Association for Computing Machinery (ACM)
- p. 1-11
Open Accessk-Anonymity on Metagenomic Features in Microbiome Databases
- Open Access
Smooth Subsum Search: A heuristic for practical integer factorization
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 values of certain polynomials, i.e., values that factor completely over a set of small primes (the factor base). As the names of the methods suggest, a sieving procedure is used for the task of quickly identifying smooth values among the candidates in a certain range. While the Number Field Sieve is asymptotically faster, the Quadratic Sieve is still considered the most efficient factorization technique for numbers up to around 100 digits. In this paper, we challenge the Quadratic Sieve by presenting a novel approach based on representing smoothness candidates as sums that are always divisible by several of the primes in the factor base. The resulting values are generally smaller than those considered in the Quadratic Sieve, increasing the likelihood of them being smooth. Using the fastest implementations of the Self-initializing Quadratic Sieve in Python as benchmarks, a Python implementation of our approach runs consistently 5 to 7 times faster for numbers with 45-100 digits, and around 10 times faster for numbers with 30-40 digits. We discuss several avenues for further improvements and applications of the technique.
Open AccessSmooth Subsum Search: A heuristic for practical integer factorization
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 values of certain polynomials, i.e., values that factor completely over a set of small primes (the factor base). As the names of the methods suggest, a sieving procedure is used for the task of quickly identifying smooth values among the candidates in a certain range. While the Number Field Sieve is asymptotically faster, the Quadratic Sieve is still considered the most efficient factorization technique for numbers up to around 100 digits. In this paper, we challenge the Quadratic Sieve by presenting a novel approach based on representing smoothness candidates as sums that are always divisible by several of the primes in the factor base. The resulting values are generally smaller than those considered in the Quadratic Sieve, increasing the likelihood of them being smooth. Using the fastest implementations of the Self-initializing Quadratic Sieve in Python as benchmarks, a Python implementation of our approach runs consistently 5 to 7 times faster for numbers with 45-100 digits, and around 10 times faster for numbers with 30-40 digits. We discuss several avenues for further improvements and applications of the technique.
- 23 March 2023
- Published by Elsevier in Journal of Number Theory
- Vol. 249, 93-118
Integer factorization as subset-sum problem
- 23 March 2023
- Published by Elsevier in Journal of Number Theory
- Vol. 249, 93-118
Integer factorization as subset-sum problem
- Open Access
- 22 October 2022
- Published by Springer Nature in Research in Number Theory
- Vol. 8 (4) , 1-17
A deterministic algorithm for finding r-power divisors
Building on work of Boneh, Durfee and Howgrave-Graham, we present a deterministic algorithm that provably finds all integers p such that $$p^r \mathrel {|}N$$ in time $$O(N^{1/4r+\epsilon })$$ for any $$\epsilon > 0$$ . For example, the algorithm can be used to test squarefreeness of N in time $$O(N^{1/8+\epsilon })$$ ; previously, the best rigorous bound for this problem was $$O(N^{1/6+\epsilon })$$ , achieved via the Pollard–Strassen method.- 22 October 2022
- Published by Springer Nature in Research in Number Theory
- Vol. 8 (4) , 1-17
Open AccessA deterministic algorithm for finding r-power divisors
Building on work of Boneh, Durfee and Howgrave-Graham, we present a deterministic algorithm that provably finds all integers p such that $$p^r \mathrel {|}N$$ in time $$O(N^{1/4r+\epsilon })$$ for any $$\epsilon > 0$$ . For example, the algorithm can be used to test squarefreeness of N in time $$O(N^{1/8+\epsilon })$$ ; previously, the best rigorous bound for this problem was $$O(N^{1/6+\epsilon })$$ , achieved via the Pollard–Strassen method. - 13 July 2022
- Published by Springer Nature
- p. 15-27
Utility and Privacy Assessment of Synthetic Microbiome Data
- 13 July 2022
- Published by Springer Nature
- p. 15-27
Utility and Privacy Assessment of Synthetic Microbiome Data
- Open Access
A time-space tradeoff for Lehman's deterministic integer factorization method
Fermat's well-known factorization algorithm is based on finding a representation of natural numbers $N$ as the difference of squares. In 1895, Lawrence generalized this idea and applied it to multiples $kN$ of the original number. A systematic approach to choose suitable values for $k$ was introduced by Lehman in 1974, which resulted in the first deterministic factorization algorithm considerably faster than trial division. In this paper, we construct a time-space tradeoff for Lawrence's generalization and apply it together with Lehman's result to obtain a deterministic integer factorization algorithm with runtime complexity $O(N^{2/9+o(1)})$. This is the first exponential improvement since the establishment of the $O(N^{1/4+o(1)})$ bound in 1977.Open AccessA time-space tradeoff for Lehman's deterministic integer factorization method
Fermat's well-known factorization algorithm is based on finding a representation of natural numbers $N$ as the difference of squares. In 1895, Lawrence generalized this idea and applied it to multiples $kN$ of the original number. A systematic approach to choose suitable values for $k$ was introduced by Lehman in 1974, which resulted in the first deterministic factorization algorithm considerably faster than trial division. In this paper, we construct a time-space tradeoff for Lawrence's generalization and apply it together with Lehman's result to obtain a deterministic integer factorization algorithm with runtime complexity $O(N^{2/9+o(1)})$. This is the first exponential improvement since the establishment of the $O(N^{1/4+o(1)})$ bound in 1977. - 18 June 2020
- Published by Springer Nature
- p. 195-207
Privacy-Preserving Anomaly Detection Using Synthetic Data
- 18 June 2020
- Published by Springer Nature
- p. 195-207
Privacy-Preserving Anomaly Detection Using Synthetic Data
- 1 June 2020
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 31 (04) , 461-481
A Reduction of Integer Factorization to Modular Tetration
- 1 June 2020
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 31 (04) , 461-481
A Reduction of Integer Factorization to Modular Tetration