Source author record

Markus Hittmeir

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.NT

Catalog footprint

Research overview

3works

1topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Deterministic methods for finding elements of large multiplicative order

We revisit the problem of rigorously and deterministically finding elements of large order in the multiplicative group of integers modulo a natural number $N$ . Solving this problem is an essential step in several recent deterministic algorithms for factoring $N$ , including the currently fastest ones. In 2018, the second author gave an algorithm that for a given target order $D \geq N^{2/5}$ , finds either an element of order exceeding $D$ , or a nontrivial divisor of $N$ , or proves that $N$ is prime. The running time was $O\left(\frac{D^{1/2}}{(\log \log D)^{1/2}} \log^2 N \right)$ bit operations, asymptotically the same as the cost of computing the order of a single element using Sutherland's optimisation of the classical babystep-giantstep method. Subsequent work by several authors weakened the hypothesis $D \geq N^{2/5}$ to $D \geq N^{1/6}$ . In this paper, we show that the hypothesis may be dropped altogether. Moreover, if $N$ is prime, we can guarantee returning an element of order exceeding $D$ , rather than a proof that $N$ is prime.

preprint2018arXiv

A reduction of integer factorization to modular tetration

Let $a,k\in\mathbb{N}$ . For the $k-1$ -th iterate of the exponential function $x\mapsto a^x$ , also known as tetration, we write $^k a:=a^{a^{.^{.^{.^{a}}}}}.$ In this paper, we show how an efficient algorithm for tetration modulo natural numbers $N$ may be used to compute the prime factorization of $N$ . In particular, we prove that the problem of computing the squarefree part of integers is deterministically polynomial-time reducible to modular tetration.

preprint2015arXiv

Digit Polynomials and their application to integer factorization

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/4+ε})$ . Strassen's well known factoring approach is a special case of our method. We will also consider a possibility to improve upon the complexity bound.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.