An Algebraic-Geometry Approach to Prime Factorization
- URL: http://arxiv.org/abs/2209.11650v1
- Date: Fri, 23 Sep 2022 15:31:07 GMT
- Title: An Algebraic-Geometry Approach to Prime Factorization
- Authors: Alberto Montina, Stefan Wolf
- Abstract summary: New algorithms for prime factorization can have a practical impact on present implementations of cryptographic algorithms.
We show that there are varieties whose points can be evaluated efficiently given a number of parameters not greater than n/2.
In one case, we show that there are varieties whose points can be evaluated efficiently given a number of parameters not greater than n/2.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: New algorithms for prime factorization that outperform the existing ones or
take advantage of particular properties of the prime factors can have a
practical impact on present implementations of cryptographic algorithms that
rely on the complexity of factorization. Currently used keys are chosen on the
basis of the present algorithmic knowledge and, thus, can potentially be
subject to future breaches. For this reason, it is worth to investigate new
approaches which have the potentiality of giving a computational advantage. The
problem has also relevance in quantum computation, as an efficient quantum
algorithm for prime factorization already exists. Thus, better classical
asymptotic complexity can provide a better understanding of the advantages
offered by quantum computers. In this paper, we reduce the factorization
problem to the search of points of parametrizable varieties, in particular
curves, over finite fields. The varieties are required to have an arbitrarily
large number of intersection points with some hypersurface over the base field.
For a subexponential or poly- nomial factoring complexity, the number of
parameters have to scale sublinearly in the space dimension n and the
complexity of computing a point given the parameters has to be subexponential
or polynomial, respectively. We outline a procedure for building these
varieties, which is illustrated with two constructions. In one case, we show
that there are varieties whose points can be evaluated efficiently given a
number of parameters not greater than n/2. In the other case, the bound is
dropped to n/3. Incidentally, the first construction resembles a kind of
retro-causal model. Retro-causality is considered one possible explanation of
quantum weirdness.
Related papers
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP)
We generalize the SDP-inspired quantum algorithm to sum-of-squares.
Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z) - Quantum and Classical Combinatorial Optimizations Applied to
Lattice-Based Factorization [0.046040036610482664]
We show that lattice-based factoring does not scale successfully to larger numbers.
We consider particular cases of the CVP, and opportunities for applying quantum techniques to other parts of the factorization pipeline.
arXiv Detail & Related papers (2023-08-15T14:31:25Z) - Integer Factorisation, Fermat & Machine Learning on a Classical Computer [0.0]
We use Lawrence's extension of Fermat's factorisation algorithm to reduce the integer factorisation problem to a binary classification problem.
To address the classification problem, based on the ease of generating large pseudo--random primes, a corpus of training data, as large as needed, is synthetically generated.
arXiv Detail & Related papers (2023-07-16T22:39:00Z) - Shallow Depth Factoring Based on Quantum Feasibility Labeling and
Variational Quantum Search [0.0]
Large integer factorization is a prominent research challenge, particularly in the context of quantum computing.
We propose a new quantum algorithm, Shallow Depth Factoring (SDF), to factor a biprime integer.
arXiv Detail & Related papers (2023-05-31T04:18:04Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation.
For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
arXiv Detail & Related papers (2022-10-12T17:54:02Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach.
We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers.
We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
arXiv Detail & Related papers (2022-09-28T17:53:25Z) - An efficient quantum algorithm for lattice problems achieving
subexponential approximation factor [2.3351527694849574]
We give a quantum algorithm for solving the Bounded Distance Decoding (BDD) problem with a subexponential approximation factor on a class of integer lattices.
The running time of the quantum algorithm is for one range of approximation factors and subexponential time for a second range of approximation factors.
This view makes for a clean quantum algorithm in terms of finite abelian groups, uses relatively little from lattice theory, and suggests exploring approximation algorithms for lattice problems in parameters other than dimension alone.
arXiv Detail & Related papers (2022-01-31T18:58:33Z) - Using Shor's algorithm on near term Quantum computers: a reduced version [0.0]
We introduce a reduced version of Shor's algorithm that proposes a step forward in increasing the range of numbers that can be factorized on noisy Quantum devices.
In particular, we have found noteworthy results in most cases, often being able to factor the given number with only one of the proposed algorithm.
arXiv Detail & Related papers (2021-12-23T15:36:59Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression.
We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
arXiv Detail & Related papers (2020-11-09T01:13:07Z) - Refined bounds for algorithm configuration: The knife-edge of dual class
approximability [94.83809668933021]
We investigate how large should a training set be to ensure that a parameter's average metrics performance over the training set is close to its expected, future performance.
We show that if this approximation holds under the L-infinity norm, we can provide strong sample complexity bounds.
We empirically evaluate our bounds in the context of integer programming, one of the most powerful tools in computer science.
arXiv Detail & Related papers (2020-06-21T15:32:21Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.