mersenneforum.org Discrete logarithm software
 Register FAQ Search Today's Posts Mark Forums Read

 2011-08-28, 18:57 #1 Unregistered   22×797 Posts Discrete logarithm software Hi, i'm searching for software that can perform discrete logarithm. base: 47 modulus: 256 bit long power: 160 bit long Can this be calculated in acceptable time? If yes, do you know software that can perform it?
2011-08-28, 19:20   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203068 Posts

Quote:
 Originally Posted by Unregistered Hi, i'm searching for software that can perform discrete logarithm. base: 47 modulus: 256 bit long power: 160 bit long Can this be calculated in acceptable time? If yes, do you know software that can perform it?
the first can be performed by log(x)/log(47) the second is capable in PARI/gp the third I can't get to work in pari gp though at least not without breaking it down more maybe.

 2011-08-28, 19:42 #3 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 2·7·461 Posts Yes, this can be done in acceptable time, though I'm not sure what the best tool is. The online Magma calculator can do discrete logs mod 2^127-1 in about eight seconds, mod 2^100+277 in about one second, mod 2^140+37 in about 16 seconds ... it ought to be not all that much harder than factoring a number of the size of the modulus.
 2011-08-28, 19:49 #4 jasonp Tribal Bullet     Oct 2004 5·709 Posts Given a 256-bit integer y, the result of raising 47 to a 160-bit integer x modulo a 256-bit prime, the OP wants to be able to find x. This is actually a cryptographic size discrete log problem, and the size of the numbers involved is in the range where you pretty much have to use the discrete log version of the number field sieve. Implementations of DLP NFS are vanishingly rare, the only one I know is GDLOG, but this problem is probably far out of its range. Edit: I assume that DLP gets harder when the modulus has no special form? Last fiddled with by jasonp on 2011-08-28 at 20:05
2011-08-28, 20:02   #5
Unregistered

191 Posts

Quote:
 Originally Posted by science_man_88 the first can be performed by log(x)/log(47)
It cannot since log2(47^x) = log2(47)*160 = 5.5 * 160 > 256. So i need to calculate discrete log.

2011-08-28, 20:08   #6
Unregistered

24×271 Posts

Quote:
 Originally Posted by science_man_88 the second is capable in PARI/gp the third I can't get to work in pari gp though at least not without breaking it down more maybe.
Can you show how to do it in PARI?

2011-08-28, 20:08   #7
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

2×5×839 Posts

Quote:
 Originally Posted by Unregistered It cannot since log2(47^x) = log2(47)*160 = 5.5 * 160 > 256. So i need to calculate discrete log.
never mind I never knew what it was about , I forgot the word discrete.

 2011-08-28, 20:28 #8 jasonp Tribal Bullet     Oct 2004 5×709 Posts Actually, the GDLOG readme gives examples of 100-digit discrete log problems it has solved, so it should only take a few days for your problem. I've been toying with moving msieve into the DLP domain, though I currently have no idea of what it would entail. The CADO-NFS developers also have plans to modify their software to handle DLPs; they specifically mention adding in the ability to use basic-sounding things like double-large-primes, which makes me think there's a lot of low-hanging fruit to be gathered unless the DLP domain is so strange that basic-sounding factorization techniques don't apply.
 2011-08-28, 21:12 #9 Unregistered   23×997 Posts Can someone please give detailed manual how to calculate discrete log to a case given in OP post?
2011-08-29, 11:26   #10
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

164508 Posts

Quote:
 Originally Posted by jasonp Actually, the GDLOG readme gives examples of 100-digit discrete log problems it has solved, so it should only take a few days for your problem. I've been toying with moving msieve into the DLP domain, though I currently have no idea of what it would entail. The CADO-NFS developers also have plans to modify their software to handle DLPs; they specifically mention adding in the ability to use basic-sounding things like double-large-primes, which makes me think there's a lot of low-hanging fruit to be gathered unless the DLP domain is so strange that basic-sounding factorization techniques don't apply.
Coping with the linear algebra is a lot more difficult... One must solve
the matrix modulo the order of the group rather than over Z/2Z.

2011-08-29, 11:28   #11
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

23×3×311 Posts

Quote:
 Originally Posted by Unregistered Can someone please give detailed manual how to calculate discrete log to a case given in OP post?
Not in this venue. A description of the calculations would take many
pages. They are very complicated.

Repeat after me:

 Similar Threads Thread Thread Starter Forum Replies Last Post pinnn Information & Answers 43 2021-03-18 15:40 xkyve Information & Answers 38 2014-07-14 15:59 vector Miscellaneous Math 3 2007-11-20 18:50 Coffenator Information & Answers 16 2007-10-03 21:01 Unregistered Information & Answers 0 2006-08-27 15:32

All times are UTC. The time now is 22:44.

Mon Aug 8 22:44:09 UTC 2022 up 32 days, 17:31, 1 user, load averages: 1.45, 1.28, 1.31