To Solve the High Degree Congruence

摘要

In this paper, the authors derive a new sufficient and necessary condition for the high degree congruence x n a (mod p) to have solutions from a known discriminant. Put forward the definition of the trivial solution to the congruence, elaborate two methods of computing the trivial solution in deterministic polynomial time, argue that non-trivial solutions to the congruence can not be obtained cyclically from the trivial solution, and infer the two new methods of seeking the trivial solution. The paper analyzes the time complexity of a probabilistic algorithm for random solutions to the congruence without especially large p and n, and gives the discrete logarithm time algorithm for non-trivial solutions to the congruence with especially large p or n. Therefore, the paper discusses roundly the way how to seek solutions to the congruence x n a (mod p), which is helpful to designing new public-key cryptosystems.