0

I've been looking everywhere for a solution, but I found nothing. how would I invert something like this? pow(4, 4, 91). pow(4, 4, 91) returns 74.

and I'm trying to get 4 from the number 74

I've tried using gmpy, yet no luck. (I'm probably going to get some answers that include brute force, and brute forcing is the last thing I want to do)

To clarify, I want to solve for x in the equation y = xa mod N, where y, a, and N are all known.

President James K. Polk
  • 40,516
  • 21
  • 95
  • 125
Control C Control V
  • 29
  • 8
  • 5
    I don't think you can invert `pow()` when you use the modulus argument, because there's no unique values that produce the result. – Barmar Feb 26 '21 at 17:48
  • @Barmar Oh, I wasn't aware of that when I asked this question. Are you 100% sure that theres absolutely no way to invert it? – Control C Control V Feb 26 '21 at 17:53
  • 2
    You've hit your head on https://en.wikipedia.org/wiki/Discrete_logarithm . Unless you're working with some particular cases, there is no general algorithm – 12345ieee Feb 26 '21 at 17:53
  • just so - you have discovered some roots of cryptography – ti7 Feb 26 '21 at 17:54
  • oh, couldn't I do something with a lookup table? (I don't know what a lookup table is, someone just told me I should look into them) – Control C Control V Feb 26 '21 at 17:55
  • You _might_ be able to if you have a known and finite number of inputs, but not for the general case ; a lookup table is broadly checking a table before attempting a computation to "look up" the result (this is often very efficient in the case of, say, a web request where you're not limited by computation, but some massive outside latency) – ti7 Feb 26 '21 at 17:56
  • 2
    Are you trying to get the first argument or the second argument? It's hard to tell since you have the same value 4 for both. – Barmar Feb 26 '21 at 17:56
  • Or is it always the case that you're doing `pow(x, x, y)`? – Barmar Feb 26 '21 at 17:56
  • Oh, im trying to get the first argument. @Barmar. And no, its not always the case that ill do that – Control C Control V Feb 26 '21 at 17:58
  • 2
    @ControlCControlV "*trying to get the first argument*" You should [edit](https://stackoverflow.com/posts/66390530/edit) the question and clarify that. To solve for the first argument, you are looking for a modular Nth root. To solve for the second argument, you are looking for a discrete logarithm. The two are entirely different problems. – dxiv Feb 26 '21 at 21:12
  • sorry, I didn't realize it would be unclear when I asked the question – Control C Control V Feb 26 '21 at 21:32
  • 1
    I have edited the question per the comments. As @dxiv noted, this is not the discrete logarithm problem but rather the modular root problem. Nevertheless, this problem is only "easy" when the complete factorization of the modulus is available. You can perform the algorithm outline in [this paper](https://arxiv.org/pdf/1111.4877.pdf) mod each of the prime powers in the factorization, then combine them using the Chinese Remainder Theorem. As you can see if you read the paper it's quite tedious. – President James K. Polk Feb 26 '21 at 23:01
  • Thank you for editing the question. I will be sure to read that paper. – Control C Control V Feb 26 '21 at 23:18
  • see this duplicate: [Modular Inverse Calculation](https://stackoverflow.com/a/58622692/2521214) – Spektre Feb 27 '21 at 08:01

1 Answers1

4

Because you're using modulus argument, you can't get the exact same values from before, since there is not only one answer. For example pow(2, 3, 5) == pow(2, 7, 5). In this case should you get 3, or 5? The answer isn't clear at all. This is why what you want to achieve is not really possible. It may be possible if you add additional constraints

Galunid
  • 578
  • 6
  • 14