0

Let a and b are the known Big Integers [Each of length 308]. I want to find the big integer x in the equation a^x = b using Java

Mathematically, By taking log on both sides of the above equation, I can simplify it as follows.

x · log2(a) = log2(b)

The above-simplified equation can be programmed. But Math.log is supported only for double values and not for Big Integers. So am looking for any alternate functions to compute this.

How to compute the value of Big Integer x. Any help will be appreciated.

codeX
  • 4,842
  • 2
  • 31
  • 36
  • I'm guessing this is homework and the point of the assignment is to have you implement an iterative algorithm that starts with a rough guess `g` for `x`, computes `a^g`, then adjusts `g` based on the result, iterating until `g` converges to `x` itself. – Gene Jan 01 '20 at 01:35
  • @smac89 Thanks for sharing the link. As per the link, the built-in functions can support only till double range. I was trying to explore any built-in support to support even a bigger range. Still thank you so much! – codeX Jan 01 '20 at 01:42
  • @Gene Thanks for the suggestion . Actually this is a part of my work involving ElGamal attack, so here my g is really very big for trial and error. – codeX Jan 01 '20 at 01:44
  • If the integer is not prime, you can break it down to it's prime factors and then the log of the number will be the sum of the logs of its prime factors. – smac89 Jan 01 '20 at 02:14
  • @arunprakashpj: Your integer problem is only superficially related to El Gamal. – President James K. Polk Jan 01 '20 at 16:07
  • Unfortunately the link listed as a duplicate is, in fact, not a duplicate, so I'm reopening. It's solving a different problem, namely a double approximation to the logarithm. However, you can solve this problem yourself by using general root-finding algorithms, the simplest of which is the [bisection method](https://en.wikipedia.org/wiki/Bisection_method) applied to a^x - b == 0. You will have to adapt it to work on integers only. – President James K. Polk Jan 01 '20 at 16:15
  • 1
    Do you expect an exact result? In general there is nothing in that equation to guarantee that x will be an integer. If x is so big that a double with its 53 bits mantissa isn't enough, then you'd need at least 2^53 bits = 1 pebibyte to store the right hand side b. This feels like it's unlikely to be of practical relevance. Are we missing some detail here? – MvG Jan 01 '20 at 17:22
  • 1
    FYI: Actually, In my EIGamal, I am equating g^x == y where y is the public key. Here g and y are of length 308. As g and y values are very long , am trying to find a way to compute x – codeX Jan 01 '20 at 21:57
  • 1
    If both g and y are 308 bit (?) long without counting leading zeros, then x is 1. Even the second power (square) of a 308 bit number has around 616 bit. If this is related to ElGamal, then chances are your equation only holds modulo some other integer, which is a *crucial* part of the setup. With that your question would essentially amount to asking about a way to compute the [discrete logarithm](https://en.wikipedia.org/wiki/Discrete_logarithm). Computing that efficiently is assumed to be hard, and a lot of public key cryptography depends on that assumption. – MvG Jan 02 '20 at 00:48
  • 1
    If a and b are only 308 bits, then bisection as @JamesReinstateMonicaPolk, which is the "trial and error" I was thinking of, refines the guess by at least one bit per iteration, which will be very reasonably fast for many applications. I'd think a few 10s of millis. A good starting guess is log2(b)/log2(a) where logs are approximated by number of bits. – Gene Jan 02 '20 at 04:10
  • Do a search on `java bigdecimal math library`. Apparently there are some popular libraries out there that might help you. – WJS Jan 03 '20 at 17:23
  • Compared a ^x == b and solved the query by looping the possible values for x. As its a weak random generator, I cracked it! Thanks, everyone for your valuable comments! – codeX Jan 04 '20 at 00:48

0 Answers0