同余定理与逆元
定理
2023-09-14 09:08:53 时间
同余定理:
数论中的重要概念。给定一个正整数m,如果两个整数a和b满足a-b能够被m整除,即(a-b)/m得到一个整数,
那么就称整数a与b对模m同余,记作a≡b(mod m)。对模m同余是整数的一个等价关系。
同余的主要性质:
逆元
利用费马小定理计算逆元
费马小定理:如果p是质数(素数),并且gcd(a,p) == 1, 那么就会满足下面的式子 ,当然了,既然p已经是素数,
那么如果a < p那么就一定会满足这个式子,既然这样我们要得到 a^-1 我们就可以利用上面的式子来计算inv(a) : a^(p-2) = inv(a) (mod p)
这样我们就得到了我们需要的逆元:
long long q_pow(long long a,long long b,long long p)
{
long long res = 1;
while(b)
{
if(b&1)
{
res = (res*a)%p;
}
a = (a*a)%p;
b>>=1;
}
return res;
}
long long inverse(long long a,long long p)
{
return q_pow(a,p-2,p);
}
相关文章
- 费马小定理
- 浅谈压缩感知(十二):压缩感知与奈奎斯特采样定理
- 关于傅里叶分析与香农采样定理
- Atitit 数据安全 密码学原理与概论 1.1. 密码学方向(公钥方向)2 1.2. 古典密码主要靠算法,现代靠密钥2 1.3. 香农三大定理2 2. 古典密码2 2.1. 古典密码
- Dilworth定理
- 神经网络的万能近似定理
- 【数字信号处理】线性时不变系统 LTI “ 输入 “ 与 “ 输出 “ 之间的关系 ( 线性卷积起点定理 | 左边序列概念 | 推理 )
- BZOJ 3589 动态树 树链拆分+纳入和排除定理
- hdu 1420(Prepared for New Acmer)(中国剩余定理)(降幂法)
- 极大极小定理
- 中值定理及导数的应用 — 高等数学(未完待续...)
- 数据结构和算法 数论 中国余数定理