实现欧拉函数python的简单介绍

2的欧拉函数值为什么是一.欧拉函数
1.算法描述
1~N 中与 N 互质的数的个数被称为欧拉函数实现欧拉函数python,也就是说,1~N中与N的最大公约数是1的数的个数,记作\phi \left ( N \right ) 。
在算术基本定理中 , 若
N=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2 }}\cdot \cdot \cdot p_{n}^{\alpha _{n}}
则实现欧拉函数python:
\phi \left ( N \right )=N\left ( 1-\frac{1}{p_{1}} \right )\left ( 1-\frac{1}{p_{2}} \right )\cdot \cdot \cdot \left ( 1-\frac{1}{p_{n}} \right )
证明如下:我们可以分以下几步求出N的互质的数
1.在1~N这些数中,将p1、p2、……pn的倍数剔除 , 很显然,pi的倍数和N的最大公约数是不是1.
N-\frac{N}{p_{1}}-\frac{N}{p_{2}}-\cdot \cdot \cdot -\frac{N}{p_{n}}
2.但需要注意是,在1~N这些数中,pi*pj的倍数倍剔除了两次,因此要把他们加上
\frac{N}{p_{1}p_{2}} \frac{N}{p_{1}p_{3}} \cdot \cdot \cdot\frac{N}{p_{n-1}p_{n}}
3.但是 , 对于pi*pj*pk的倍数,在第1步时,被剔除了三次,在第2步时,被pi*pj、pi*pk、pj*pk加上了三次,因而我们需要把pi*pj*pk的倍数再剔除一次:
-\frac{N}{p_{1}p_{2}p_{3}}-\frac{N}{p_{1}p_{2}p_{4}}-\cdot \cdot \cdot -\frac{N}{p_{n-2}p_{n-1}p_{n}}
4.那么可以想到 , 接下来就是所有N除以四项乘积的和,减去N除以五项乘积的和……
事实上,将所有的这些式子加起来,得到的就是
\phi \left ( N \right )=N\left ( 1-\frac{1}{p_{1}} \right )\left ( 1-\frac{1}{p_{2}} \right )\cdot \cdot \cdot \left ( 1-\frac{1}{p_{n}} \right )
首先,当分母为奇数个乘积时 , 那每一项的符号都是-1的奇数次方,还是-1实现欧拉函数python;当分母为偶数个乘积时,每一项的符号都是-1的偶数次方,为正 。
这个公式可以类比于约数的个数,道理是一样的 。
\left ( p_{1}^{0} p_{1}^{1}\cdot \cdot \cdotp_{1}^{\alpha _{1}}\right )\left ( p_{2}^{0} p_{2}^{1}\cdot \cdot \cdotp_{2}^{\alpha _{2}}\right )\cdot \cdot \cdot \left ( p_{n}^{0} p_{n}^{1}\cdot \cdot \cdotp_{n}^{\alpha _{n}}\right )
2.代码实现
可以发现,欧拉函数并不关心每个质因子的指数是什么 , 因而我们不用s来存储指数 , 也不用map来存储质因子,每当我们发现一个质数i时,让结果乘以(1-1/i) 。但需要注意两点:
1.对于(1-1/i),1/i是小数,就这么写的话,那每一项都是1了 , 所以要×i再÷i , 即:res=res/i*(i-1) 。
2.一定要记得在循环结束后,判断x是否会大于1,如果大于1,说明还存在x这个质因子,再执行一步:res=res/x*(x-1) 。
具体代码:
#includeiostream
using namespace std;
int n;
int main(){
cinn;
while(n--){
int x;
cinx;
int res=x;
for(int i=2;i=x/i;i){
if(x%i==0){
while(x%i==0){
x=x/i;//i是我的一个质数
}
res=res/i*(i-1);
}
}
if(x1) res=res/x*(x-1);//注意
coutresendl;
}
}
二.筛法求欧拉函数
1.算法描述
第一部分中的算法适合于求单个给定数字对应的欧拉函数的值 , 但是当题目要求求1~N所有数字的欧拉值之和时 , 用第一部分中的算法就会花费很多时间,下介绍用筛法求欧拉函数:
首先我们回顾筛法求质数的过程,对于给定的正整数N:
for(int i=2;i=n;i){
if(!str[i]){
primes[cnt]=i;
}
else{
for(int j=0;primes[j]=n/i;j){
str[i*primes[j]]=true;
if(i%primes[j]==0) break;
}
}
}
通过筛法,所有的质数,合数我们都可以遍历到,把所有的质数加入数组primes中,并且str[i*primes[j]]保证了每一个数都会被它的最小质因子筛掉,而if(i%primes[j]==0)保证了不会被重复标记,详细介绍可以参考:
那如何做出修改让筛法求欧拉函数?
1.首先,对于质数i , 那么1~i-1都与i互质 , 那么\phi \left (i \right )=i-1
2.对于合数 , 即我用str[i*primes[j]]将一个合数筛掉时 , 我必须同时把它的欧拉值求出来 , 我们分为以下两种情况:
A.若i可以整除primes[j] , 那么primes[j]*i和i有共同的质因子 , 这是因为primes[j]是i的质因子 , 那么\phi \left ( i \right )已经包括了1-\frac{1}{primes[j]}这一项,而欧拉函数的值与指数无关,因而:
\phi \left ( i*primes[j] \right )=primes[j]*\phi \left ( i \right )
B.若i不能够整除primes[j],那么primes[j]*i比i多一个质因子primes[j],这是因为i本身不包含质因子primes[j],而primes[j]本身是质数,不会再有质因子,因而:
\phi \left ( i*primes[j] \right )=primes[j]\left ( 1-\frac{1}{primes[j]} \right )\phi \left ( i\right )=\left ( primes[j] -1\right )\phi \left ( i \right )
因而,每一个数的欧拉值都可以通过该种方法求出来 。
2.代码实现
关于代码实现需要注意的是,res的值可能会很大 , 所以要定义成long long类型 。
具体代码:
#includeiostream
using namespace std;
int x;
const int N=1000010;
long long res;//最后的欧拉函数的值的和 , 有可能会非常大 , 要用long long
bool str[N];//是否被标记过
int primes[N];//存放质因子
int cnt;
int phi[N];//各个N的函数值
int main(){
phi[1]=1;//1的欧拉值为1捏
cinx;
for(int i=2;i=x;i){
if(!str[i]){//如果没有被标记过 , 那么是质数
phi[i]=i-1;//质数的欧拉值就是i-1
primes[cnt]=i;
}
for(int j=0;primes[j]=x/i;j){
str[i*primes[j]]=true;//首先我一定能把所有的合数遍历到 , 这是肯定的
if(i%primes[j]==0){
//如果i可以整除primes[j]的话,那么i和primes[j]*i的最小质因子是相同的
phi[i*primes[j]]=primes[j]*phi[i];
break;
}
else{
//如果i不可整除primes[j]的话,那么i和primes[j]*i就相差一个primes[j]这个最小质因子
phi[i*primes[j]]=primes[j]*phi[i]*(primes[j]-1)/primes[j];
//那这样就把所有数的欧拉值都存在phi中
}
}
}
for(int i=1;i=x;i){
res=res phi[i];
}
coutres;
}
Python如何引用欧拉常数欧拉常数(Euler-Mascheroniconstant) 。
学过高等数学实现欧拉函数python的人都知道实现欧拉函数python , 调和级数S=1 1/2 1/3 ..是发散实现欧拉函数python的这时引用欧拉常数 。
在数论实现欧拉函数python,对正整数n,欧拉函数是小于n实现欧拉函数python的正整数中与n互质的数的数目(因此φ(1)=1)此函数以其首名研究者欧拉命名(Euler’stotientfunction) , 它又称为Euler’stotientfunction、φ函数、欧拉商数等例如φ(8)=4,因为1,3,5,7均和8互质 。
python怎么调用欧拉距离的函数φ函数的值 通式:φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数 , x是不为0的整数 。φ(1)=1(唯一和1互质的数(小于等于1)就是1本身) 。(注意:每种质因数只一个 。比如12=2*2*3那么φ
CTF常见RSA相关问题的解决(复现) 本文参考为对其知识进行掌握,写此文章来梳理和加深记忆
前言:理解基本概念,本文将每种攻击方式实现方法提炼成了一个函数,便于理解原理也可以直接调用 。
基?。?
RSA概要:
在开始前可以通过《RSA算法详解》这篇文章了解关于RSA的基础知识,包括加解密方法 , 算法原理和可行性证明等 。(特详细)
应用流程:
1.选取两个较大的互不相等的质数p和q 计算n =p q 。
2.计算phi =(p-1) (q-1) 。
3.选取任意的e , 使得e满足1ephi 且 gcd(e,phi) ==1 .
4.计算e关于phi的模逆元d,即d满足(e*d)%phi ==1.
5.加解密:c=(m^e)%n ,m =(c^d)%n.其中m为明文,c为密文 (n,e)为公钥,d为私钥,要求0=mn.
求模逆可直接利用gmpy2库 。如 import gmpy2 print gmpy2.invert(47,30) 可求得47模30的逆为23 。
扩展欧几里得算法基于欧几里得算法,能够求出使得 ax by=gcd(a,b) 的一组x,y 。
常见攻击方式实践
准备工具
python gmpy2库 libnum库
yafu
RSATool2v17.exe
RSA解密
若已知私钥d,则可以直接解密:m=pow(c,d,n).
若已知质数p和q,则通过依次计算欧拉函数值phi、私钥d可解密 。简易实现如下:
在选取加密指数e时要求phi,e互质,也就是gcd(phi,e)==1,如果不满足是无法直接解密的 。
SCTF2018的Crypto - a number problem , 题目是: x**33=1926041757553905692219721422025224638913707 mod 3436415358139016629092568198745009225773259 tell me the smallest answer of x
其中n=3436415358139016629092568198745009225773259 可以直接分解得到p,q,出phi=(p-1)*(q-1) ,然后惊奇地发现gcd(phi,33)==3。这时如果对加密过程比较熟悉的话,就可以想到实际上公钥e=11,明文是m=x^3 , 应该先求出m 。然后再爆破x 。
n2,n3已知,利用共模攻击得到n1,由gcd(n1,n2)==p1 分解n1,n2,就可解密得到两部分msg,拼接即可 。
小明文攻击
适用情况:e较小 , 一般为3 。
公钥e很小,明文m也不大的话,于是 m^e=k*n m中的的k值很小甚至为0,爆破k或直接开三次方即可 。Python实现:
例子:Extremely hard RSA
题目提供的n是4096位的,e=3 。
Rabin加密中的N可被分解
适用情况:e==2
Rabin加密是RSA的衍生算法 , e==2是Rabin加密典型特征,可以百度或阅读以了解到详细的说明 , 这里只关注解密方法 。一般先通过其他方法分解得到p,q , 然后解密 。
Python实现:
函数返回四个数,这其中只有一个是我们想要的明文,需要通过其他方式验证,当然CTF中显然就是flag字眼了 。
Wiener’s Attack
适用情况:e过大或过小 。
工具:
在e过大或过小的情况下,可使用算法从e中快速推断出d的值 。详细的算法原理可以阅读: 低解密指数攻击。
例子:2018强网杯nextrsa-Level2
**私钥文件修复
适用情况:提供破损的私钥文件 。**
参考修复存储私钥的文件,得到p和q 。
**私钥修复
Python 脚本:**
从缺失的私钥中,我们可以分析出各部分数据代表的数字 。
改动原脚本中的各部分内容即可恢复出私钥,大致算法为:
**LSB Oracle Attack
适用情况:可以选择密文并泄露最低位 。**
在一次RSA加密中,明文为m,模数为n,加密指数为e,密文为c 。我们可以构造出 c'=((2^e)*c)%n=((2^e)*(m^e))%n=((2*m)^e)%n,因为m的两倍可能大于n , 所以经过解密得到的明文是m'=(2*m)%n。我们还能够知道m'的最低位 lsb是1还是0 。因为n是奇数,而 2*m是偶数 , 所以如果 lsb是0,说明 (2*m)%n是偶数,没有超过n,即 mn/2.0,反之则 mn/2.0。举个例子就能明白 2%3=2是偶数 , 而 4%3=1是奇数 。以此类推,构造密文 c"=(4^e)*c)%n使其解密后为 m"=(4*m)%n,判断 m"的奇偶性可以知道 m和n/4的大小关系 。所以我们就有了一个二分算法,可以在对数时间内将m的范围逼近到一个足够狭窄的空间 。
更多信息可参考: RSA Least-Significant-Bit Oracle Attack和RSA least significant bit oracle attack。
Python实现:
【实现欧拉函数python的简单介绍】关于实现欧拉函数python和的介绍到此就结束了,不知道你从中找到你需要的信息了吗 ?如果你还想了解更多这方面的信息,记得收藏关注本站 。

    推荐阅读