Skip to main content
The 2024 Developer Survey results are live! See the results

# Questions tagged [factoring]

The decomposition of an integer number to the product of other integers. Algorithms such as RSA are based on the premise that no practical way has been found was to factorize large integers when they have been produced by multiplying two large primes.

53 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
17 votes
0 answers
427 views

### Fewest qubits required for the discrete logarithm problem and integer factorization

According to a paper from 2002, the most efficient circuit to factor an $n$-bit integer requires $2n+3$ qubits and $O(n^{3}\lg(n))$ elementary quantum gates, assuming ideal qubits. Later on, according ...
• 15.4k
13 votes
0 answers
870 views

### RSA factorization with special primes

Suppose that primes for RSA modulus are generated using formula: $P_i(x,y) = \operatorname{next\_prime}(x^{z_i}+y^{z_i}) = x^{z_i}+y^{z_i}+d_i$ where $x,y$ are unknown random numbers with size 128 ...
10 votes
0 answers
168 views

• 1
0 votes
0 answers
348 views

### RSA : Is there a way to compute phi(n) or N itself if we only know e, d and a ciphertext?

I am trying to solve a problem where private key exponent d, ciphertext c, and public key exponent e (65537) are known. How can I calculate φ(n) or n itself? An extended version of the problem would ...
• 33
0 votes
0 answers
216 views

### CTF question with hint "Quadratic method to solve ifp problem"

I totally have no idea about this Rabin decrypt problem. source code: https://github.com/shanzhuer/myctf/blob/main/crypto/rabin.py Inside there were $2^{21}$ times of encryption and decryption of ...
0 votes
0 answers
65 views

### What kind of special numbers are not suitable as RSA keys?

I have read that some integers are not appropriate to be chosen as the modulus in an RSA cryptosystem. Some of these numbers are those that, given a modulus $n=pq$, then $p-1$ or $q-1$ do not have ...
0 votes
0 answers
79 views

### How do I retrieve a number which has been multiplied with a random number?

I have a 1024-bit number $n$ obtained by multiplying two 512-bit randomly generated prime numbers $p$ and $q$. Then there's $\phi = (p-1)(q-1)$, which is another 1024-bit number. I do not have $\phi$ ...
0 votes
0 answers
552 views

### Brute force integer factorization - back of the envelope calculation

RSA-240, an integer with 240 decimal digits from the original RSA Factoring Challenge, has recently been factorized. According to the researchers, the factorization took a total of 900 core-years on ...
• 101
0 votes
0 answers
89 views

### Given a deterministic oracle that calculates square roots modulo n, factor n

When $n = pq$ where $p$ and $q$ are primes, we can generate random numbers until we get $a$ and $b$ such that $a^2 \equiv b^2 \pmod n$. This implies $n$ has some common factor with $a^2-b^2$, and then ...