Scholarlink

In this paper we consider the integer factorization problem that constitutes a base of security for cryptographic schemes from the family of solutions based on the Rivest-Shamir-Adleman concept. Apart from quantum Shor’s algorithm, an efficient classical algorithm which enables to solve this problem in polynomial time has not been made so far. The best known classical algorithms carry out factorization in merely subexponential time. We show how a natural extension from the generalized approach to smoothness leads us to the concepts of decomposition witnesses, and on this basis, we present a new approach to elliptic-curve factorization. Instead of assuming that we have the witness of large order, what we did in [8], we assume there is given the set X of witnesses generating large subgroup in \(G\subset E(\mathbb {Z}_N)\) that have some additional properties. We justify that either X contains the separating witness or the subgroup \(&lt;X&gt;\) generated by the set X in \(E(\mathbb {Z}_N)\) is noncyclic. The main result of this paper shows how to factor an integer, which is a product of two primes, in time \(L\left( \frac{1-\theta _\sigma (1-\beta )}{\sigma \alpha _0}+\sigma \alpha _0 + o(1), \,\, r\right) .\) This is an improvement as compared to the previous results provided that \(\theta _\sigma \ge {(2-2\sigma +\sigma ^2)}/{2(1-\beta )}.\) </X>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On \(\beta \) –Separating Sets and Deterministic Factoring

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Jacek Pomykała,
  • Mariusz Jurkiewicz,
  • Olgierd Onierczyk,
  • Kamila Prabucka

摘要

In this paper we consider the integer factorization problem that constitutes a base of security for cryptographic schemes from the family of solutions based on the Rivest-Shamir-Adleman concept. Apart from quantum Shor’s algorithm, an efficient classical algorithm which enables to solve this problem in polynomial time has not been made so far. The best known classical algorithms carry out factorization in merely subexponential time. We show how a natural extension from the generalized approach to smoothness leads us to the concepts of decomposition witnesses, and on this basis, we present a new approach to elliptic-curve factorization. Instead of assuming that we have the witness of large order, what we did in [8], we assume there is given the set X of witnesses generating large subgroup in \(G\subset E(\mathbb {Z}_N)\) that have some additional properties. We justify that either X contains the separating witness or the subgroup \(<X>\) generated by the set X in \(E(\mathbb {Z}_N)\) is noncyclic. The main result of this paper shows how to factor an integer, which is a product of two primes, in time \(L\left( \frac{1-\theta _\sigma (1-\beta )}{\sigma \alpha _0}+\sigma \alpha _0 + o(1), \,\, r\right) .\) This is an improvement as compared to the previous results provided that \(\theta _\sigma \ge {(2-2\sigma +\sigma ^2)}/{2(1-\beta )}.\)