Re: can we find one-way trapdoor funcation family from the theory of calculus

From: Unruh (unruh-spam_at_physics.ubc.ca)
Date: 11/20/05 

Date: 20 Nov 2005 20:18:04 GMT

"Milan VXdgsvt" <milan_vxdgsvt@seznam.cz> writes:

>Pubkeybreaker wrote:

>> Unruh wrote:
>>
>> > NP is not a concept that applies to continuous functions.
>>
>> Yet more nonsense. The question, for example:
>> For given x, is x^2 < a is most definitely a decision problem that
>> is in NP.

>I'm afraid I'm not a mathematician but I have to be on Unruh's side
>with this. Once you are able to specify "x", it is discrete. Even if
>you say "x = pi", it's discrete since you only used a few bytes to
>specify "x".

>How would you decide when "x" was infinitely long, e.g.
>1,414213562373095048801688724209... ?

>> Once again, I suggest you consider f(x) = x. It is most definitely
>> continuous and most definitely has a finite representation.

>That's irrelevant. If you work with "equations" instead of "variables",
>you work with discrete quantities again. No matter what they describe.

>> > and a polynomial in
>> > infinity makes no sense.
>>
>> This sentence is just total gibberish. Exactly what is a
>> 'polynomial in infinity'?????

>The P and NP class are defined with respect to the input size. If the
>length of input is infinite, as is the case with continuous variables,
>the computation time is infinite.
>Some special cases, like 2*2, can be computed in finite time, but there
>are so few of them that they don't matter. It's not actually continuous.

>> > NP is a concept applied to finite discrete
>> > problems. It talks about polynomial in the length of the input. A
>> > continuous function has infinitely long inputs in general.
>>
>> More nonsense. Any input that you supply to any computer function
>> is most definitely finite in its representation.

>You cannot give a continuous problem to the computer.

>> In brief: You have ALMOST ZERO understanding of the topics you are
>> trying to discuss, and you garble the little that you do understand.

>I guess it's more like a misunderstanding.

>A completely different question is, if the space of equations would be
>a good candidate for cryptography, e.g. it's easy to check if
>pow(3.456, 4.567)-pow(1.234, 2.345) = 286,544274225
>but it would be hard to find a short equation that evaluates to
>286,544274225.

>Another candidate would be reverting an unstable system of equations,
>carried out in truncated arithmetic, e.g.
>(http://spanky.triumf.ca/www/fractint/lorenz_type.html):

> xnew = x + (-a*x*dt) + (a*y*dt)
> ynew = y + (b*x*dt) - (y*dt) - (z*x*dt)
> znew = z + (-c*z*dt) + (x*y*dt)
> (default values: dt = .02, a = 5, b = 15, c = 1)

>Given [x,y,z], you can easily carry out 100 iterations, but it would be
>hard to find a point 100 iterations back, that lies in a given small
>cube.

But these are discrete problems. And it is exactly this kind of mixing
problem that does form the trapdoor discrete function. Modular arthmetic is
of this form precisely for numbers much larger than N, arithmetic mod N is
a highly mixing -- it is not really chaotic--system

Note that in your case, if I am given one solution (an input/output pair)
then I can find nearby solutions easily.

>I guess some problems of these kinds are what the OP asked for.

But if so those are exactly classical trapdoor functions.

Computers do discrete mathematics. thus, problems that a computer does are
discrete problems, and one can apply the concept of polynomial in their
input length to them. Now what one wants is also very fast mixing. Given a
year I can make an arbitrarily complex trapdoor function. But modular
arthmetic is already far too slow. So, can one find extremely fast trapdoor
functions?

> Milan

Relevant Pages

  • Re: Interaction of light with matter
    ... Googling for - light interaction matter - gives me lots ... One persistent difficulty bringing all this together is the different foundational concepts used- on one hand, there are discrete entities that interact. ... There is "first quantization" and "second quantization", which deals with discrete particles and either discrete or continuous radiation. ... There are ways to "generate" the refractive index starting from dipole density, but for real materials it's not particularly simple or useful. ...
    (sci.physics)
  • Re: Neural netss (was Re: death of the mind.)
    ... Space-time is either discrete, or not. ... Yes, actually analog devices are much too complex to model completely, ... since it doesn't really matter to be overly exact. ... I suppose I would have to take up discrete maths and theoretical ...
    (sci.cognitive)
  • Re: i am SO wrong.... (nDc)
    ... But a set of discrete points, no matter how many there are, can not ... completely define a continuous form. ... I have an Oracle turntable with an SME III ...
    (rec.music.gdead)
  • Re: Neural netss (was Re: death of the mind.)
    ... > power of the continuum is not needed. ... > to what can be known about matter. ... that discrete devices and discrete responses are the same thing. ... invented calculus and continuous maths for this purpose. ...
    (sci.cognitive)