J. Doe Asked:2020-12-13 06:43:44 +0000 UTC2020-12-13 06:43:44 +0000 UTC 2020-12-13 06:43:44 +0000 UTC 如何快速找到比较 x^p0 = 1 (mod p) 的至少一种解决方案？ 772 有一个同余a^p0 = 1 (mod p)，其中p0和p已知是大素数。 您需要以编程方式查找任何a > 1. 一个简单的枚举a需要很长时间。有没有更快的方法来找到至少一种解决方案？ сравнение 1 个回答 Voted Best Answer J. Doe 2020-12-13T18:33:11Z2020-12-13T18:33:11Z 找到了答案。 您需要从 (1; p - 1) 中选择一个随机 h。 然后以足够高的概率 x = h^[(p-1)/p0] mod p 将符合条件 x^p0 = 1 (mod p)。
找到了答案。
您需要从 (1; p - 1) 中选择一个随机 h。
然后以足够高的概率 x = h^[(p-1)/p0] mod p 将符合条件 x^p0 = 1 (mod p)。