# Tag Info

## Hot answers tagged factorization

14

No, it is not at all feasible to build an index of prime factors to break RSA. Even if we consider 384-bit RSA, which was in use but breakable two decades ago, the index would need to include a sizable portion of the 160 to 192-bit primes, so that the smallest factor of the modulus has a chance to be in the index. Per the Prime number theorem there are in ...

11

The three main general-purpose algorithms for factorization are the quadratic sieve (QS), the elliptic curve method (ECM) and the number field sieve (NFS). On Complexity The running time of these algorithms is expressed with the L-notation: $L_n[a,c]$ means that the asymptotic complexity of factoring a number $n$ is $O(e^{(c+o(1))(\log n)^a(\log \log ... 8 The generic discrete logarithm problem is this: Given a group$(G, ·)$with generator$g$and$y \in G$, find$x \in \mathbb N$such that$y = g^x$. The "classic" discrete logarithm problem (the one used in "classic" DSA and ECDSA) is this with some subgroup of the (multiplicative) group of a prime field, i.e.$(\mathbb Z/p \mathbb Z)^*$: Given a ... 8 Msieve is public domain and has good reputation. For instance, a 631-bit integer was factored in late 2010 with Msieve used (at least for some parts). 8 RSA themselves (the company) say this in their RSA Factoring Challenge FAQ: Why is the RSA Factoring Challenge no longer active? Various cryptographic challenges — including the RSA Factoring Challenge — served in the early days of commercial cryptography to measure the state of progress in practical cryptanalysis and reward researchers for the new ... 7 You might want to look at NIST SP800-57, section 5.2. As of 2011, new RSA keys generated by unclassified applications used by the U.S. Federal Government, should have a moduli of at least bit size 2048, equivalent to 112 bits of security. If you are not asking on behalf of the U.S. Federal Government, or a supplier of unclassified software applications to ... 7 For numbers over about 115 (decimal) digits, the best algorithm currently known in the General Number Field Sieve (GNFS – sometimes just called the Number Field Sieve, though there's also a Special Number Field Sieve for factoring numbers of a special form). The GNFS, unfortunately, is an exceedingly complex algorithm, and I don't know of any online ... 6 In addition to Msieve factor is a public-domain integer factorization program for Windows. Qsieve, a suite of programs for integer factorization. Factorization source code and other related code is here There is a database of prime numbers here like List of all saved primes (500 digits+) and here is a list of factorization software and libraries. 6 Pure nonsense. For choosing the random$\Delta$between$\sqrt{\min(N, Ň)}$and$\sqrt{\max(N, Ň)}$there are too many possibilities for it to work. For example whenever the first and last digits of$N$differ, you get something like$\frac{1}{10} \cdot \sqrt N$possibilities (the exact formula doesn't matter). So you can replace the first formula$gcd[N, ...

6

I don't believe a lower bound has ever been proven for the "fewest" number of bits needed. Coppersmith showed, however, how given either the $n/4$ least or $n/4$ most significant bits of $p$ where $n$ is the size of the modulus $N=pq$, $N$ can be efficiently factored. Additionally, given the $n/4$ least significant bits of $d$, one can reconstruct $d$ (and ...

5

I don't think there's anything to worry about here. Remarks 4.2 and 4.3 in the second paper point out that these approaches need to first find a point on a curve with a very large conductor/discriminant, and that seems to be very hard. (Harder than factoring the integer using NFS.) There are many ways to compute factorings and discrete logarithms where you ...

5

Let's assume for an instant that you could build a large table of all primes. Then... what ? How would you use it ? What would you look up ? If you "just" scan the table and try to divide the number to factor by each prime, then this is known as trial division; there is no need to store the primes (they can be regenerated on-the-fly; that's the division ...

5

Actually, from my examination of the paper, I don't know if the result is of even academic interest. One generic way to factor a value $n$ is to take a function $F$ and define: for i = 1 to some_upper_limit do temp = F( n, i ) factor = gcd( temp, n ) if 1 < factor and factor < n output factor; halt output Failed This will work ...

5

No. The paper reports success factoring integers of 13 digits 15 digits in an hour, or of the form $n = p\cdot (p+2)$, which are factored in seconds with existing algorithms (Pollard rho or ECM, Fermat). There is no comparison of the proposed algorithms against these classics. The proposed algorithms are useless as a direct method for factoring numbers of ...

5

The procedure to do this is: Find a large prime factor $r$ When searching for the prime $p$, look among numbers of the form $rk+1$ When we find our prime $p$, we know that $p-1$ will have $r$ as a factor. Step 1 is comparatively cheap compared to original search from the prime $p$; we select an $r$ which is large (as far as factors of $p-1$ go), but is ...

4

If you have to ask, you are probably not the intended audience. Quoting the introduction of the paper: We implemented our method on a PC using Shoup’s NTL library version 5.4.1 [7]. Unfortunately, we have to say that the practical effect of our method is not good on a single PC, it is worse than many known algorithms on this problem. However, we ...

4

The theory is explained in the research paper that introduced the idea: Time-lock puzzles and timed-release crypto. Ronald L. Rivest, Adi Shamir, and David A. Wagner. MIT Laboratory for Computer Science, Technical memo MIT/LCS/TR-684 (1996) (Revision 3/10/96). The paper is cited in Rivest's description of the time capsule. As the security analysis in ...

4

Yes there are several algorithms, as simple or even simpler as the proposed algorithm, that are expected to factor $N$ much faster. The simplest and oldest is the Sieve of Eratosthenes (which works for any $N$); there's also Fermat's factoring method, preferably with the easy sieve improvement to recognize squares efficiently (which works when $N$ is the ...

4

Yes, using Miller-Rabin with a random witness does give a practical factoring method. When you run the Miller-Rabin algorithm, it can end in one of three ways: The final value is not 1; this case causes Miller-Rabin to output "Composite" An intermediate value was not 1 or N-1, but the next value was 1; this causes Miller-Rabin to output "Composite" The ...

3

This recommendation is here specifically to prevent Fermat's Factorization Method from yielding a factorization. This method can yield factor a number if its two factors are sufficiently close; this recommendation would prevent that from being a possibility. Now, you ask 'is such a recommendation reliable'? Well, it certainly does prevent that ...

3

If you're asking about the likely future for public key cryptography, then my opinion is that we are likely to see a transition (gradually over the next number of years) from things such as RSA and DH, and into Elliptic Curve Cryptography. This is because ECC is just more efficient; we know that we can break RSA and DH in subexponential time; that means ...

3

Note: this is only an attempt at answering the first part of the question, asking if William's p+1 factorization method is redundant with Pollard's p-1, on the basis of how the algorithms are used in practice. Pollard's p-1 (resp. William's p+1) factorization method is efficient to find a factor of $n$ if any of the factors $p$ of $n$ is such that $p-1$ ...

3

The flaw in your reasoning lies in your assumption that finding the discrete log of $f$ is any easier than finding the discrete log of $g$. It just isn't. That assumption is not correct. And if you try to recurse and apply your procedure to $f$, you'll recurse for a very long time, and your algorithm will take exponentially long. Let me summarize your ...

2

The simplest answer would be to look at the keylength.com site, and if you don't trust that, to the linked papers, particularly by NIST and ECRYPT II. Bare in mind that you may have additional restrictions and - if you are brave or stupid - relaxations depending on the use case.

2

How long would that take in permutations and perhaps with the fastest computer in the world? Given the analysis by @fgrieu using the prime number theorem, we know there are roughly $2^{185}$ possible prime numbers which could be used to construct a $384$-bit RSA key pair. Thus there are $2^{185^2}$ possible RSA key pairs (since it takes two primes to ...

2

Unless $2^t$ is the order of $2$ in the group $\mathbb Z_n$, in which case the solution is trivial. Unless the factors of $n$ are known, in which case the Chinese remainder theorem can be used. Unless $n$ (or its factors) has a special form, with only a few sparse bits being set (e.g. $n = 2^a + 2^b + 1$) and similar cases where $n$ has only a few ...

2

It becomes clear once you understand what $p-1$ and ECM are doing. I'll start with $p-1$, since it is simpler. Suppose the number you want to factor, $n$, is the product of two primes: $p$ and $q$. If we knew $p-1$, we could get $p$ from $n$ by doing $$\gcd(a^{p-1} - 1 \bmod n, n) = p.$$ This works because by working modulo $n$, we're working "in ...

2

This question is only relevant if you choose $p,q$ in a non-standard way. The standard way to choose $p,q$ is to choose them as two independent random $k/2$-bit numbers. If you do it the standard way, the question is not relevant (the probability that $|p-q|$ is too small is negligible -- and is dominated by the chances of other kinds of failures). This ...

2

Before you edited it, both $b$ and $k$ were unknowns. Now $k$ is known and the challenge is to find $b$. Assuming $p$ is prime, and that $gcd(k,p-1)=1$ this can be done by raising $g$ to the power of the inverse of $k \mod p-1$. This is the same as RSA decryption where the modulus is prime and similar to decrypting where the factorization of the composite ...

Only top voted, non community-wiki answers of a minimum length are eligible