Re: Determining the inverse function operation from a function definition

SM Ryan <wyrmwif@tsoft.org>28 Apr 2005 14:54:06 -0400

From comp.compilers

Related articles
Determining the inverse function operation from a function definition rlfoster1@cox.net (Ron Foster) (2005-04-26)
Re: Determining the inverse function operation from a function definit torbenm@diku.dk (2005-04-28)
Re: Determining the inverse function operation from a function definit mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2005-04-28)
Re: Determining the inverse function operation from a function definit lfinsto1@gwdg.de (Laurence Finston) (2005-04-28)
Re: Determining the inverse function operation from a function definit wyrmwif@tsoft.org (SM Ryan) (2005-04-28)
Re: Determining the inverse function operation from a function definit drdiettrich@compuserve.de (Dr. Diettrich) (2005-04-28)
Re: Determining the inverse function operation from a function definit nmm1@cus.cam.ac.uk (2005-04-30)
Re: Determining the inverse function operation from a function definit gah@ugcs.caltech.edu (glen herrmannsfeldt) (2005-04-30)
Re: Determining the inverse function operation from a function definit drdiettrich@compuserve.de (Dr. Diettrich) (2005-05-13)
| List of all articles for this month |

 From: SM Ryan Newsgroups: comp.compilers Date: 28 Apr 2005 14:54:06 -0400 Organization: Quick STOP Groceries References: 05-04-067 Keywords: theory Posted-Date: 28 Apr 2005 14:54:06 EDT

# It "feels" as though the inverse operation could be accomplished by
# backing-out the original operation steps in reverse order, but it appears
# that such an approach could also be fraught with peril.

Function inversion is simple in affine functions, after dealing with
issues like f(x)=0. The problem for these kinds of functions is
equivalent to inverting a matrix, which may or may not be singular. If
the function is not affine but is differentiable, then it is locally
affine; you can see if you can invert the differential matrix. Again
be aware of potential singularities.

Prolog does symbolic inversion on some functions.

Some function inversions are thought to be inherently difficult;
cryptography is based on this assumption. For example DES is an
invertible function that is intentionally hard to invert.

# I'd appreciate it if someone could point me to some relevant material.