Re: How about helping optimization in language?

From	Bernd Paysan <bernd.paysan@gmx.de>
Newsgroups	comp.lang.forth
Subject	Re: How about helping optimization in language?
Date	2012-04-10 23:11 +0200
Organization	1&1 Internet AG
Message-ID	<jm27l5$5ku$1@online.de> (permalink)
References	(9 earlier) <7xiph9bm0y.fsf@ruckus.brouhaha.com> <jlv01a$evd$1@online.de> <7xiph86tbe.fsf@ruckus.brouhaha.com> <2012Apr10.113955@mips.complang.tuwien.ac.at> <7xty0rq4jl.fsf@ruckus.brouhaha.com>

Show all headers | View raw

Paul Rubin wrote:

> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>>secret-key) crypto algorithms you think are "in NP".
>>
>> They all have to be.  You want the verification (decoding) to be
>> relatively fast,
> 
> Yes, but Bernd appeared to be incorrectly using "in NP" to mean
> "NP-hard", so I used it the same way.

Well, it's sloppy wording, but what I mean is "in and only in NP, under 
the assumption that P!=NP".  Given that P!=NP has no proof, it is a bit 
difficult to correctly speak about these things, but that doesn't really 
matter.  You know what I mean, and that's what communication is about.

>> If the crypto algorithm is any good, finding the key will also be
>> NP-hard (and thus, NP-complete).
> 
> What makes you think this?  Do you know of any specific crypto
> algorithms where finding the key is known to be NP-hard?  What is
> known about their practical security?  Does anyone use them?

In general, all crypto algorithms use algorithms which are presumed to 
be NP-hard, and no easy to solve subset exists.  The Knapsack based 
cryptosystems are an example, how difficult that is: many of them have 
been successfully attacked, while the problem in principle is NP hard, 
but unfortunately not always.  Here's a paper on this, trying to create 
a secure knapsack based cryptosystem:

