Looking for EXPTIME-algorithm

Could somebody give me an example of an algorithm such that the
following conditions would be true.

Let M and N be finite sets such that |M| = |N|.


1. There is bijective mapping f: M -> N
2. It is (computationally) easy to calculate y = f (x), where x belongs

to M and y belongs to N
3. It is hard to calculate x = g (y), where g is inverse function of f.

Calculation of x should take EXPTIME (EXPTIME-completeness would be
nice property).


In short, the algorithm should resemble a cryptographic algorithm (the
longer it takes to calculate x the better). Perfect hashing is in some
ways similar to the algoritm I am looking for: there are no collisions
but the computation of x should be hard. Prime factorization won't do
the trick, because there are super-polynomial ways to factor a prime
(if I have understood the idea correctly).


How about if |M| < |N| and the first condition is f: M -> N is
injenctive mapping?


Any suggestions or links? I'm stuck. Thanks.

.

Relevant Pages

  • Re: HPGCC 2: sat_decode_real
    ... > GCD is not done by prime factorization; ... > Algorithm, which does not use primes or factorizing or anything like ... Prev by Date: ...
    (comp.sys.hp48)
  • Re: If P==NP how to solve the Prime Factorization problem?
    ... But no where any algorithm is mentioned to ... solve Prime factorization in Polynomial time if we know an algorithm ... If P==NP then this algorithm will terminate in polynomial time. ...
    (comp.theory)
  • Looking for EXPTIME-algorithm
    ... There is bijective mapping f: ... Calculation of x should take EXPTIME (EXPTIME-completeness would be ... the algorithm should resemble a cryptographic algorithm (the ... Prime factorization won't do ...
    (comp.theory)
  • Re: If P==NP how to solve the Prime Factorization problem?
    ... But no where any algorithm is mentioned to ... solve Prime factorization in Polynomial time if we know an algorithm ... If P==NP then this algorithm will terminate in polynomial time. ...
    (comp.theory)