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

 2011-08-28, 18:57 #1 Unregistered   24·11·19 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

26×131 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 13×491 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 24×13×17 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

100011001110012 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

22×1,303 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

203008 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 24·13·17 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   2×3,877 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

Nov 2003

22×5×373 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

Nov 2003

22×5×373 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 23:17.

Thu Apr 15 23:17:20 UTC 2021 up 7 days, 17:58, 1 user, load averages: 1.48, 1.82, 1.94