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

324 questions
Filter by
Sorted by
Tagged with
206 views

### How could a 1024‒bits RSA modulus be most economically factored within months today?

Of course this is a question with an answer that is due to evolve. A 2002 paper about TWIRL stated that the cost would be around 10M\$and an other 10M\$ to manufacture the device. A later 2007 paper ...
• 122
98 views

### RSA given 30% MSB of p and 30%MSB of q

is factoring RSA given 30% MSB of p and 30%MSB of q possible in polynomial time? Notice that it is known that given 50% MSB of p or q it is doable in polynomial time using Coppersmith's theorem
• 453
150 views

### Can a very efficient RSA factoring algorithm be worth money?

If someone had a very efficient RSA factoring algorithm, would a company or government entity be willing to purchase it? What factoring time would be considered fast, months, days, hours, minutes? ...
32 views

1 vote
94 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, ...
• 22.1k
368 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
173 views

• 447
1 vote
44 views

199 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
373 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 ...
• 48.3k
627 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
402 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
801 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
93 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,181
1 vote