Talk:Integer factorization

I thought Diffie-Hellman required calculating logarithms on a finite field, not factorisation, or are the problems somehow related?

---

Yes Diffie-Hellman is discrete logarithm. So is DSA. Discrete logarithm for integers modulo a prime appears to be related somehow it factorisation, but a factorisation breakthrough is not guaranteed to solve discrete logarithm. The current champion method of both problems is the Number Field Seive, and there are only minor differences between the version that does factors and the version that does discrete logarithm. Also Shor's algorithm (which works on proposed quantum computers: no-one knows if they can actually be built large enough to be useful) would blow both problems out of the water.

But there is no guarantee (as far as we know at the moment) that a breakthrough factoring algorithm would also do discrete logarithm. I'm not sure if a breakthrough discrete log method is guaranteed to do factoring as well. Several otherwise reputable people have claimed that it would, but i have never seen a proof, or a cite of one.

---

Yes, that's right. I wasn't thinking when I typed the list. I'll remove the DH/DSS entries. --LC

---

Actually i don't know a lot about BBS, but i rather suspect it would be difficult to break if you don't know the modulus. So even if factorisation is easy, if you don't tell people the modulus, BBS might be safe. Does anyone know if this is true? I vaguely remember there are some proposed uses of BBS where you do tell people the modulus, so a quick factor method would at least reduce the usefulness of BBS.

---

If the discrete log problem can be solved quickly, factorization can also be done quickly.. this has been proven.

As for the BBS. Breaking BBS is provably as hard as factoring the Modulus. If you had a huge modulus and it was secret then i guess it'd be incredibly hard to break.

---

The article says:

This problem is of significance in mathematics, cryptography, complexity theory, and quantum computers.

Is it really of significance "in" complexity theory and quantum computers? I would interpret this as meaning that a deeper understanding of integer factorization would lead to a deeper understanding of complexity theory (or quantum computers). I'm not sure that this is true (unlike the case for mathematics or cryptography).

Article name

I was just wondering... Should this be at prime factorization? That term seems to be more common. -- Oliver P. 04:25, 7 Jan 2004 (UTC)

It's rather difficult to say...this article was named "integer factorization" because there are other types of factorization (you can factorize polynomials, for example). I'd say either is OK, so "integer factorization" should stand, I think. Decrypt3 01:05, Jul 30, 2004 (UTC)

Besides, prime factorization is certain to draw fire from Wikipedians pointing out that primes cannot be factorized.
—Herbee 18:30, 18 Feb 2005 (UTC)

No, "prime factorization" is understood to mean decomposing integers into primes. It's a recognized term: [1] (http://mathworld.wolfram.com/PrimeFactorization.html). Decrypt3 21:20, Feb 18, 2005 (UTC)

Granted, but being wrong never seems to inhibit do-gooders from flaming or "being bold". I think integer factorization is slightly better than prime factorization because it draws less fire. —Herbee 15:26, 2005 May 23 (UTC)

---

Is the recently added external link by 136.1.1.154 really necessary? It doesn't really aid comprehension of the topic, and to be honest, I find it to be an insult to the reader's intelligence. Decrypt3 01:09, Jul 30, 2004 (UTC)

I agree it's not particularly useful; I've removed it. — Matt 01:19, 30 Jul 2004 (UTC)

---

There is a separate and unnecessary article called prime factorization algorithm that should be deleted. I don't see anything worthy of merging there. Anyone cares to volunteer?

I vote to delete. All it is, is an extended example of trial division. If anything, the example and source code should be merged into trial division. Decrypt3 21:20, Feb 18, 2005 (UTC)

Prime factorization is in P

... not unknown as this article suggests. See prime numbers.

Factorization record

Perhaps I'm being too pedantic, but the article says

As of 2005, the largest number factored using general-purpose methods...

Surely this is misleading? Large numbers that are p-smooth for small p can be factored in polynomial time, so should it be made clear that it is really the record for factoring semiprimes that is mentioned? Birkett 11:22, 21 May 2005 (UTC)

You're right. That edit was incorrect; I've reverted it. Decrypt3 16:39, May 21, 2005 (UTC)

My original thinking was that the clause "using general methods as part of public research" covered it for all numbers, because has anyone factored a larger number using general methods as part of public research? You could easily generate such a record, of course. Perhaps we need a better qualifier than "as part of public research"? — Matt Crypto 21:57, 22 May 2005 (UTC)

Now I'm thinking that maybe the "general-purpose methods" part should go. We use semiprimes as the gauge of factoring technology because they're the most "difficult", but in theory, the fact that they're semiprimes doesn't matter for general-purpose algorithms, by definition. I think larger numbers have been factored, but using specialized algorithms because they're not semiprimes. I think only the semiprimes are really relevant here because of their application in public-key crypto. So I think the general-purpose part is causing the problem. Decrypt3 08:09, May 23, 2005 (UTC)