Re: can we find one-way trapdoor funcation family from the theory of calculus
From: Unruh (unruh-spam_at_physics.ubc.ca)
Date: 20 Nov 2005 20:18:04 GMT
"Milan VXdgsvt" <email@example.com> writes:
>> 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
>How would you decide when "x" was infinitely long, e.g.
>> 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
>Another candidate would be reverting an unstable system of equations,
>carried out in truncated arithmetic, e.g.
> 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
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