C/C++教程

CINTA作业三:同余、模指数、费尔马小定理、欧拉定理

本文主要是介绍CINTA作业三:同余、模指数、费尔马小定理、欧拉定理,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

CINTA作业三:同余、模指数、费尔马小定理、欧拉定理

提示:本章主要围绕整数运算中模关系的运算


文章目录

  • CINTA作业三:同余、模指数、费尔马小定理、欧拉定理
  • 一、实现求乘法逆元的函数
  • 二、实现模指数运算的函数
  • 三、费尔马小定理的应用
  • 四、欧拉定理的应用
  • 五、手动计算7^{1000}的最后两个数位等于什么


一、实现求乘法逆元的函数

要求如下:

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

代码如下:

#include<iostream>
//#include<math.h>
using namespace std;
int gcd(int a,int b);
int egcd(int a,int b);
int solve_equations(int a,int b,int m);

void main()
{
	int a,b,m;

	//求a模m的乘法逆元
	cout<<"输入整数a和m"<<'\n';
	cin>>a>>m;
	if(egcd(a,m)==0)   cout<<"不存在a模m的乘法逆元!"<<'\n';
	else               cout<<"a模m的乘法逆元为:"<<egcd(a,m)<<'\n';  


	//求解同余方程
	cout<<'\n'<<'\n'<<"输入同余方程(ax = b mod m)的相关数据a,b,m(m>0)"<<'\n';;
	cin>>a>>b>>m;
	//cout<<"x="<<solve_equations(egcd(a,m),b,m)<<'\n';
	if(solve_equations(a,b,m)==-1)     cout<<"该同余方程无解!"<<'\n';
	else              cout<<"该同余方程的解为:  x="<<solve_equations(a,b,m)<<'\n';
	

}


int gcd(int a,int b)
{
	int t;
	while(b!=0)
	{
	  t=a%b;
	  a=b;
      b=t;
	}
	return a;
}


int egcd(int a,int b)
{
	int m=b;
	if(gcd(a,b)!=1)   return 0;    //a存在模m的乘法逆元的充要条件是gcd(a,m) = 1
	else
	{ 
		int r0=1,r1=0,s0=0,s1=1;
	    while(b)
	    {
		    int q=a/b;
		    int t=b;
		    b=a%b;
		    a=t;

		    int x=r1;
		    r1=r0-q*r1;
		    r0=x;

		    int y=s1;
		    s1=s0-q*s1;
		    s0=y;
	    }

		if(r0>0)    return r0;  
		else        return r0+m;
     }
}

int solve_equations(int a,int b,int m)
{
	if(b%gcd(a,m)!=0)    return -1;     //同余方程有解的充要条件是 gcd(a,m)∣b
	else
	{
		int x=1;
		b=egcd(a,m)*b;
	    while((x-b)%m!=0)
	         x++;
	    return x;
	}
}

总结:

1.a存在模m的乘法逆元的充要条件是gcd(a,m) = 1
2.同余方程有解的充要条件是 gcd(a,m)∣b
在这里插入图片描述


二、实现模指数运算的函数

要求如下:

给定x、y和m,求x的y次方模m。

代码如下(示例):

#include<iostream>
using namespace std;
int rec_mod_exo(int x,int y,int p);    //迭代法

void main()
{
	int x,y,m;
	cout<<"**** 求x的y次方模m ****"<<'\n';
	cout<<"输入x、y和m"<<'\n';
	cin>>x>>y>>m;
	cout<<"结果为:"<<rec_mod_exo(x,y,m)<<'\n';;
}

int rec_mod_exo(int x, int y, int p)
{
	int z;
	if(y==0)   return 1;
	z=rec_mod_exo(x,y/2,p);
	if(y%2==0)      //y为偶数
		return z*z%p;
	else            //y为奇数
		return x*z*z%p;
}

 


三、费尔马小定理的应用

要求如下:

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

 
解: 5 2020 5^{2020} 52020 ≡ \equiv ≡ 5 91 ∗ 22 + 18 5^{91*22+18} 591∗22+18 (mod 23)
     ∴ \therefore ∴ 5 91 ∗ 22 + 18 5^{91*22+18} 591∗22+18 ≡ \equiv ≡ 5 18 5^{18} 518 (mod 23)

    又 ∵ \because ∵ 5 2 5^{2} 52 mod 23 = 2
         5 4 5^{4} 54 mod 23 = 4
         5 8 5^{8} 58 mod 23 = 8
         5 16 5^{16} 516 mod 23 = 18

     ∴ \therefore ∴ 5 18 5^{18} 518 (mod 23) ≡ \equiv ≡ 5 10010 5^{10010} 510010 (mod 23)
     ∴ \therefore ∴ 原式 = (18x2) mod 23 =13

 


四、欧拉定理的应用

要求如下:

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

 
解:由欧拉Phi函数公式可知, ϕ \phi ϕ(55) = ϕ \phi ϕ(5) ϕ \phi ϕ(11)
    又由欧拉Phi函数性质知, ϕ \phi ϕ(5)=4, ϕ \phi ϕ(11)=10
    ∴ \therefore ∴ ϕ \phi ϕ(55) = 4 x 10 = 40
    由欧拉定理知, 2 ϕ ( 55 ) 2^{ϕ(55)} 2ϕ(55) ≡ \equiv ≡ 1 (mod 55) ;
    即, 2 40 2^{40} 240 ≡ \equiv ≡ 1 (mod 55)
    ∴ \therefore ∴ 2 100000 2^{100000} 2100000 mod 55 = 2 40 ∗ 2500 2^{40*2500} 240∗2500 mod 55 = 1

 


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

要求如下:

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

解:要求 7 1000 7^{1000} 71000 的最后两个位数,即求 7 1000 7^{1000} 71000 mod 100
     ∵ \because ∵ gcd(7,100) = 1
     ∴ \therefore ∴由欧拉定理知, 7 ϕ ( 100 ) 7^{ϕ(100)} 7ϕ(100) ≡ \equiv ≡ 1 (mod 100)
    由欧拉Phi函数公式可知, ϕ \phi ϕ(100) = ϕ \phi ϕ(25) ϕ \phi ϕ(4) = 20 x 2 = 40
     即, 7 40 7^{40} 740 ≡ \equiv ≡ 1 (mod 100)
     ∴ \therefore ∴ 7 1000 7^{1000} 71000 mod 100 = 2 40 ∗ 25 2^{40*25} 240∗25 mod 100 = 1
     ∴ \therefore ∴ 7 1000 7^{1000} 71000 的最后两个数位等于01

 


这篇关于CINTA作业三:同余、模指数、费尔马小定理、欧拉定理的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!