有限域上的逆元求解

有限域上的逆元求解

这个模运算之前没有看懂，学习相关数论知识之后，理解了有限域的基本四则运算。

有限域F(p)上元素g的逆元g^-1，两者关系有：g * g^-1 mod p  = 1，所以上面的运算：

4/13 = 4*13^-1 = 4*16 = 6464 mod 23 = 18

下面代码实现了有限域 F(p)中a的逆元计算，很简单的穷举法，没有使用扩展欧几里得算法，原理就是有限域上F(p)的所有元素必定在0-p内。

a, p两个数互质，(如13，23)，如a=1/4，它的逆元为6，6 * 4 mod 23 = 1。

#include using namespace std;typedef long long LL;LL getInverseElement(LL a, LL p) { for (int i = 1; i < p; i++) { LL num = i * a; if (num % p == 1) { return i; } }}int main() { LL a, p; while (cin >> a) { cin >> p; LL ans = getInverseElement(a, p); cout << ans << endl; } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。