20110828, 18:57  #1 
2^{2}×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? 
20110828, 19:20  #2  
"Forget I exist"
Jul 2009
Dumbassville
20306_{8} Posts 
Quote:


20110828, 19:42  #3 
(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^1271 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.

20110828, 19:49  #4 
Tribal Bullet
Oct 2004
5·709 Posts 
Given a 256bit integer y, the result of raising 47 to a 160bit integer x modulo a 256bit 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 20110828 at 20:05 
20110828, 20:02  #5 
191 Posts 

20110828, 20:08  #7 
"Forget I exist"
Jul 2009
Dumbassville
2×5×839 Posts 

20110828, 20:28  #8 
Tribal Bullet
Oct 2004
5×709 Posts 
Actually, the GDLOG readme gives examples of 100digit 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 CADONFS developers also have plans to modify their software to handle DLPs; they specifically mention adding in the ability to use basicsounding things like doublelargeprimes, which makes me think there's a lot of lowhanging fruit to be gathered unless the DLP domain is so strange that basicsounding factorization techniques don't apply. 
20110828, 21:12  #9 
2^{3}×997 Posts 
Can someone please give detailed manual how to calculate discrete log to a case given in OP post?

20110829, 11:26  #10  
"Bob Silverman"
Nov 2003
North of Boston
16450_{8} Posts 
Quote:
the matrix modulo the order of the group rather than over Z/2Z. 

20110829, 11:28  #11 
"Bob Silverman"
Nov 2003
North of Boston
2^{3}×3×311 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Help with discrete logarithm  pinnn  Information & Answers  43  20210318 15:40 
GDLOG discrete logarithm usage example  xkyve  Information & Answers  38  20140714 15:59 
Finding totient using discrete logarithm  vector  Miscellaneous Math  3  20071120 18:50 
Solving discrete logarithm in 2 variables  Coffenator  Information & Answers  16  20071003 21:01 
Discrete logarithm mod Mersenne primes?  Unregistered  Information & Answers  0  20060827 15:32 