mersenneforum.org  

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

Reply
 
Thread Tools
Old 2017-11-03, 07:02   #1
pinnn
 
Nov 2017

1016 Posts
Default Help with discrete logarithm

Hi all!

I try to solve reversing chanllenge.
I understand algo:
2^x mod 1000000000000000000000000000000000000000000 = 7642587499893475369658291795841

So I have to find x. I read some papers about discrete logarithm but can't found any suitable solution.

Could you help me?
pinnn is offline   Reply With Quote
Old 2017-11-03, 07:17   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22×3×5×157 Posts
Default

Can you find any x>0 that 2x is odd? No, all of these will be even.

Can you find any even numbers A>0 and B>0 such that A mod B will be odd? of course not

Now look back at your problem... what do you see?
Batalov is offline   Reply With Quote
Old 2017-11-03, 07:36   #3
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

22×5×307 Posts
Default

I guess it is meant to be "2^x - 1 mod ..."
retina is offline   Reply With Quote
Old 2017-11-03, 08:02   #4
pinnn
 
Nov 2017

24 Posts
Default

Quote:
Originally Posted by Batalov View Post
Can you find any x>0 that 2x is odd? No, all of these will be even.

Can you find any even numbers A>0 and B>0 such that A mod B will be odd? of course not

Now look back at your problem... what do you see?
I see problem)
pinnn is offline   Reply With Quote
Old 2017-11-03, 08:22   #5
pinnn
 
Nov 2017

24 Posts
Default

That's correct:
2^x mod 1000000000000000000000000000000000000000000 = 15285174999786950739316583591682
pinnn is offline   Reply With Quote
Old 2017-11-03, 08:27   #6
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

22·5·307 Posts
Default

Quote:
Originally Posted by pinnn View Post
That's correct:
2^x mod 1000000000000000000000000000000000000000000 = 15285174999786950739316583591682
x = 103.59190401122605093391136817141...
retina is offline   Reply With Quote
Old 2017-11-03, 08:46   #7
pinnn
 
Nov 2017

1016 Posts
Default

Quote:
Originally Posted by retina View Post
x = 103.59190401122605093391136817141...
?? No solution?
pinnn is offline   Reply With Quote
Old 2017-11-03, 09:52   #8
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

7·239 Posts
Default

Quote:
Originally Posted by pinnn View Post
That's correct:
2^x mod 1000000000000000000000000000000000000000000 = 15285174999786950739316583591682
In our Number Theory discussion thread, you can learn about the Chinese Remainder Theorem:
http://www.mersenneforum.org/showthread.php?t=21692
Nick is offline   Reply With Quote
Old 2017-11-03, 10:05   #9
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

5BA16 Posts
Default

Quote:
Originally Posted by pinnn View Post
That's correct:
2^x mod 1000000000000000000000000000000000000000000 = 15285174999786950739316583591682
That has still no solution, hint: 15285174999786950739316583591682==2 mod 4.
R. Gerbicz is offline   Reply With Quote
Old 2017-11-03, 10:23   #10
pinnn
 
Nov 2017

24 Posts
Default

Quote:
Originally Posted by Nick View Post
In our Number Theory discussion thread, you can learn about the Chinese Remainder Theorem:
http://www.mersenneforum.org/showthread.php?t=21692
I know this teorem. And I try use it:
1. Factorization modulus - 1 (1000000000000000000000000000000000000000000-1) =
[ <3, 3>, <7, 2>, <11, 1>, <13, 1>, <37, 1>, <43, 1>, <127, 1>, <239, 1>, <1933,
1>, <2689, 1>, <4649, 1>, <459691, 1>, <909091, 1>, <10838689, 1> ]

2. For each factor:
2 = 15285174999786950739316583591682 ^ p mod 9
2 = 15285174999786950739316583591682 ^ q mod 49
2 = 15285174999786950739316583591682 ^ z mod 11
...

3. And use Chinese Remainder Theorem

But I stuck at 2 step. Can't find (Pohlig-Hellman) p, q ...
pinnn is offline   Reply With Quote
Old 2017-11-03, 10:40   #11
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

7·239 Posts
Default

To use the Chinese Remainder Theorem here, you work in the integers modulo \(2^{42}\) and modulo \(5^{42}\) instead of the integers modulo \(10^{42}\).
But, as R. Gerbicz pointed out, there is still a mistake in the number on the right (or no solution).
Nick is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
GDLOG discrete logarithm usage example xkyve Information & Answers 38 2014-07-14 15:59
Discrete logarithm software Unregistered Information & Answers 39 2012-04-27 20:08
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 07:30.

Sun May 9 07:30:47 UTC 2021 up 31 days, 2:11, 0 users, load averages: 3.09, 2.86, 2.73

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.