http://math.univ-angers.fr/~evain/npComplet.pdf

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: How about helping optimization in language? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-03-28 12:07 -0500
  Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-01 22:48 -0700
    Re: How about helping optimization in language? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-04-02 04:41 -0500
      Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-02 17:40 -0700
        Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-02 15:35 -1000
          Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-02 19:25 -0700
            Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-02 20:45 -1000
            Re: How about helping optimization in language? Mark Wills <markrobertwills@yahoo.co.uk> - 2012-04-03 00:51 -0700
              Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-02 22:17 -1000
                Re: How about helping optimization in language? Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-04-03 02:32 -0700
              Re: How about helping optimization in language? mhx@iae.nl (Marcel Hendrix) - 2012-04-03 20:22 +0200
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-03 11:53 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-03 09:10 -1000
                Re: How about helping optimization in language? Mark Wills <markrobertwills@yahoo.co.uk> - 2012-04-03 14:16 -0700
                Re: How about helping optimization in language? mhx@iae.nl (Marcel Hendrix) - 2012-04-05 21:27 +0200
              Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-03 22:27 +0200
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-03 10:45 -1000
                Re: How about helping optimization in language? Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-04-04 10:34 +0000
            Re: How about helping optimization in language? Mark Wills <markrobertwills@yahoo.co.uk> - 2012-04-03 00:43 -0700
        Re: How about helping optimization in language? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-04-03 03:59 -0500
          Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-03 20:34 -0700
            Re: How about helping optimization in language? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-04-04 05:32 -0500
              Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-07 22:15 -0700
                Re: How about helping optimization in language? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-04-08 04:55 -0500
                Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-08 15:51 +0000
                Re: How about helping optimization in language? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-04-08 11:34 -0500
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-08 13:11 -0700
                Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-08 23:40 +0200
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-08 15:14 -0700
                Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-09 09:37 +0000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-09 19:05 -0700
                Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-10 10:32 +0000
                Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-08 23:18 +0200
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-08 20:51 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-08 19:09 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-09 21:05 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 21:57 -1000
                Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-09 17:42 +0200
                Re: How about helping optimization in language? jacko <jackokring@gmail.com> - 2012-04-09 09:34 -0700
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-09 22:37 -0700
                Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-10 09:39 +0000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-10 03:12 -0700
                Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-10 23:11 +0200
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-10 21:18 -0700
                Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-11 10:00 +0000
                Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-10 22:12 +0200
                Re: How about helping optimization in language? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-04-10 16:24 -0500
                Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-10 08:34 +0000
                Re: How about helping optimization in language? John Passaniti <john.passaniti@gmail.com> - 2012-04-09 10:09 -0700
                Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-09 21:21 +0200
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-09 19:02 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 16:44 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-09 20:00 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 17:27 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-09 20:49 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 18:12 -1000
                Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-10 10:24 +0000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-10 03:40 -0700
                Re: How about helping optimization in language? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-04-10 04:39 -0500
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-10 03:05 -0700
                Re: How about helping optimization in language? Coos Haak <chforth@hccnet.nl> - 2012-04-10 18:13 +0200
                Re: How about helping optimization in language? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-04-10 12:02 -0500
                Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-10 14:36 +0000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-10 23:01 -0700
                Re: How about helping optimization in language? Mark Wills <markrobertwills@yahoo.co.uk> - 2012-04-11 00:51 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-10 22:18 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-11 02:45 -0700
                Re: How about helping optimization in language? "Paul E. Bennett" <Paul_E.Bennett@topmail.co.uk> - 2012-04-11 19:47 +0100
                Complexity (was: How about helping optimization in language?) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-09 08:52 +0000
                Re: Complexity (was: How about helping optimization in language?) Mark Wills <markrobertwills@yahoo.co.uk> - 2012-04-09 03:01 -0700
                Re: Complexity Paul Rubin <no.email@nospam.invalid> - 2012-04-09 10:17 -0700
                Re: Complexity "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 11:33 -1000
                Re: Complexity "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 11:43 -1000
                Re: Complexity (was: How about helping optimization in language?) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-10 07:31 +0000
                Re: Complexity (was: How about helping optimization in language?) Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-09 17:08 +0200
                Re: Complexity "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 11:21 -1000
                Re: Complexity Paul Rubin <no.email@nospam.invalid> - 2012-04-09 20:30 -0700
                Re: Complexity "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 22:19 -1000
                Re: Complexity Paul Rubin <no.email@nospam.invalid> - 2012-04-10 01:48 -0700
                Re: Complexity Mark Wills <markrobertwills@yahoo.co.uk> - 2012-04-10 01:28 -0700
                Re: Complexity "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 22:48 -1000
                Re: Complexity Paul Rubin <no.email@nospam.invalid> - 2012-04-10 01:51 -0700
                Re: Complexity Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-04-10 20:06 +0000
                Re: How about helping optimization in language? stephenXXX@mpeforth.com (Stephen Pelc) - 2012-04-09 10:24 +0000
                Re: How about helping optimization in language? Nomen Nescio <nobody@dizum.com> - 2012-04-09 16:18 +0200
                Re: How about helping optimization in language? Mark Wills <markrobertwills@yahoo.co.uk> - 2012-04-09 07:23 -0700
                Re: How about helping optimization in language? stephenXXX@mpeforth.com (Stephen Pelc) - 2012-04-09 15:27 +0000
            Re: How about helping optimization in language? BruceMcF <agila61@netscape.net> - 2012-04-04 06:51 -0700
        Re: How about helping optimization in language? stephenXXX@mpeforth.com (Stephen Pelc) - 2012-04-03 09:06 +0000
        Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-03 16:13 +0000
          Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-03 12:43 -0700
            Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-03 10:16 -1000
              Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-03 13:41 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-03 11:01 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-03 22:42 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-03 21:11 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-04 01:02 -0700
            Re: How about helping optimization in language? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-04-04 05:35 -0500
              Re: How about helping optimization in language? Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-04-04 15:01 +0000
              Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-06 00:08 -0700
                Re: How about helping optimization in language? Jan Coombs <jan_2011-02@murray-microft.co.uk> - 2012-04-06 12:05 +0100
            Re: How about helping optimization in language? Alex McDonald <blog@rivadpm.com> - 2012-04-03 15:56 -0700
          Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-03 22:06 +0200
            Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-03 13:22 -0700
            Re: How about helping optimization in language? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-04-04 05:43 -0500
              Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-04 23:15 +0200
              Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-04 19:02 -0700
            Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-04 13:34 +0000
    Re: How about helping optimization in language? stephenXXX@mpeforth.com (Stephen Pelc) - 2012-04-02 09:49 +0000
      Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-02 20:04 -0700
        Re: How about helping optimization in language? stephenXXX@mpeforth.com (Stephen Pelc) - 2012-04-03 09:30 +0000
          Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-03 13:16 -0700
            Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-03 22:45 +0200
              Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-03 23:26 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-03 21:29 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-04 02:32 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-04 07:30 -1000
                Re: How about helping optimization in language? John Passaniti <john.passaniti@gmail.com> - 2012-04-04 08:51 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-04 10:31 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-07 21:20 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-07 19:18 -1000
                Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-08 15:59 +0000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-08 22:12 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-08 19:42 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-08 23:26 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-08 20:37 -1000
                Re: How about helping optimization in language? Fritz Wuehler <fritz@spamexpire-201204.rodent.frell.theremailer.net> - 2012-04-09 23:33 +0200
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 11:52 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-09 18:42 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 15:57 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-09 19:08 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 16:29 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-09 19:53 -0700
                Re: How about helping optimization in language? "Elizabeth D. Rather" <erather@forth.com> - 2012-04-09 17:05 -1000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-09 20:15 -0700
                Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-10 21:46 +0200
                Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-10 10:42 +0000
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-11 21:26 -0700
                Re: How about helping optimization in language? Mark Wills <markrobertwills@yahoo.co.uk> - 2012-04-12 00:24 -0700
                Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-12 01:55 -0700
            Re: How about helping optimization in language? stephenXXX@mpeforth.com (Stephen Pelc) - 2012-04-03 22:06 +0000
              Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-04 13:20 +0000
                Re: How about helping optimization in language? stephenXXX@mpeforth.com (Stephen Pelc) - 2012-04-04 21:18 +0000
                Re: How about helping optimization in language? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-05 15:36 +0000
                Re: How about helping optimization in language? stephenXXX@mpeforth.com (Stephen Pelc) - 2012-04-05 18:32 +0000
            Re: How about helping optimization in language? kenney@cix.compulink.co.uk - 2012-04-04 04:39 -0500
              Re: How about helping optimization in language? Paul Rubin <no.email@nospam.invalid> - 2012-04-04 02:50 -0700
            Re: How about helping optimization in language? BruceMcF <agila61@netscape.net> - 2012-04-03 18:07 -0700
              Re: How about helping optimization in language? Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-04-05 11:10 +0000
                Re: How about helping optimization in language? BruceMcF <agila61@netscape.net> - 2012-04-05 13:21 -0700
                Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-05 23:26 +0200
                Re: How about helping optimization in language? Mark Wills <markrobertwills@yahoo.co.uk> - 2012-04-05 14:49 -0700
                Re: How about helping optimization in language? Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2012-04-06 08:58 +0100
                Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-06 19:07 +0200
                Re: How about helping optimization in language? Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2012-04-07 10:07 +0100
                Re: How about helping optimization in language? Bernd Paysan <bernd.paysan@gmx.de> - 2012-04-07 21:18 +0200
                Re: How about helping optimization in language? BruceMcF <agila61@netscape.net> - 2012-04-08 07:36 -0700
                Re: How about helping optimization in language? jacko <jackokring@gmail.com> - 2012-04-08 07:56 -0700
                Re: How about helping optimization in language? jacko <jackokring@gmail.com> - 2012-04-08 07:49 -0700

csiph-web