November 30, 2025Open Access

Computing (N) for an RSA module with a single quantum query

Key Points

The algorithm computes the greatest common divisor efficiently, facilitating new insights in factoring RSA modules.
It operates with a probability of at least 1 - 1/N^(1/2 - epsilon), where epsilon is a small positive constant.
Using quantum queries allows for potentially enhanced performance in RSA module factorization.
The findings may enable advancements in cryptographic security assessments based on RSA technology.

Abstract

Abstract In this paper, we give a polynomial time algorithm to compute (N) φ (N) for an RSA module N using as input the order modulo N of a randomly chosen integer. This provides a new insight in the very important problem of factoring an RSA module with extra information. In fact, the algorithm is extremely simple and consists only on a computation of a greatest common divisor, two multiplications and a division. The algorithm works with a probability of at least 1-1N^{1/2- } 1 - 1 N 1 / 2 - ϵ, where ϵ is any small positive constant.

Computing (N) for an RSA module with a single quantum query

Key Points

Abstract

Cite This Study

Also Consider

Also Consider