Luigi Auriemma

aluigi.org (ARCHIVE-ONLY FORUM!)
It is currently 19 Jul 2012 12:32

All times are UTC [ DST ]





Forum locked This topic is locked, you cannot edit posts or make further replies.  [ 4 posts ] 
Author Message
 Post subject: exptmod
PostPosted: 10 May 2010 02:56 

Joined: 10 May 2010 02:25
Posts: 2
Not sure if anyone here can help, but I was directed here by a friend.

Using a large number library, I'm using a function called mp_exptmod (Currently using LibTomMath)
What this does is a calculation such as, (a ** b) % c = d

I'm attempting to try a reversal of this somehow, and have no idea where to start (math isn't really my strong point lol)
I have two samples,
(3989164954469923270136 ** 7922973163614769257511) % 12090425874644131058489 = 19749455703201550423
(1343852261239897004666 ** 7922973163614769257511) % 12090425874644131058489 = 22838020368551383127

And one I'm trying to reverse:
(??? ** 7922973163614769257511) % 12090425874644131058489 = 19155424029236793431

Can anyone here give me any idea as to an efficient method to generate a list of values that the first value could be to get that answer?
There's a maximum value of 37778931862957161709567 that I know of. And trying 0 - 37778931862957161709567 would be unrealistic to calculate...

Thanks in advance for any suggestions/ideas.


Top
 Profile  
 
 
 Post subject: Re: exptmod
PostPosted: 10 May 2010 08:54 

Joined: 13 Aug 2007 21:44
Posts: 4068
Location: http://aluigi.org
I guess that the "**" operator should be the power instruction, anyway the problem is the "%" one because divisions and (moreover) modulus cut parts of the original number that so can't be recovered.

it's like having "100%3=1" and trying to recover 100 from the other 2 known numbers... impossible.

math is not my best field (ih ih ih) anyway I bet on the "impossible direct reversing" option.


Top
 Profile  
 
 Post subject: Re: exptmod
PostPosted: 13 May 2010 05:38 

Joined: 10 May 2010 02:25
Posts: 2
Thanks for the response.

I understand how the math works, I just have no idea on reverse operations.

In "100%3=1", the 100 really isn't that important to me. I'd be fine with 1, 4, 7, anything. I don't need the exact, I'm just looking for anything that gives the expected result.
If you have any ideas, I'd love to hear them.

Thanks again for your time, I know this seems pretty useless, but it's mostly curiosity that won't let me ignore it lol


Top
 Profile  
 
 Post subject: Re: exptmod
PostPosted: 13 May 2010 10:52 

Joined: 13 Aug 2007 21:44
Posts: 4068
Location: http://aluigi.org
in this case the operation you must do is the radix but yeah it's totally useless here because it will return ever a 0 due to the truncation of the original result with modulus:
result = 19155424029236793431 radix 7922973163614769257511


Top
 Profile  
 
Display posts from previous:  Sort by  
Forum locked This topic is locked, you cannot edit posts or make further replies.  [ 4 posts ] 

All times are UTC [ DST ]


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
cron