0

pow(a,x,c) operator in python returns (a**x)%c . If I have values of a, c, and the result of this operation, how can I find the value of x?

Additionally, this is all the information I have

pow(a,x,c) = pow(d,e,c)

Where I know the value of a,c,d, and e.

These numbers are very large (a = 814779647738427315424653119, d = 3, e = 40137673778629769409284441239, c = 1223334444555556666667777777) so I can not just compute these values directly.

I'm aware of the Carmichael's lambda function that can be used to solve for a, but I am not sure if and/or how this applies to solve for x.

Any help will be appreciated.

Henry Davinson
  • 1
  • 1
  • probably better suited for the math stack exchange site – I wrestled a bear once. Oct 09 '20 at 20:36
  • 1
    I suspect that this would be much more appropriate on https://math.stackexchange.com. It seems that python is only incidental to the problem. – Mad Physicist Oct 09 '20 at 20:38
  • To be clear, you have a^x mod c, a, and c, and want x, yes? Well, the trivial solution is to loop through all values of x, testing them. The loop will execute at most c - 1 times before a repetition, at which point you stop, due to Euler's theorem. Of course for the value of c you give this may be rather slow. However, if you reuse the same a and c over multiple calculations, you can build a sort of cache in one, slow operation and then make fast lookups afterwards. – Anonymous1847 Oct 09 '20 at 20:39
  • The solution also depends on whether you know that a and c are relatively prime. – Anonymous1847 Oct 09 '20 at 20:42
  • Additionally, if you reuse the same c but not necessarily the same a between calculations, you can build a more general cache by first finding a multiplicative generator g for the group of units mod c. Then build a cache of all the powers of g in order. Then on any calculation, given a and a^x, lookup their exponents of g in that cache and then do a modular calculation to find x. Hold on, I'm going to put this in an answer. – Anonymous1847 Oct 09 '20 at 20:46
  • 2
    This is the discrete logarithm problem. It's one of the very hard problems modern cryptography relies on, and it is, again, very hard. You're not going to break it. – user2357112 Oct 09 '20 at 20:47
  • @user2357112 Ah yes, I thought this might be an NP-complete problem, but I forgot the name. – Anonymous1847 Oct 09 '20 at 20:48
  • This not quite the discrete logarithm problem because there is some extra information provided. I don't see how to take advantage of it, but perhaps someone smarter than me can. I note that `c` is chosen to put this just at the upper bound of a typical person's computing resources and patience using the relatively simple O(sqrt(c)) algorithms, so that at suggests there's a shortcut. Out of curiousity, what is the value of `a`? – President James K. Polk Oct 10 '20 at 00:17
  • 1
    a = 814779647738427315424653119 – Henry Davinson Oct 10 '20 at 00:50
  • see [Inverse modpow](https://stackoverflow.com/a/58622692/2521214) – Spektre Oct 10 '20 at 08:53

1 Answers1

0

As @user2357112 says in the comments, this is the discrete logarithm problem, which is computationally very difficult for large c, and no fast general solution is known.

However, for small c there are still some things you can do. Given that a and c are coprime, there is an exponent k < c such that a^k = 1 mod c, after which the powers repeat. Let b = a^x. So, if you brute force it by calculating all powers of a until you get b, you'll have to loop at most c times:

def do_log(a, b, c):
    x = 1
    p = a
    while p != b and p != 1:
        x += 1
        p *= a
        p %= c
    if p == b:
        return x
    else:
        return None # no such x

If you run this calculation multiple times with the same a, you can do even better.

# a, c constant
p_to_x = {1: 0}
x = 1
p = a
while p != 1:
    p_to_x[p] = x
    x += 1
    p *= a
    p %= c

def do_log_a_c(b):
    return p_to_x[b]

Here a cache is made in a loop running at most c times and the cache is accessed in the log function.

Anonymous1847
  • 2,568
  • 10
  • 16