Hello. I return the number to the power modulo:

(x ^ y) mod N = z

I know y , N , z . How to find x ?

  • This is a question about number theory, not about programming. Well, I think that since the question is about cryptography, there is a chance that the task is not solved much faster than the search. - VladD
  • @pavel: How will the primitive root help? Moreover, it does not exist on any module. - VladD
  • @VladD yes you are right, I gave the basic link. I did not notice that there is such an article e-maxx.ru/algo/discrete_root . Well, cryptography usually works for the logarithm of the number (the number of digits for example) and considers it slow, it is not a brute force head start. - pavel
  • @pavel: Yeah, the article says what the primitive root rolls. But still, it's only for a simple module. For arbitrary, there still must be investigated solvability. I'm afraid this is a good piece of number theory. - VladD
  • one
    @pavel: Yeah, right! But there is more likely not to cross, and the Chinese theorem on residuals. - VladD

1 answer 1

  1. Compound N can be factorized and reduced to the original comparison to a system of comparisons with respect to relatively simple modules - powers of primes.
  2. The decision of each of these comparisons is reduced to the decision of several comparisons on a simple basis.
  3. The solution of comparisons on a simple basis is considered in the article at the link OP. The degree of such a comparison can be reduced with the help of the small Fermat theorem.
  4. Knowing the classes of the required number by mutually simple modules, it is easy to reconstruct the class of this number from their product, that is, from the base of N.

Details on paragraphs. 1, 2, 4 - in the book by I. M. Vinogradov , ch. Iv.