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

331 questions
Filter by
Sorted by
Tagged with
466 views

### How did they factor RSA-704?

I don't understand the 'Wiedemann algorithm' works. Can someone explain the factoring of RSA-704 in an easy way?
• 435
1 vote
94 views

### Why is it impractical to generate a semiprime dictionary? [duplicate]

This might be a very simple question. However, I am just learning the concept, so just excuse me. I am wondering why there is not any attempt to generate all semiprime numbers? (as an dict. attack to ...
35k views

### Security strength of RSA in relation with the modulus size

NIST SP 800-57 §5.6.1 p.62–64 specifies a correspondence between RSA modulus size $n$ and expected security strength $s$ in bits: ...
4k views

### RSA leak bits to factor N

Suppose you randomly generate large primes p and q as in RSA, and then tell me N=pq but not p or q. Then, you would like to actually let me factor N, except you should tell me as few bits of ...
• 293
1 vote
488 views

In the Paillier cryptosystem [1] the encryption of $m \in \mathbb{Z}_N$ with randomness $r \in \mathbb{Z}_n^*$ is $c = g^m r^n \bmod{n^2}$. The additive-homomorphic property of the system shows that $... 5 votes 1 answer 232 views ### In RSA, how to make sure that$p-1$and$q-1$are still hard to factorize? See this question. The comment by Brett Hale stated: On the other hand, ensuring$(p - 1)$has a large prime factor requires very little extra effort. What's actually the 'little extra effort'? • 629 5 votes 2 answers 640 views ### Why would this method of discrete logarithm finding not work? Say we do know$b$but not$k$, and are given$g$such that$g\equiv b^k\pmod p$. And say there exist factors$E = e + m'p$($e \equiv b^i \bmod p$) and$F = f + m''p$($f \equiv b^j \bmod p$) of$g$. ... 3 votes 1 answer 321 views ### Discrete log analog of ECM factoring algorithm? Anecdotally, most factoring algorithms have a corresponding variant algorithm that can be used to attack the discrete log problem using similar ideas. Is there an analog of the elliptic curve (ECM) ... • 36.5k 2 votes 1 answer 186 views ### What's the strategy for future directions in cryptography? Bigger numbers/faster searching, or new methods, say, of factoring? I'm taking a course in cryptography, and I would value any comments. This is not too technical a question, but more about directions or strategy in cryptography. My question is, is public key ... 24 votes 4 answers 5k views ### What is the progress on the MIT LCS35 Time Capsule Crypto-Puzzle? Ron Rivest posed a puzzle in 1999. MIT LCS35 Time Capsule Crypto-Puzzle. The problem is to compute$2^{2^t} \pmod n$for specified values of$t$and$n$. Here$n$is the product of two large ... • 343 2 votes 1 answer 1k views ### Choosing good parameter for Lenstra's elliptic curve factorization In Wikipedia, there is an article explaining Lenstra's factorization algorithm. As far as I got it, we choose some$e \in \mathbb{N}$and a point$P$on the curve and then calculate$eP$. While ... • 133 2 votes 0 answers 139 views ### Generating Polynomials for the MPQS I'm going to try and eventually factor RSA-100, but my current QS needs a lot of improvement, so I'm going to try and switch over to the MPQS. I'm a bit confused as to how the MPQS works, which is ... • 115 5 votes 2 answers 3k views ### Attacks on the RSA Cryptosystem I was reading some articles about attacks on RSA system and I wonder about some generalization of the following theorem. Theorem (Coppersmith). Let$N=pq$be an$n$-bit RSA modulus, where$p&...
1k views

First off, if you're doing William's p+1 test, then also doing Pollard's p-1 is redundant, since the p+1 test covers both cases, right? Second, why is the recurrence $V_{n+1} = aV_n - V_{n-1}$ used? ...
• 331
290 views

### Quadratic Sieve Bottleneck, Multiple Polynomials an option?

After my failed attempt at trying to implement the ECM, I started working on the quadratic sieve. It works, but the bottleneck is finding smooth values over the factor base. The way I implemented it ...
• 115
2k views

### Carmichael number factoring

Unsure whether this is the right forum for this question, worth a try. The task im faced with is to implement a poly-time algorithm that finds a nontrivial factor of a carmichael number. Many ...
• 101
9k views

• 36.5k
2k views

### Why are elliptic curve variants of RSA "chiefly of academic interest"?

Yesterday I was thinking about elliptic curve variants of popular protocols/algorithms (ECDH, ECES[1], etc) and the thought occured that I had never seen an elliptic curve variant of RSA. My ...
• 38.7k
17k views

### OTP from Sony BIOS password recover [closed]

From Dogbert's blog: Sony has a line of laptops ("Vaio") which compete mainly in the high value market segments. They implemented a master password bypass which is rather sane in comparison to the ...
268 views

### RSA security assumptions - does breaking the DLP also break RSA? [duplicate]

Possible Duplicate: Would the ability to efficiently find Discrete Logs have any impact on the security of RSA? I'm wondering if breaking the DLP, that is the basis for ElGamal and DSA, would ...
• 2,450
89k views

### How big an RSA key is considered secure today?

I think 1024 bit RSA keys were considered secure ~5 years ago, but I assume that's not true anymore. Can 2048 or 4096 keys still be relied upon, or have we gained too much computing power in the ...
• 1,587
492 views

### Is the new preprint "An Algorithm For Factoring Integers" by Yingpu Deng and Yanbin Pan worth reading? [closed]

I just discovered on the eprint server of the IACR the paper mentioned in the title. Scanning quickly over the paper I didn't find anything spectacular, so I doubt that their new(?) approach will be ...
• 89
7k views

### Is it feasible to build an index of prime factors?

Would it be possible to break an RSA key, in for example 1 week of time, if the cracker have already spent X number of years building an index of primes by performing every permutation of existing ...
• 483
632 views

### An Elliptic curve cryptography implementation which can be terminated

I'd like to have an implementation of elliptic curve cryptography along the lines of secp256k1 which is secure until some information is published after which it is broken. One idea would be to use ...
• 737
17k views

### Why has the RSA factoring challenge been withdrawn?

Wikipedia states that RSA challenge has been withdrawn. Does it mean that an efficient factoring algorithm is "just around the corner"? or are there some other reasons? If the challenge was still ...
• 1,659
5k views

### How to calculate the time it'll take to crack RSA or DH?

Sometimes the easiest way to describe security of a type of cryptography is to say that "the time it takes to solve for an x-bit key would be y years". How would one go about doing such a calculation ...
• 699
5k views

### Which algorithms are used to factorize large integers?

Even if RSA decided to cancel the Factoring Challenge, it seems that some teams keep working on it. According to Wikipedia, RSA-768 has been factored in late 2009. What are the current large integer ...
• 511