CINTA作业三:同余、模指数、费尔马小定理、欧拉定理
发布日期:2022-03-08 21:50:34 浏览次数:2 分类:技术文章

本文共 2095 字,大约阅读时间需要 6 分钟。

文章目录


一、同余

1.求解乘法逆元

要求:实现求乘法逆元的函数,给定a和m,求a模m的乘法逆元,无解时给出无解提示,并且只返回正整数,进而给出求解同余方程(ax=b mod m)的函数,即给定a,b,m,输出满足方程的x,无解给出无解提示。

#include
int egcd(int c,int m){
int b=m; int r1=1,s1=0;//1*c+0*m=c int r2=0,s2=1;//0*c+1*m=m int r=0,t=0,p=0; //r是余数,t是商 r=c%m; while(r!=0) {
t=c/m; c=m; m=r;//gcd p=r2; r2=r1-t*r2; r1=p; r=c%m; }//等式右端辗转相除法 if(m!=1)return -1;//如果gcd(c,m)!=1,返回-1 if(r2>0)return r2; else return b+r2; }int main(){
int c,m; scanf("%d %d",&c,&m); if(egcd(c,m)==-1) printf("%d在%d条件下不存在乘法逆元\n",c,m); else printf("%d在%d条件下的乘法逆元是%d\n",c,m,egcd(c,m));}

2.求解同余方程

#include
int congruence(int a,int b,int m){
int w=m; int r1=1,s1=0;//1*c+0*m=c int r2=0,s2=1;//0*c+1*m=m int r=0,t=0,p=0; //r是余数,t是商 r=a%m; while(r!=0) {
t=a/m; a=m; m=r;//gcd p=r2; r2=r1-t*r2; r1=p; r=a%m; }//等式右端辗转相除法 if(b/m*m
0)return r2*(b/m); else return (w+r2)*(b/m); }int main(){
int a,b,m; printf("请依次输入a,b,m:\n"); scanf("%d %d %d",&a,&b,&m); if(congruence(a,b,m)==-1) printf("该同余方程没有整数解\n"); else printf("同余方程的解为:%d\n",congruence(a,b,m));}

只有当 b 为 g c d ( a , m ) b为gcd(a,m) bgcd(a,m)的倍数时,同余方程有整数解,个数为 g c d ( a , m ) gcd(a,m) gcd(a,m)

当gcd(a,m)=1时,方程有一个解

二、模指数运算

实现模指数运算函数,给定x,y和m,计算x的y次方模m

#include
int rec_mod_exp(int x,int y,int p){
int z=0; if(y==0) return 1; z=rec_mod_exp(x,y/2,p); if(y==0) return z*z%p; else return x*z*z%p;}

三、费尔马小定理

设p=23,a=5,使用费尔马小定理计算a^{2020}mod p

解: 5 2020 m o d 23 = 5 ( 23 − 1 ) ∗ 91 + 18 m o d 23 5^{2020} mod 23=5^{(23-1)*91+18} mod 23 52020mod23=5(231)91+18mod23

= 5 18 m o d 23 =5^{18}mod23 =518mod23
= 6 =6 =6

四、欧拉定理

使用欧拉定理计算2^{100000}mod 55。

由于 ϕ ( 55 ) = 40 \phi(55)=40 ϕ(55)=40,由欧拉定理可得 2 100000 m o d 55 = 2 40 ∗ 2500 m o d 55 = 1 2^{100000}mod55=2^{40*2500}mod 55=1 2100000mod55=2402500mod55=1

五、手动计算7^{1000}的最后两个数位等于什么

计算 7 1000 7^{1000} 71000的后两位等同于求 7 1000 m o d 100 7^{1000}mod 100 71000mod100

由于 ϕ ( 100 ) = 40 \phi(100)=40 ϕ(100)=40,由欧卡定理可得 7 1000 m o d 100 = 7 40 ∗ 25 m o d 100 = 1 7^{1000}mod 100=7^{40*25}mod100=1 71000mod100=74025mod100=1,所以后两位是01

转载地址:https://blog.csdn.net/m0_55443969/article/details/120633763 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:CINTA作业二:GCD与EGCD
下一篇:CINTA作业五:循环群

发表评论

最新留言

路过,博主的博客真漂亮。。
[***.116.15.85]2024年03月14日 09时02分30秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

ifpc挖filecoin_Filecoin挖矿分析全套 不容错过的干货 2019-04-21
python扫雷 高级算法_Python玩转算法—扫雷 2019-04-21
牛客网python测试考试答案_牛客网SQL题库之考试分数 2019-04-21
git获取所有branch_使用jGit 通过gitUrl 获取Git的所有分支 2019-04-21
mysql like 数字结尾_重拾MySQL之正则表达式 2019-04-21
mysql where从句_《快速念咒——MySQL自学入门指南》:第1章第8节:模糊查询LIKE——一窝兔子(上)... 2019-04-21
mysql 重置密码_mysql忘记密码如何重置密码,以及修改root密码的三种方法 2019-04-21
python-docx tables后追加内容_Mac brew安装MySQL8.0.21后忘记密码(重置密码篇) 2019-04-21
python中两个时间相减结果转为小时_Python起步(二)基础数据类型1 2019-04-21
定义泛化。举个例子_网易考拉应用的dubbo泛化调用,是如何实现的? 2019-04-21
mysql里可以用cube吗_sql server的cube操作符使用详解_mysql 2019-04-21
php mysql 图书_使用PHP+MySQL来对图书管理系统进行构建 2019-04-21
单片机c语言 int1,51单片机into、int1中断计数c语言源程序.doc 2019-04-21
c语言课程设计工资管理建库,C语言课程设计工资管理系统参考.doc 2019-04-21
c语言case中途跳出,break语句在switch结构语句中的作用是终止某个case,并跳出switch结构语句。... 2019-04-21
c51写c语言外部ram头文件,C51中访问外部RAM的方法 2019-04-21
51c语言产生随机证书,基于51单片机的随机数产生器设计-LCD1602-KEY-(电路图+程序源码)... 2019-04-21
C语言编写程序计算高考倒计时天数,基于51单片机LCD12864大字符校时万年历带高考倒计时程序... 2019-04-21
c语言打开一个html文件路径,C语言文件处理-C语言文件的打开和关闭 2019-04-21
普职融通信息技术课本C语言,“三步走”扎实推进“普职融通”办学新模式 2019-04-21