Re: The factoring problem

From: Simon Johnson (simon.johnson_at_gmail.com)
Date: 06/27/05 

Date: 27 Jun 2005 02:44:12 -0700

> Sorry for a possibly stupid question...

It's not a stupid question, it's a very important question indeed.

A lot of people to talk about whether factoring in the NP complexity
class as being important to cryptography. This, however, is a tad
misleading. Complexity theory makes a statement about the difficulty of
the problem at infinity. In cryptography, we never work with numbers of
infinite size. It is quite possible that if factoring was found to be
in P that it'd still be useful to cryptography because the P time
algorithm may run in O(n^100).

All that matter to cryptography is that factoring is significantly more
difficult than multiplication at useable sizes of numbers.

Simon.

Relevant Pages

  • Re: A Newbie to the group.
    ... had been suggested to me by an Iraqi mathematician who had read my ... work in factoring vectors and I was convinced that Ada-95 was the only ... I take you mean why did I think Ada was the more suitable language? ... I had been introduced to cryptography by one Dr. Chalabi who I ...
    (comp.lang.ada)
  • Re: A Newbie to the group.
    ... had been suggested to me by an Iraqi mathematician who had read my ... work in factoring vectors and I was convinced that Ada-95 was the only ... I take you mean why did I think Ada was the more suitable language? ... I had been introduced to cryptography by one Dr. Chalabi who I ...
    (comp.lang.ada)
  • Re: A Newbie to the group.
    ... had been suggested to me by an Iraqi mathematician who had read my ... work in factoring vectors and I was convinced that Ada-95 was the only ... I take you mean why did I think Ada was the more suitable language? ... I had been introduced to cryptography by one Dr. Chalabi who I ...
    (comp.lang.ada)
  • Re: A Newbie to the group.
    ... had been suggested to me by an Iraqi mathematician who had read my ... work in factoring vectors and I was convinced that Ada-95 was the only ... I had been introduced to cryptography by one Dr. Chalabi who I ... prepares her encryption program with all the ...
    (comp.lang.ada)
  • Re: Speculative, but at least interesting
    ... >With the proviso that my knowledge of cryptography is limited to ... Certainly factoring experts have no such fear. ... >in factoring techniques. ... I know of no factoring methods which ...
    (sci.math)