Extending Regev's factoring algorithm to compute discrete logarithms

• URL: http://arxiv.org/abs/2311.05545v2
• Date: Tue, 30 Jan 2024 12:29:52 GMT
• Title: Extending Regev's factoring algorithm to compute discrete logarithms
• Authors: Martin Eker{\aa} and Joel G\"artner
• Abstract summary: Regev recently introduced a quantum factoring algorithm that may be perceived as a $d$-dimensional variation of Shor's factoring algorithm. In this work, we extend Regev's factoring algorithm to an algorithm for computing discrete logarithms in a natural way.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Regev recently introduced a quantum factoring algorithm that may be perceived as a $d$-dimensional variation of Shor's factoring algorithm. In this work, we extend Regev's factoring algorithm to an algorithm for computing discrete logarithms in a natural way. Furthermore, we discuss natural extensions of Regev's factoring algorithm to order finding, and to factoring completely via order finding. For all of these algorithms, we discuss various practical implementation considerations, including in particular the robustness of the post-processing.

Related papers

• Rank-One Modified Value Iteration [3.04988705714342]
  We provide a novel algorithm for solving planning and learning problems of Markov decision processes.<n>We show that the proposed algorithm consistently outperforms first-order algorithms and their accelerated versions for both planning and learning problems.
  arXiv  Detail & Related papers  (2025-05-03T14:06:50Z)
• Implementation and Analysis of Regev's Quantum Factorization Algorithm [0.2874893537471256]
  We present our implementation of Regev's algorithm for factoring composite numbers. Despite Regev's theoretical advantage, our implementation exhibited execution times longer than Shor's algorithm for small integer factorization.
  arXiv  Detail & Related papers  (2025-02-13T21:02:15Z)
• Bregman-divergence-based Arimoto-Blahut algorithm [53.64687146666141]
  We generalize the Arimoto-Blahut algorithm to a general function defined over Bregman-divergence system. We propose a convex-optimization-free algorithm that can be applied to classical and quantum rate-distortion theory.
  arXiv  Detail & Related papers  (2024-08-10T06:16:24Z)
• A New Algorithm for Computing Branch Number of Non-Singular Matrices over Finite Fields [1.3332839594069594]
  The number of non-zero elements in a state difference or linear mask directly correlates with the active S-Boxes. The differential or linear branch number indicates the minimum number of active S-Boxes in two consecutive rounds of an SPN cipher. This paper presents a new algorithm for computing the branch number of non-singular matrices over finite fields.
  arXiv  Detail & Related papers  (2024-05-11T13:06:03Z)
• An Efficient Quantum Factoring Algorithm [0.27195102129094995]
  We show that $n$bit integers can be factorized by independently running a quantum circuit with $tildeO(n3/2)$. The correctness of the algorithm relies on a number-theoretic assumption reminiscent of those used in subexponential classical factorization algorithms.
  arXiv  Detail & Related papers  (2023-08-12T13:57:38Z)
• A Constrained BA Algorithm for Rate-Distortion and Distortion-Rate Functions [13.570794979535934]
  modification of Blahut-Arimoto (BA) algorithm for rate-distortion functions. modified algorithm directly computes the RD function for a given target distortion.
  arXiv  Detail & Related papers  (2023-05-04T08:41:03Z)
• Multivariate Systemic Risk Measures and Computation by Deep Learning Algorithms [63.03966552670014]
  We discuss the key related theoretical aspects, with a particular focus on the fairness properties of primal optima and associated risk allocations. The algorithms we provide allow for learning primals, optima for the dual representation and corresponding fair risk allocations.
  arXiv  Detail & Related papers  (2023-02-02T22:16:49Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  We consider the problem of computing an equilibrium in a class of nonlinear generalized Nash equilibrium problems (NGNEPs) Our contribution is to provide two simple first-order algorithmic frameworks based on the quadratic penalty method and the augmented Lagrangian method. We provide nonasymptotic theoretical guarantees for these algorithms.
  arXiv  Detail & Related papers  (2022-04-07T00:11:05Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  We study a class of algorithms for solving bilevel optimization problems in both deterministic and deterministic settings. We exploit a warm-start strategy to amortize the estimation of the exact gradient. By using this framework, our analysis shows these algorithms to match the computational complexity of methods that have access to an unbiased estimate of the gradient.
  arXiv  Detail & Related papers  (2021-11-29T15:10:09Z)
• Benchmarks for quantum computers from Shor's algorithm [0.0]
  Properties of Shor's algorithm and the related period-finding algorithm could serve as benchmarks for the operation of a quantum computer. Distinctive universal behaviour is expected for the probability for success of the period-finding as the input quantum register is increased.
  arXiv  Detail & Related papers  (2021-11-27T09:46:16Z)
• A quantum version of Pollard's Rho of which Shor's Algorithm is a particular case [0.0]
  Pollard's Rho is a method for solving the integer factorization problem. We show that Pollard's Rho is a generalization of Shor's algorithm.
  arXiv  Detail & Related papers  (2020-11-10T19:11:37Z)
• A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performance [16.0251555430107]
  This is the first GP-based algorithm with an order-optimal regret guarantee. Compared with the prevailing GP-UCB family of algorithms, the proposed algorithm reduces computational complexity by a factor of $O(T2d-1)$.
  arXiv  Detail & Related papers  (2020-10-27T02:15:15Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)
• Automatic Differentiation in ROOT [62.997667081978825]
  In mathematics and computer algebra, automatic differentiation (AD) is a set of techniques to evaluate the derivative of a function specified by a computer program. This paper presents AD techniques available in ROOT, supported by Cling, to produce derivatives of arbitrary C/C++ functions.
  arXiv  Detail & Related papers  (2020-04-09T09:18:50Z)

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.