# 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.

321 questions
Filter by
Sorted by
Tagged with
29 views

1 vote
92 views

### Non probabilistic algorithm : Given secret key $d$ we can factorize $n$ assuming $e$ is small

I read in an introduction to a paper that if $e$ is small enough and we were given secret key $d$ in RSA, then there is an efficient deterministic algorithm to factorize $n$. I've searched about that ...
• 173
5k views

### Quantum Computing Used to Break RSA by "fixing" Schnorr's Recent Factorization Claim?

There is a claim by Chinese researchers making the rounds (Schneier's blog here) that RSA can be broken by Quantum Computers. The paper is on arXiv. Wading through the discussion in Schneier's blog, ...
• 21.2k
312 views

### RSA: exploiting consecutive primes

It's given 2 plaintexts $m_1$ and $m_2$, and 5 different values of $n\quad\{n_1, n_2, n_3, n_4, n_5\}$ which are generated as follows: $n_1$ is a a product of two relatively small 128-bit $p$ and $q$ ...
1 vote
160 views

• 445
1 vote
43 views

194 views

### How much work to find such $n$?

Let $W$ be a random $200$ bit number. How much work would it take to find a semiprime $n=p_1\cdot p_2$ such that $p_1,p_2 > 2^{50}$ and $|W-n|<2^{12}$? More generally, let $W_b$ be a random ...
• 23
1 vote
341 views

### Using Shor's algorithm to access RSA messages without factoring

Most of the time people forgot that the real aim of the adversary against encryption is accessing the message. For example, in the RSA case, we talk about the factoring of the modulus to reach the ...
• 47.6k
560 views

### Rabin Cryptosystem: Chosen-Ciphertext Attack

I read in literature that Rabin Cryptosystem can be broken using chosen-ciphertext attack. It is described that after chosen ciphertext is decrypted attacker can factorize public key $n$ by using ...
1 vote
361 views

### What are those RSA Challenges, DES Challenges and RSA Factoring Challenges

Can someone explain the differences between the DES challenge, the RSA challenges, and the RSA factoring challenge? What were the aims? I think the factoring challenge was to encourage research, the ...
• 11
706 views

### Factoring a RSA modulus given parts of a Factor

e,N,c and around 2/3 of p are given and I need to get the whole p to decrypt c. ...
1 vote
89 views

### The significance of the field of the factor in Lenstra’s ECM

I am going through Lenstra's Elliptic Curve Factorisation from Silverman's Mathematical Cryptography book. I have understood the algorithm itself, but unable to understand a specific point the book ...
• 2,169
1 vote
223 views

### RSA factorization knowing the form of p and q

I'm wondering if knowing the form of both factors (p and q) of a RSA modulus N is a significant help for factoring or not. For instance: p of the form 4k+3, so (p-3)%4 = 0 and q of the form 4k+7, so (...
• 11
80 views

### What would be the safety requirements for the primes in $n=p \cdot q$ regarding the factorization?

Let it be $p, q \in \mathbb{P}$ with $p,q \in [2^{b-1}, 2^b]$ for some $b \in \mathbb{N}$ and $p \cdot q = n \in \mathbb{N}$. What would be the distance between $p$ and $q$ (as a function of b) so ...
• 53
248 views

### Factoring RSA if prime p is used as the private exponent

I've got two 1024 bits primes $p,q$, and $n = p \cdot q$. Now I know the result of $c^{p} \bmod n = x$, also the value of $c$ is given, I wonder if it is possible to factorize $n$.
• 59