Advertisement
Published in:
2018 | OriginalPaper | Chapter
Factoring n and the Number of Points of Kummer Hypersurfaces mod n
Authors : Robert Dryło, Jacek Pomykała
Published in: Number-Theoretic Methods in Cryptology
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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\).