Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Factoring is not known to be NP-complete. This question asked for consequences of Factoring being NP-complete. Curiously, no one asked for consequences of Factoring being in P (maybe because such a question is trivial).

So my questions are:

  1. Which would be the theoretical consequences of Factoring being in P? How the overall picture of complexity classes would be affected by such a fact?
  2. Which would be the practical consequences of Factoring being in P? Please do not say that banking transactions could be in jeopardy, I already know this trivial consequence.
share|improve this question
5  
I asked a similar question a few days ago: "What is the power of P with an integer factorization oracle?" cstheory.stackexchange.com/questions/4765/… –  Marzio De Biasi Feb 23 '11 at 16:38
    
Also related: What are the consequences of factoring being NP-complete? –  Kaveh Feb 24 '11 at 4:11
3  
@Kaveh, the question already links to that one. –  Peter Taylor Feb 24 '11 at 7:16

3 Answers 3

up vote 28 down vote accepted

There are pretty much no complexity-theoretic consequences of Factoring being in P. This means that there are no good justifications for factoring being hard, other than that nobody has been able to crack it so far.

Polynomial-time factoring would make it possible to take square roots over $Z_n$ (and also over a much more general class of rings as well), and give polynomial-time algorithms for a number of other number-theoretic problems for which the bottleneck in the algorithm is currently factoring.

As for practical consequences, banking transactions are probably not that much of a problem -- as soon as it was known that factoring was in P, the banks would switch to some other system, probably causing only a brief period of delays while this was being implemented. Decoding past banking transactions would probably not cause serious problems for the banks. A much more serious problem is that all the communication which was previously protected by RSA would now be in danger of being read.

share|improve this answer
35  
A bit off-topic, but as soon as it was known that factoring was in P, the banks would switch to some other system is largely wishful thinking. I discovered in December that a company which doesn't do anything except process credit card details was using a variant of Vigenère with a key shorter than some runs of known plaintext. Worse, the technical director of the company wouldn't believe me that it was insecure until I sent him some attack code. MD5, despite being widely considered broken, is still used heavily in banking. –  Peter Taylor Feb 23 '11 at 17:12
    
@PeterTaylor, as soon as it was known that factoring was in P, the banks would switch to some other system is largely wishful thinking". With the current cheap price of Flash memory, it is completely feasible to create a One Time Pad solution for banking, users would go from time to time to an ATM to download extra random bytes. RSA is just cheaper and simpler. –  Flávio Botelho Feb 24 '11 at 0:14
    
Having strong symmetric ciphers is no replacement for asymmetric ciphers, though it suffices for certain specific tasks. You run into the issue of not being able to use digital signatures, etc. –  Joe Fitzsimons Feb 24 '11 at 0:22
    
Actually you can have digital signatures with symmetric ciphers! It's just a lot more cumbersome and you need a much greater confidence in the trusted 3rd party. Look up at the Handbook of Applied Cryptography's chapters 11.6 and 11.7. –  Flávio Botelho Feb 24 '11 at 0:58
    
@Flavio: But non-repudiation doesn't work in the same way, does it? –  Joe Fitzsimons Feb 24 '11 at 1:12

RSA is one of the most important encryption/signature schemes which breaks if FACTORING is in P. However, there are many more. Several (but not all) of them are based on the assumption that distinguishing squares and non-squares modulo a composite number is hard:

  1. Rabin's signature scheme
  2. Rabin's oblivious transfer
  3. Goldwasser–Micali semanticly-secure cryptosystem
  4. Blum-Blum-Shub pseudorandom generator
  5. Feige-Fiat-Shamir identification scheme

And many other schemes. However, note that schemes based on the hardness of discrete log (say, the Diffie-Helmann protocol or Elgamal encryption/signature scheme) will continue to be secure.

share|improve this answer
2  
It seems very likely to me that if factoring is in P, then so is the discrete log problem. Certainly the converse is true. –  Joe Fitzsimons Feb 25 '11 at 22:48
    
@Joe: I have the same feelings, but is there any proof or mathematical evidence? –  Sadeq Dousti Feb 26 '11 at 3:16
2  
There is an easy proof of the converse, since $a^{pq} \equiv a^{p+q-1}~(\mbox{mod } pq)$. Take $c_a = \log_N(a^N \mbox{mod }N)$. So if $p = x + y$ and $q = x - y$, then $x = \frac{c_a + 1}{2}$, and $y = \sqrt{x^2 - N}$, and you have your factors. I don't think there is a known proof of the converse, but I may be wrong. Either way, both are instances of the abelian hidden subgroup problem, and are linked via Euler's theorem, so there are similarities. –  Joe Fitzsimons Feb 26 '11 at 4:33
4  
@Joe: Very interesting! Your comment motivated me to dig more into this, and found a result by Eric Bach which states that "solving the discrete logarithm problem for a composite modulus is exactly as hard as factoring and solving it modulo primes." –  Sadeq Dousti Feb 26 '11 at 7:31
    
Lattice based crypto should hopefully remain secure though. –  Antimony Aug 21 '12 at 5:28

A major consequence of Factoring being in $P$ is that multiplication (of two equal size integers) is not one-way function. This would be very surprising result since multiplication is widely believed to be the strongest candidate for one-way function. However, this may not change the picture of complexity classes.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.