欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

31.数论算法总结

程序员文章站 2022-07-15 22:38:05
...

1.GCD

int gcd(int a, int b){
  if(b == 0) return a;
  return gcd(b ,a%b);
}

2 欧拉公式

ϕ(n)=npn(11p) \phi(n)=n\prod_{p|n}(1-\frac{1}{p})

Z15=1,2,4,7,8,11,13,14 Z_{15}^{*}={1,2,4,7,8,11,13,14}

Z15=15×(113)×(115) |Z_{15}^{*}|=15\times (1-\frac{1}{3}) \times(1-\frac{1}{5})

15=31×51 15 = 3^{1}\times 5^{1}

15 * 2/3 * 4/5 表示对原有集合的缩减,缩减的比例是能够以p为除数整除n的比例为依据。

3.求幂(反复平方法)

typedef long long int ll;
ll mod_mul(ll a, ll b, ll mod)
{
    ll res = 0;
    while (b)
    {
        if (b & 1)
            res = (res + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return res;
}
ll mod_pow(ll a, ll n, ll mod)
{
    ll res = 1;
    while (n)
    {
        if (n & 1)
            res = mod_mul(res, a, mod);
        a = mod_mul(a, a, mod);
        n >>= 1;
    }
    return res;
}

####4.RSA算法
31.数论算法总结
例子:p=11,q=29,n=319,e=3.

ϕ(n)=(p1)(q1)=280\phi(n)=(p-1)(q-1)=280

1=ax+ny=>1=3×x+280y1=ax'+ny'=> 1=3\times x'+280y'

x=93mod  280=187x'=-93\mod 280=187

d=187d = 187

C=Memod  n=1003mod  319=254C=M^e \mod n=100^3\mod 319=254

M=Cdmod  n=254187mod  319=100M=C^d \mod n = 254^{187} \mod 319 = 100

5.素数判定

5.1 费马引理

ap1=(1mod  p) a^{p-1}=(1\mod p)

5.2 二次探测引理

x2=(1mod  p),x=1 or x=p1 x^2=(1\mod p),x=1\ or\ x=p-1

proof.
x21=(x+1)(x1)=(0mod  p)p(x+1)(x1) x^2-1=(x+1)(x-1)=(0\mod p)\rightarrow p|(x+1)(x-1)

p is prime number, so, x+1=p, x-1=0 => x=p-1, x=1
5.3 Miller-Rabin改进

对于n,若为素数,则n-1比为偶数,令
n1=2qm n-1=2^{q}m
其中,m的二进制后跟q个0,即为n-1。

对于素数,则必满足费马引理(a2qm=an1=(1mod  n), q=0a^{2^{q}m}=a^{n-1}=(1\mod n),\ q=0

由二次探测引理可知,a2qm=(a2q1m)2=(1mod  n)a^{2^{q}m}=(a^{2^{q-1}m})^2=(1\mod n), 记x=a2q1mx=a^{2^{q-1}m},则x=1 or x=n1x=1 \ or\ x=n-1,当n为素数时,否则n为合数。

所以对如下序列{x}进行上述验证:
am,a2m,a4m,,a2qm a^{m},a^{2m},a^{4m},\cdots,a^{2^qm}
只要其中某一项不满足x2=(1mod  n)x^2=(1\mod n)时,x=1或x=n-1,则n必为合数。

// Miller-Rabin随机算法检测n是否为合数
bool Miller_Rabin(ll n, int s)
{
    ll m = n - 1, k = 0;
    while (!(m & 1))
    {
        k++;
        m >>= 1;
    }
    for (int i = 1; i <= s; i++)  // 迭代次数
    {
        ll a = rand() % (n - 1) + 1;	//每次选取不同的基
        ll x = mod_pow(a, m, n);
        ll y;
        for (int j = 1; j <= k; j++)
        {
            y = mod_mul(x, x, n);
            if (y == 1 && x != 1 && x != n - 1)	//二次探测检查
                return true;
            x = y;
        }
        if (y != 1)			//费马引理检查
            return true;
    }
    return false;
}

bool is_prime(int n){
    if (n == 2)
        return true;
    if (n < 2 || !(n & 1))
        return false;
    return !Miller_Rabin(n, 1);
}
5.4 误判概率

​ 结论:上界2s2^{-s},实际表现更好。

​ 证明:群论不想看,以后有心情再学。

6 整数因子分解

#include <iostream>
#include <vector>
using namespace std;
void solve(int n, int s, vector<int>& res){
    for(int i=s;i<=n;i++){
        if(n%i == 0){
            res.push_back(i);
            solve(n/i, i, res);
            break;
        }
    }
}
int main(){
    vector<int> res;
    solve(60, 2, res);
    for(auto e: res)
        cout << e << " ";
    cout << endl;
    return 0;
}