Re: A new hard problem
- From: bobic <fbloveu@xxxxxxxxxxx>
- Date: Sat, 04 Aug 2007 14:58:40 -0000
On 8 4 , 4 12 , Thomas Pornin <por...@xxxxxxxxx> wrote:
According to bobic <fblo...@xxxxxxxxxxx>:
Hi, guys, recently, I meet the following problem, it seems hard,
however, I have no idea about how hard it is. Can you help me? Thanks
in advance!
On input g^a, g^b, a/b, to compute a.
Let's suppose that g is the generator for a finite, cyclic group G.
The group is known, it has order q. g is known. a and b are integers
modulo q (0 < a < q and 0 < b < q) and neither is known.
Then your problem is equivalent to discrete logarithm.
If you can solve discrete logarithm in G, then you can compute a from
g and g^a.
On the other hand, assume that you know g^x and want to compute x.
Choose a random integer v modulo q and decide that a = vx and b = x.
You can compute g^a = (g^x)^v
You have g^b = g^x
You have a/b = (vx)/x = v
Hence you have an instance of your problem. If you can solve it,
then you get vx and can compute x = (vx)/v.
--Thomas Pornin
That's it! Thank you very much!
.
- References:
- A new hard problem
- From: bobic
- Re: A new hard problem
- From: Thomas Pornin
- A new hard problem
- Prev by Date: Need Some help on QUADRATIC SIEVE
- Next by Date: Re: tnn.sports.triathlon
- Previous by thread: Re: A new hard problem
- Next by thread: how to coonvert decimal number in tobase 64 format.
- Index(es):
Relevant Pages
|
