Re: a^(b^x) mod n?
From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 06/22/05
- Next message: Peter Pearson: "Re: a^(b^x) mod n?"
- Previous message: fredsaf_20055_at_yahoo.com: "Re: a^(b^x) mod n?"
- In reply to: fredsaf_20055_at_yahoo.com: "a^(b^x) mod n?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Wed, 22 Jun 2005 16:04:04 +0000 (UTC)
>Given positive integers a,b,x,n is it possible to efficiently compute:
>a^(b^x) mod n?
>phi(n) is unknown and b^x is so large it can't be used directly.
>Or is it known this to be a hard problem?
This has been conjectured to be hard (even for parallel computers!)
in the following paper:
http://www.cs.berkeley.edu/~daw/papers/timelock.ps
I have never seen any further evidence for its hardness (other than
"I can't seem to find any efficient algorithm for this problem").
- Next message: Peter Pearson: "Re: a^(b^x) mod n?"
- Previous message: fredsaf_20055_at_yahoo.com: "Re: a^(b^x) mod n?"
- In reply to: fredsaf_20055_at_yahoo.com: "a^(b^x) mod n?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
