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.

Improve this question
14
  • 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
    Commented Feb 26, 2021 at 17:48
  • 2
    You've hit your head on en.wikipedia.org/wiki/Discrete_logarithm . Unless you're working with some particular cases, there is no general algorithm
    – 12345ieee
    Commented Feb 26, 2021 at 17:53
  • 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
    Commented Feb 26, 2021 at 17:56
  • 2
    @ControlCControlV "trying to get the first argument" You should 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
    Commented Feb 26, 2021 at 21:12
  • 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 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
    Commented Feb 26, 2021 at 23:01

1 Answer 1

Reset to default
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

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.