模块化算术 - 证明或反驳计算

Question

大家好我是计算机专业的学生，​​正在自学算法课

在课程中我看到了这个问题： 我认为这是一个简单的问题，但我无法理解

证明或反驳：5^{3001} = 12^{301} (mod 31)$

我的解决方案是从 (5 和 12) 开始，重复平方模 31。

我的解决方案：

5^{3001} = 12^{301} (mod 31) =
5*5^{3000} = 12*12^{300} (mod 31) =
5*125^{2998} = 12*6^{300}*2^{300} (mod 31) = 
5*1^{2998} = 12*36^{299}*32^{296} (mod 31) = 
5 = 12*36^{299}*32^{296} (mod 31) = 
5 = 12*5^{299}*1^{296} (mod 31) = 
5 = 12*125^{297}*1 (mod 31) = 
5 = 12*1^{297}*1 (mod 31) = 
5 = 12

我就是这样做的，我认为这样做是不对的，还有其他方法可以证明或反驳这种说法吗？

Answer 1

平方取幂当然可行，这样做没问题，但看起来工作量很大，您可以使用快捷方式：a³⁰ ≡ 1 mod 31 if gcd(a, 31) = 1 (欧拉定理).

5³⁰⁰¹ ≡ 5 * (5³⁰)¹⁰⁰ ≡ 5 * 1¹⁰⁰ ≡ 5 mod 31

12³⁰¹ ≡ 12 * (12³⁰)¹⁰ ≡ 12 * 1¹⁰ ≡ 12mod 31

指数 3001 和 301（结合 modulus, 31）看起来像是专门选择它们来实现基于欧拉定理的方法。对于大多数 可以 选择的任意数字，这种方法就不会那么好。