模p运算
给定一个正整数p,任意一个整数n,一定存在等式
n = kp + r
其中k、r是整数,且 0 ≤ r < p,称呼k为n除以p的商,r为n除以p的余数。
对于正整数p和整数a,b,定义如下运算:
- 取模运算:a mod p 表示a除以p的余数。
- 模p加法:(a + b) mod p ,其结果是a+b算术和除以p的余数,也就是说,(a+b) = kp +r,则 (a+b) mod p = r。
- 模p减法:(a-b) mod p ,其结果是a-b算术差除以p的余数。
- 模p乘法:(a × b) mod p,其结果是 a × b算术乘法除以p的余数。
可以发现,模p运算和普通的四则运算有很多类似的规律,如:
规律
公式
结合率 |
((a+b) mod p + c)mod p = (a + (b+c) mod p) mod p ((a*b) mod p * c)mod p = (a * (b*c) mod p) mod p |
交换率 |
(a + b) mod p = (b+a) mod p (a × b) mod p = (b × a) mod p |
分配率 |
((a +b)mod p × c) mod p = ((a × c) mod p + (b × c) mod p) mod p |
简单的证明其中第一个公式:
((a+b) mod p + c) mod p = (a + (b+c) mod p) mod p
假设
a = k1 p + r1 b = k2 p + r2 c = k3 p + r3
a+b = (k1 + k2) p + (r1 + r2)
如果(r1 + r2) >= p ,则
(a+b) mod p = (r1 + r2) -p
否则
(a+b) mod p = (r1 + r2)
再和c进行模p和运算,得到
结果为 r1 + r2 + r3的算术和除以p的余数。
对右侧进行计算可以得到同样的结果,得证。
模p相等
如果两个数a、b满足a mod p = b mod p,则称他们模p相等,记做
a ≡ b mod p
可以证明,此时a、b满足 a = kp + b,其中k是某个整数。
对于模p相等和模p乘法来说,有一个和四则运算中迥然不同得规则。在四则运算中,如果c是一个非0整数,则
ac = bc 可以得出 a =b
但是在模p运算中,这种关系不存在,例如:
(3 x 3) mod 9 = 0
(6 x 3) mod 9 = 0
但是
3 mod 9 = 3
6 mod 9 =6
定理(消去律):如果gcd(c,p) = 1 ,则 ac ≡ bc mod p 可以推出 a ≡ b mod p
证明:
因为ac ≡ bc mod p
所以ac = bc + kp,也就是c(a-b) = kp
因为c和p没有除1以外的公因子,因此上式要成立必须满足下面两个条件中的一个
1) c能整除k
2) a = b
如果2不成立,则c|kp
因为c和p没有公因子,因此显然c|k,所以k = ck'
因此c(a-b)kp可以表示为c(a-b) =ck'p
因此a-b = k'p,得出a ≡ b mod p
如果a = b,则a ≡ b mod p 显然成立
得证
欧拉函数
欧拉函数是数论中很重要的一个函数,欧拉函数是指:对于一个正整数n,小于n且和n互质的正整数的个数,记做:φ(n),其中φ(1)被定义为1,但是并没有任何实质的意义。
定义小于n且和n互质的数构成的集合为Zn,称呼这个集合为n的完全余数集合。
显然,对于素数p,φ(p)= p -1.对于两个素数p、q,他们的乘积n = pq 满足φ(n) =(p-1)(q-1)
证明:对于质数p,q,满足φ(n) =(p-1)(q-1)
考虑n的完全余数集Zn = { 1,2,....,pq -1}
而不和n互质的集合由下面三个集合的并构成:
1) 能够被p整除的集合{p,2p,3p,....,(q-1)p} 共计q-1个
2) 能够被q整除的集合{q,2q,3q,....,(p-1)q} 共计p-1个
3) {0}
很显然,1、2集合中没有共同的元素,因此Zn中元素个数 = pq - (p-1 + q- 1 + 1) = (p-1)(q-1)
欧拉定理
对于互质的整数a和n,有aφ(n) ≡ 1 mod n
证明:
首先证明下面这个命题:
对于集合Zn={x1,x2,...,xφ(n)},考虑集合
S = {ax1 mod n,ax2mod n,...,axφ(n)mod n}
则S = Zn
1) 由于a,n互质,xi也与n互质,则axi也一定于p互质,因此
任意xi,axi mod n 必然是Zn的一个元素
2) 对于Zn中两个元素xi和xj,如果xi ≠ xj 则axi mod n ≠ axi mod n,这个由a、p互质和消去律可以得出。
所以,很明显,S=Zn
既然这样,那么
(ax1 × ax2×...×axφ(n))mod n
= (ax1 mod n × ax2mod n × ... × axφ(n)mod n)mod n
= (x1 × x2 × ... × xφ(n))mod n
考虑上面等式左边和右边
左边等于(aφ(n) × (x1 × x2 × ... × xφ(n))mod n) mod n
右边等于x1 × x2 × ... × xφ(n))mod n
而x1 × x2 × ... × xφ(n))mod n和p互质
根据消去律,可以从等式两边约去,就得到:
aφ(n) ≡ 1 mod n
推论:对于互质的数a、n,满足aφ(n)+1 ≡ a mod n
费马定理
a是不能被质数p整除的正整数,则有ap-1 ≡ 1 mod p
证明这个定理非常简单,由于φ(p) = p-1,代入欧拉定理即可证明。
同样有推论:对于不能被质数p整除的正整数a,有ap ≡ a mod p
分享到:
相关推荐
RSA算法中求模乘运算的结果 void modular exponentitation int x int r int p int t { int a b c; a x;b r;c t; if b 0 如果b为零 则结果等于1 { printf "%d" c ; 输出结果 return; } if b>0 ...
压缩包内的“15_number_mod”文件可能包含了整个设计的源代码,包括顶层模块、计数器模块、MOD运算模块以及数码管驱动模块等。为了理解整个设计,我们需要打开这个文件查看具体的Verilog代码。 在设计中,计数器...
用链表实现,界面用MFC设计,可实现多项式四则运算,可以参考
在数学中,MOD运算是取模运算,它返回两个数相除后的余数。这个运算符通常用于检查一个数是否能够被另一个数整除,或者在处理循环逻辑时,如判断日期的星期几。在等式`a mod b = c`中,a是被除数,b是除数,c是余数...
在工业自动化中,取余数MOD运算有很多实际的应用场景。例如: 1. **周期性任务**:通过计算时间间隔或计数器的模值,可以实现周期性的动作执行,比如每隔一定次数执行一次特定操作。 2. **分组或分类**:在生产线中...
标题中的“sushu.rar_MOD_site:www.pudn.com”可能是指在PUDN(一个分享编程资源的网站)上发布的关于MOD运算的一个源码压缩包,其中“MOD”通常指的是数学运算中的模运算,即求余数。在编程中,MOD函数用于计算两数...
#### 三、Mod运算的性质 ##### 1. 加减法 - **公式**:`(M + N) mod q = ((M mod q) + (N mod q)) mod q` - **解释**:若已知`M mod q` 和 `N mod q`,则可以直接计算出 `(M + N) mod q` 的值。 - **示例**:假设`...
加密过程是将明文m(小于n)通过指数运算进行加密,公式为:C = m^e (mod n)。解密则是将密文C通过私钥d进行指数运算,还原出明文,公式为:M = C^d (mod n)。由于指数运算的性质,这两个过程可以相互逆推,但如果...
- **mod运算**:同div运算符一起使用,返回除法的余数。 运算优先级是决定计算顺序的关键。根据描述,乘法、除法、整除和取余运算(*、/、div、mod)的优先级高于加法和减法(+、-)。 在Pascal中,变量是用来存储...
5. **逆运算**:逆运算通常指的是求解x关于模n的逆元,即找到一个y使得x * y ≡ 1 (mod n)。在密码学中,模逆元在RSA算法中尤为重要,因为公钥和私钥的生成就依赖于求解大数的模逆。 **RsaKit.exe** 是一个可能的...
表达式`4 + 56 * 7 / 8 Mod 9`会先执行除法和乘法,再执行Mod运算,结果是5,所以答案是D。 IIf函数是一个三元条件表达式,如`x = IIf(a > 5, -1, 0)`,当a大于5时,x的值为-1,否则为0。如果a=6,x的值将是-1,...
3. **mod运算的优化**:模运算在RSA中频繁进行,为了提高效率,可以使用Karatsuba算法或更高级的快速幂算法来加速乘法,结合模运算,优化整体性能。 通过以上步骤,我们可以理解并实现RSA加密算法,它在实际应用中...
如果运算元包含小数,VB会先将其四舍五入为整数,然后执行Mod运算。 VB中的`^`运算符表示次方,例如`2^3`表示2的3次方,结果是8。乘法运算符`*`用于两个数的乘法,例如`4 * 7`将得到28。 程序的基本单元是表单...
6. **求模运算**:对级数之和进行整数求余函数MOD运算,即MOD(C(17), 31),得到一个余数值。 7. **求校验码**:校验码18C为31减去上一步得到的余数,即18C = 31 - MOD(C(17), 31)。 8. **确认校验码**:最后,校验...
4. 第四题要求画出求商和余数的流程图,需要用到Mod运算和整除运算,以及变量的赋值。 5. 第五题未提供具体流程图,因此无法直接确定xy的值。 6. 第六题是设计一个安全渡河的算法,需要考虑如何控制老虎和牛的数量,...
得力-D991CN函数计算器说明书
取模运算,即求余数,通常表示为a mod b,返回的是a除以b的余数。在数字电路设计中,取模运算对于各种应用如计数器、除法器以及密码学等都是至关重要的。Cordic算法通过迭代方式,逐次调整输入向量,直到达到期望的...
12. 表达式3*2\5 Mod 3的结果是1,因为整数除法优先于Mod运算。 13. 不合法的VB变量名是D)andif,因为它包含了VB的保留字。 14. 错误的数组定义语句是C) Dim d (-10),因为数组索引不能为负数。 15. 当x=10时,y=...
4. 函数mod运算:在数学中,`mod`函数表示取余运算,`mod(23,-5)`的结果是-2,因为23除以-5的余数是-2。 5. 触发器:在数据库中,触发器是一种特殊的存储过程,当对数据库表进行特定操作(如INSERT、UPDATE或DELETE...
传统的分库分表策略通常采用mod运算或基于时间的分片方式,如按星期或月份分库。这些方法虽然简单,但在扩容时需要进行数据迁移,因为原有的数据分布不再适应新的分片规则。例如,从3个分片扩展到5个时,原有的mod3...