CDR: Re: Minesweeper and defeating modern encryption technology

[Declan McCullagh]

It's been a long time since my computer science classes. But I'll give
it a shot.

The general name for this topic is complexity theory, the study of
how inherently difficult certain classes of problems are to solve.

Perhaps a not unreasonable summary would be problems in the class "P"
can be solved in deterministic polynomial time. Some of these would
include problems like simple sorting of strings that your OS does
whenever it displays files in a directory.

"NP" problems, on the other hand, are those that can be solved in
nondeterministic polynomial time (think only by guessing). NP
includes P.

Of relevance to our discussion is that factoring is a NP problem.
Much of modern cryptography relies on factoring being a "hard" problem.
If it is not, things will get interesting quickly. :)

Arnold Reinhold has another view here, saying P=NP is not relevant
to crypto:
http://world.std.com/~reinhold/p=np.txt

-Declan
 
(PS: don't use the toad.com address)


On Fri, Nov 03, 2000 at 07:40:51PM +0100, Olav wrote:
> Perhaps someone could explain this P vs. NP stuff to a normal
> not-yet-student?
> And, this program, what features are required to prove his theory?
> 
> 
> Thanks in advance,
> Olav
> 
> 
> On Thu, 02 Nov 2000, you wrote:
> > >http://digitalmass.boston.com/news/daily/11/01/minesweeper.html
> > 
> > >from the article:
> > "Proving the conjecture false would mean that modern encryption technology,
> > the foundation of electronic commerce, would be open to easy attack."
> > 
> > Isn't that a little general? Possibly jumping to some hasty conclusions
> > about P versus NP as well?
>