Factoring n and the Number of Points of Kummer Hypersurfaces mod n

Abstract

In this paper we describe the reduction of factorization of a square-free integer n to the problem of determining the number of points in $\mathbb {Z}_n^{d+1}$ on twists of Kummer hypersurfaces $y^k = f(x_1,\ldots , x_d)\,{\text {mod}}\,n$, where $f(x_1,\ldots , x_d)\in \mathbb {Z}_n[x_1,\ldots , x_d]$ and $k>1$. This reduction is expected to be polynomial time (in ${\text {log}}\,n$) for small k and fixed number of prime divisors of n provided that some necessary for this reduction conditions are satisfied. This extends the known reduction of factorization to determining the number of points on elliptic curves $y^2 = x^3 +ax +b$ over $\mathbb {Z}_n$. In particular our reduction implies that factorization of n can be reduced to determining the number of points on quadrics in $\mathbb {Z}_n^{d}$, $d>1$, which extends the known reduction of factorization to determining the order of $\mathbb {Z}_n^*$. We also describe the reduction of factorization to determine the number of points in $\mathbb P^2(\mathbb {Z}_n)$ on superelliptic curves $y^k = f(x_1)\,{\text {mod}}\,n$. To study the complexity of these reductions we introduce some notions and prove useful facts for a more precise analysis. In greater detail we consider the case of the reduction when $n=pq$ is a product of two primes and $k=2$.