关于欧拉函数python实现的信息

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那么φ

相关问答

Q1: python的math库有没有欧拉函数？

对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（因此φ(1)=1）。此函数以其首名研究者欧拉命名(Euler’s totient function)，它又称为Euler’s totient function、φ函数、欧拉商数等。cs-dn 例如φ(8)=4，因为1,3,5,7均和8互质。

Q2: 2的欧拉函数值为什么是

一.欧拉函数

1.算法描述

1∼N 中与 N 互质的数的个数被称为欧拉函数，也就是说，1~N中与N的最大公约数是1的数的个数，记作\phi \left ( N \right )。

在算术基本定理中，若

N=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2 }}\cdot \cdot \cdot p_{n}^{\alpha _{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 )

证明如下：我们可以分以下几步求出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；当分母为偶数个乘积时，每一项的符号都是-1的偶数次方，为正。

这个公式可以类比于约数的个数,道理是一样的。

\left ( p_{1}^{0}+p_{1}^{1} +\cdot \cdot \cdot + p_{1}^{\alpha _{1}}\right )\left ( p_{2}^{0}+p_{2}^{1} +\cdot \cdot \cdot + p_{2}^{\alpha _{2}}\right )\cdot \cdot \cdot \left ( p_{n}^{0}+p_{n}^{1} +\cdot \cdot \cdot + p_{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;

}

Q3: Python如何引用欧拉常数

欧拉常数(Euler-Mascheroniconstant)。

学过高等数学的人都知道，调和级数S=1+1/2+1/3+..是发散的这时引用欧拉常数。

在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（因此φ(1)=1）此函数以其首名研究者欧拉命名(Euler’stotientfunction)，它又称为Euler’stotientfunction、φ函数、欧拉商数等例如φ(8)=4，因为1，3，5，7均和8互质。

Q4: 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实现：

Q5: 请问 图片里的双横线那里是什么符号 表示什么意思？

你好，这是欧拉函数

在数论，对正整数n，欧拉函数是小于等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名(Euler'so totient function)，它又称为Euler's totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。 从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。

定    义

小于n的数中与n互质的数的数目

其中p1, p2……pn为x的所有质因数，x是不为0的整数。

φ(1)=1（唯一和1互质的数(小于等于1)就是1本身）。

注意：每种质因数只一个。 比如12=2*2*3那么φ（12）=12*（1-1/2）*(1-1/3)=4

若n是质数p的k次幂，因为除了p的倍数外，其他数都跟n互质。

设n为正整数，以 φ(n)表示不超过n且与n互素的正整数的个数，称为n的欧拉函数值

φ：N→N，n→φ(n)称为欧拉函数。

欧拉函数是积性函数——若m,n互质，

特殊性质：当n为奇数时，

, 证明与上述类似。

若n为质数则

证明

设A, B, C是跟m, n, mn互质的数的集，据中国剩余定理，A*B和C可建立一一对应的关系。因此φ(n)的值使用算术基本定理便知，若则

例如

与欧拉定理、费马小定理的关系

对任何两个互质的正整数a, m(m=2)有

即欧拉定理

当m是质数p时，此式则为：

a^(p-1)≡1(mod m)

即费马小定理。

编程实现

编辑

利用欧拉函数和它本身不同质因数的关系，用筛法计算出某个范围内所有数的欧拉函数值。

欧拉函数和它本身不同质因数的关系：

欧拉函数ψ（N）=N{∏p|N}（1－1/p）

亦即:

（P是数N的质因数）