Decomposition of RSA modulus applying even order elliptic curves

• URL: http://arxiv.org/abs/2503.00950v1
• Date: Sun, 02 Mar 2025 16:09:07 GMT
• Title: Decomposition of RSA modulus applying even order elliptic curves
• Authors: Jacek Pomykała, Mariusz Jurkiewicz,
• Abstract summary: An efficient integer factorization algorithm would reduce the security of all variants of the RSA cryptographic scheme to zero.<n>We demonstrate how a natural extension of the generalized approach to smoothness, combined with the separation of $2$-adic point orders, leads us to propose a factoring algorithm.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: An efficient integer factorization algorithm would reduce the security of all variants of the RSA cryptographic scheme to zero. Despite the passage of years, no method for efficiently factoring large semiprime numbers in a classical computational model has been discovered. In this paper, we demonstrate how a natural extension of the generalized approach to smoothness, combined with the separation of $2$-adic point orders, leads us to propose a factoring algorithm that finds (conjecturally) the prime decomposition $N = pq$ in subexponential time $L(\sqrt 2+o(1), \min(p,q))$. This approach motivated by the papers \cite{Len}, \cite{MMV} and \cite{PoZo} is based on a more careful investigation of pairs $(E,Q)$, where $Q$ is a point on an elliptic curve $E$ over $\Z _N$. Specifically, in contrast to the familiar condition that the largest prime divisor $P^+(\ord Q_p)$ of the reduced order $\ord Q_p$ does not divide $\#E(\F_q)$ we focus on the relation between $P^+(\ord Q_r)$ and the smallest prime number $l_{\min}(E,Q)$ separating the orders $\ord Q_p$ and $\ord Q_q$. We focus on the ${\calE}_2$ family of even order elliptic curves over $\Z_N$ since then the condition $l_{\min}(E,Q)\le 2$ holds true for large fraction of points $(x,y)\in E(\Z_N)$. Moreover if we know the pair $(E,Q)$ such that $P^+(\ord Q_r)\le t<l_{\min}(E,Q)$ and $d=\max_{r\in \{p,q\}}(\ord Q_r)$ is large in comparison to $\min_{r\in \{p,q\}}|a_r(E)|\neq 0$ then we can decompose $N$ in deterministic time $t^{1+o(1)}$ by representing $N$ in base $d$.

Related papers

• On estimating the trace of quantum state powers [2.637436382971936]
  We investigate the computational complexity of estimating the trace of quantum state powers $texttr(rhoq)$ for an $n$-qubit mixed quantum state $rho$. Our speedup is achieved by introducing efficiently computable uniform approximations of positive power functions into quantum singular value transformation.
  arXiv  Detail & Related papers  (2024-10-17T13:57:13Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  We consider the randomized communication complexity of the distributed $ell_p$-regression problem in the coordinator model. For $p = 2$, i.e., least squares regression, we give the first optimal bound of $tildeTheta(sd2 + sd/epsilon)$ bits. For $p in (1,2)$,we obtain an $tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound.
  arXiv  Detail & Related papers  (2023-07-11T08:51:53Z)
• Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
  We show how to find all $k$ marked elements in a list of size $N$ using the optimal number $O(sqrtN k)$ of quantum queries.
  arXiv  Detail & Related papers  (2023-02-20T19:11:44Z)
• Exact Fractional Inference via Re-Parametrization & Interpolation between Tree-Re-Weighted- and Belief Propagation- Algorithms [0.4527270266697462]
  We show how to express $Z$ as a product, $forall lambda: Z=Z(lambda)tilde Z(lambda)$, where the multiplicative correction, $tilde Z(lambda)$, is an expectation over a node-independent probability distribution. We also discuss the applicability of this approach to the problem of image de-noising.
  arXiv  Detail & Related papers  (2023-01-25T00:50:28Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
  arXiv  Detail & Related papers  (2022-02-10T16:10:41Z)
• Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes [12.640283469603357]
  We study the computational complexity of computing the normalizing constant. We show that $sum_Sdet(bf A_S,S)p$ exactly for every (fixed) positive even integer $p$ is UP-hard and Mod$_3$P-hard.
  arXiv  Detail & Related papers  (2021-11-28T14:08:25Z)
• Simplest non-additive measures of quantum resources [77.34726150561087]
  We study measures that can be described by $cal E(rhootimes N) =E(e;N) ne Ne$.
  arXiv  Detail & Related papers  (2021-06-23T20:27:04Z)
• The planted matching problem: Sharp threshold and infinite-order phase transition [25.41713098167692]
  We study the problem of reconstructing a perfect matching $M*$ hidden in a randomly weighted $ntimes n$ bipartite graph. We show that if $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ for an arbitrarily small constant $epsilon>0$, the reconstruction error for any estimator is shown to be bounded away from $0$.
  arXiv  Detail & Related papers  (2021-03-17T00:59:33Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

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.