mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2011-08-28, 18:57   #1
Unregistered
 

4,003 Posts
Default 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?
  Reply With Quote
Old 2011-08-28, 19:20   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by Unregistered View Post
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.
science_man_88 is offline   Reply With Quote
Old 2011-08-28, 19:42   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

18E916 Posts
Default

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.
fivemack is offline   Reply With Quote
Old 2011-08-28, 19:49   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·3·19·31 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2011-08-28, 20:02   #5
Unregistered
 

161778 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
  Reply With Quote
Old 2011-08-28, 20:08   #6
Unregistered
 

3·13·233 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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?
  Reply With Quote
Old 2011-08-28, 20:08   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by Unregistered View Post
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.
science_man_88 is offline   Reply With Quote
Old 2011-08-28, 20:28   #8
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×3×19×31 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2011-08-28, 21:12   #9
Unregistered
 

7·97 Posts
Default

Can someone please give detailed manual how to calculate discrete log to a case given in OP post?
  Reply With Quote
Old 2011-08-29, 11:26   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-08-29, 11:28   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by Unregistered View Post
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:

Google is my friend.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Help with discrete logarithm pinnn Information & Answers 32 2017-11-08 00:08
GDLOG discrete logarithm usage example xkyve Information & Answers 38 2014-07-14 15:59
Finding totient using discrete logarithm vector Miscellaneous Math 3 2007-11-20 18:50
Solving discrete logarithm in 2 variables Coffenator Information & Answers 16 2007-10-03 21:01
Discrete logarithm mod Mersenne primes? Unregistered Information & Answers 0 2006-08-27 15:32

All times are UTC. The time now is 18:30.

Sun Jan 17 18:30:34 UTC 2021 up 45 days, 14:41, 0 users, load averages: 1.19, 1.67, 1.85

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.