Re: multiplicative group question

From: David A Molnar (dmolnar_at_argus.EECS.Berkeley.EDU)
Date: 06/29/05 

Date: Wed, 29 Jun 2005 20:20:59 +0000 (UTC)

Khan <khanhvn@yahoo.com> wrote:
> Is there a computable multiplicative (semi)group such that:
> (1) Finding Nth root, i.e. find M given M^n and n, is intractable.
> (2) Finding multiplicative inverse is intractable (or inverses do not
> exist)

> RSA, for example, satisfies #1, but I wonder if there is something with
> both #1 and #2.

You might enjoy reading Susan Hohenberger's master's thesis.
http://theory.lcs.mit.edu/~cis/theses/hohenberger-masters.ps

She investigates the notion of groups that satisfy 2) plus a number
of related notions. Unfortunately, as far as I know, no (semi)group
is known that satisfies 2), let alone both 1) and 2). If you happen
to find a candidate, I would be interested to hear about it.

-David Molnar

Quantcast