An average case efficient algorithm for solving two variable linear diophantine equations

• URL: http://arxiv.org/abs/2409.14052v1
• Date: Sat, 21 Sep 2024 07:51:12 GMT
• Title: An average case efficient algorithm for solving two variable linear diophantine equations
• Authors: Mayank Deora, Pinakpani Pal,
• Abstract summary: Solving two variable linear diophantine equations has applications in many cryptographic protocols such as RSA and Elliptic curve cryptography. We revisit two algorithms to solve two variable linear diophantine equations.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Solving two variable linear diophantine equations has applications in many cryptographic protocols such as RSA and Elliptic curve cryptography. Extended euclid's algorithm is the most widely used algorithm to solve these equations. We revisit two algorithms to solve two variable linear diophantine equations. For one of them, we do fine-grained analysis of the number of recursive calls and find a periodic function, which represents the number of recursive calls. We find the period and use it to derive an accurate closed form expression for the average number of recursive calls incurred by that algorithm. In the process of this derivation we get an upper bound on the average number of recursive calls, which depends on the intermediate values observed during the execution of algorithm. We propose an iterative version of the algorithm. While implementation of our algorithm, we verify a well known result from number theory about the probability of two random integers being coprime. Due to that result, our algorithm encounters an additional constraint for approximately 40% times. On almost all of these constrained inputs i.e. on nearly 100 % of them the algorithm outperforms two existing algorithms.

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 Quantum Diophantine Equation Solution Finder [0.0]
  Grover's algorithm is a quantum search algorithm which can find marked indices in a list very efficiently. By treating the indices as the integer variables in the diophantine equation, Grover's algorithm can be used to find solutions in brute force way more efficiently than classical methods.
  arXiv  Detail & Related papers  (2024-08-21T13:31:32Z)
• 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)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$. We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
  arXiv  Detail & Related papers  (2024-02-09T19:01:48Z)
• 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)
• Efficient Strongly Polynomial Algorithms for Quantile Regression [12.772027028644041]
  We revisit the classical technique of Quantile Regression (QR) This paper proposes several strongly efficient classical algorithms for QR for various settings. For two dimensional QR, making a connection to the geometric concept of $k$-set, we propose an algorithm with a worst-case time complexity of $mathcalO(n4/3 polylog(n))$. We also propose a randomized divide-and-conquer algorithm -- RandomizedQR with an expected time complexity of $mathcalO(nlog2(n))$ for two dimensional
  arXiv  Detail & Related papers  (2023-07-14T03:07:42Z)
• An Efficient Summation Algorithm for the Accuracy, Convergence and Reproducibility of Parallel Numerical Methods [0.0]
  We have introduced a new parallel algorithm for summing a sequence of floating-point numbers. This algorithm which scales up easily with the number of processors, adds numbers of the same exponents first. In this article, our main contribution is an extensive analysis of its efficiency with respect to several properties.
  arXiv  Detail & Related papers  (2022-05-11T08:31:48Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse [121.54116938140754]
  We propose a new Hessian inverse free Fully Single Loop Algorithm for bilevel optimization problems. We show that our algorithm converges with the rate of $O(epsilon-2)$.
  arXiv  Detail & Related papers  (2021-12-09T02:27:52Z)
• RAMA: A Rapid Multicut Algorithm on GPU [23.281726932718232]
  We propose a highly parallel primal-dual algorithm for the multicut (a.k.a.magnitude correlation clustering) problem. Our algorithm produces primal solutions and dual lower bounds that estimate the distance to optimum. We can solve very large scale benchmark problems with up to $mathcalO(108)$ variables in a few seconds with small primal-dual gaps.
  arXiv  Detail & Related papers  (2021-09-04T10:33:59Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• An integer factorization algorithm which uses diffusion as a computational engine [0.0]
  We develop an algorithm which computes a divisor of an integer $N$, which is assumed to be neither prime nor the power of a prime. By comparison, Shor's algorithm is known to use at most $O(log N)2log (log N) log (log log N)$ quantum steps on a quantum computer.
  arXiv  Detail & Related papers  (2021-04-23T14:11:33Z)
• Well Separated Pair Decomposition and power weighted shortest path metric algorithm fusion [0.0]
  We consider an algorithm that computes all $s$-well separated pairs in certain point sets in $mathbbRn$, $n$ $>$ $1$. We also consider an algorithm that is a permutation of Dijkstra's algorithm, that computes $K$-nearest neighbors using a certain power weighted shortest path metric in $mathbbRn$, $n$ $>$ $1$.
  arXiv  Detail & Related papers  (2021-03-20T17:38:13Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• How Do You Want Your Greedy: Simultaneous or Repeated? [41.440943886672855]
  We present SimultaneousGreedys, a deterministic algorithm for constrained submodular Julia. We also present SubmodularGreedy, a package which implements these algorithms.
  arXiv  Detail & Related papers  (2020-09-29T13:34:09Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  We propose unified algorithms for the important cases of first-order expectations and second-order expectations in edge-factored, non-projective spanning-tree models. Our algorithms exploit a fundamental connection between gradients and expectations, which allows us to derive efficient algorithms.
  arXiv  Detail & Related papers  (2020-08-29T14:58:26Z)
• Second-order Conditional Gradient Sliding [79.66739383117232]
  We present the emphSecond-Order Conditional Gradient Sliding (SOCGS) algorithm. The SOCGS algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations. 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.