A Guess and Determine Attack on the Elliptic Curve Discrete Logarithm Problem

• URL: http://arxiv.org/abs/2607.09814v1
• Date: Fri, 10 Jul 2026 04:19:39 GMT
• Title: A Guess and Determine Attack on the Elliptic Curve Discrete Logarithm Problem
• Abstract summary: We develop an algorithm to find a zero minor in a rectangular matrix.<n>We discuss the complexity of our algorithm, success probability and provide implementation details.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper is a continuation of our earlier work, in which, we described a Las Vegas algorithm to solve the elliptic curve discrete logarithm problem. The Las Vegas algorithm reduces the elliptic curve discrete logarithm problem to finding a zero minor in a matrix. Using intersection poset of a hyperplane arrangement, we develop an algorithm to find a zero minor in a rectangular matrix. Our methods are elementary. We discuss the complexity of our algorithm, success probability and provide implementation details. We also provide simulation details. Finding a zero minor in a matrix is also of independent interest.

Related papers

• Double Index Calculus Algorithm: Faster Solving Discrete Logarithm Problem in Finite Prime Field [8.950235011733273]
  We propose the double index calculus algorithm to solve the discrete logarithm problem in a finite prime field. Our algorithm is faster than the index calculus algorithm. Our algorithm is more general than the index calculus algorithm.
  arXiv  Detail & Related papers  (2024-09-13T12:41:32Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Bregman-divergence-based Arimoto-Blahut algorithm [53.64687146666141]
  We generalize the Arimoto-Blahut algorithm to a general function defined over Bregman-divergence system.<n>This algorithm can be applied to classical and quantum rate-distortion theory.
  arXiv  Detail & Related papers  (2024-08-10T06:16:24Z)
• A fixed-point algorithm for matrix projections with applications in quantum information [7.988085110283119]
  We show that our algorithm converges exponentially fast to the optimal solution in the number of iterations. We discuss several applications of our algorithm in quantum resource theories and quantum Shannon theory.
  arXiv  Detail & Related papers  (2023-12-22T11:16:11Z)
• Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning [4.10375234787249]
  We present a framework for designing efficient algorithms for unsupervised learning problems. Our framework is based on a meta algorithm that learns arithmetic circuits in the presence of noise.
  arXiv  Detail & Related papers  (2023-11-13T12:26:25Z)
• A quantum central path algorithm for linear optimization [5.450016817940232]
  We propose a novel quantum algorithm for solving linear optimization problems by quantum-mechanical simulation of the central path. This approach yields an algorithm for solving linear optimization problems involving $m$ constraints and $n$ variables to $varepsilon$-optimality. In the standard gate model (i.e., without access to quantum RAM), our algorithm can obtain highly-precise solutions to LO problems using at most $$mathcalO left( sqrtm + n textsfnnz (A) fracR_1
  arXiv  Detail & Related papers  (2023-11-07T13:26:20Z)
• Minors solve the elliptic curve discrete logarithm problem [0.0]
  This paper explores ways to solve the elliptic curve discrete logarithm problem. It follows our earlier work, where we tried to solve this problem by finding a zero minor in a matrix over the same finite field on which the elliptic curve is defined.
  arXiv  Detail & Related papers  (2023-10-06T10:05:25Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Learning the Positions in CountSketch [49.57951567374372]
  We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem. In this work, we propose the first learning-based algorithms that also optimize the locations of the non-zero entries.
  arXiv  Detail & Related papers  (2023-06-11T07:28:35Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Second-order Conditional Gradient Sliding [70.88478428882871]
  We present the emphSecond-Order Conditional Gradient Sliding (SOCGS) algorithm.<n>The SOCGS algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations.<n>It is useful when the feasible region can only be accessed efficiently through a linear optimization oracle.
  arXiv  Detail & Related papers  (2020-02-20T17:52:18Z)

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.