mersenneforum.org Help with discrete logarithm
 Register FAQ Search Today's Posts Mark Forums Read

 2017-11-03, 07:02 #1 pinnn   Nov 2017 1016 Posts 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?
 2017-11-03, 07:17 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 22×3×5×157 Posts 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?
 2017-11-03, 07:36 #3 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 22×5×307 Posts I guess it is meant to be "2^x - 1 mod ..."
2017-11-03, 08:02   #4
pinnn

Nov 2017

24 Posts

Quote:
 Originally Posted by Batalov 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)

 2017-11-03, 08:22 #5 pinnn   Nov 2017 24 Posts That's correct: 2^x mod 1000000000000000000000000000000000000000000 = 15285174999786950739316583591682
2017-11-03, 08:27   #6
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

22·5·307 Posts

Quote:
 Originally Posted by pinnn That's correct: 2^x mod 1000000000000000000000000000000000000000000 = 15285174999786950739316583591682
x = 103.59190401122605093391136817141...

2017-11-03, 08:46   #7
pinnn

Nov 2017

1016 Posts

Quote:
 Originally Posted by retina x = 103.59190401122605093391136817141...
?? No solution?

2017-11-03, 09:52   #8
Nick

Dec 2012
The Netherlands

7·239 Posts

Quote:
 Originally Posted by pinnn That's correct: 2^x mod 1000000000000000000000000000000000000000000 = 15285174999786950739316583591682
In our Number Theory discussion thread, you can learn about the Chinese Remainder Theorem:

2017-11-03, 10:05   #9
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

5BA16 Posts

Quote:
 Originally Posted by pinnn That's correct: 2^x mod 1000000000000000000000000000000000000000000 = 15285174999786950739316583591682
That has still no solution, hint: 15285174999786950739316583591682==2 mod 4.

2017-11-03, 10:23   #10
pinnn

Nov 2017

24 Posts

Quote:
 Originally Posted by Nick 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 ...

 2017-11-03, 10:40 #11 Nick     Dec 2012 The Netherlands 7·239 Posts 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).

 Similar Threads Thread Thread Starter Forum Replies Last Post xkyve Information & Answers 38 2014-07-14 15:59 Unregistered Information & Answers 39 2012-04-27 20:08 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 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