31.数论算法总结

1.GCD

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

2 欧拉公式

$\phi(n)=n\prod_{p|n}(1-\frac{1}{p})$ϕ(n)=np∣n∏​(1−p1​)

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

$|Z_{15}^{*}|=15\times (1-\frac{1}{3}) \times(1-\frac{1}{5})$∣Z15∗​∣=15×(1−31​)×(1−51​)

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

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算法

例子：p=11,q=29,n=319,e=3.

$\phi(n)=(p-1)(q-1)=280$ϕ(n)=(p−1)(q−1)=280

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

$x'=-93\mod 280=187$x′=−93mod280=187

$d = 187$d=187

$C=M^e \mod n=100^3\mod 319=254$C=Memodn=1003mod319=254

$M=C^d \mod n = 254^{187} \mod 319 = 100$M=Cdmodn=254187mod319=100

5.素数判定

5.1 费马引理

$a^{p-1}=(1\mod p)$ap−1=(1modp)

5.2 二次探测引理

$x^2=(1\mod p),x=1\ or\ x=p-1$x2=(1modp),x=1 or x=p−1

proof.
$x^2-1=(x+1)(x-1)=(0\mod p)\rightarrow p|(x+1)(x-1)$x2−1=(x+1)(x−1)=(0modp)→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比为偶数，令
$n-1=2^{q}m$n−1=2qm
其中，m的二进制后跟q个0，即为n-1。

对于素数，则必满足费马引理（$a^{2^{q}m}=a^{n-1}=(1\mod n),\ q=0$a2qm=an−1=(1modn), q=0）

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

所以对如下序列{x}进行上述验证：
$a^{m},a^{2m},a^{4m},\cdots,a^{2^qm}$am,a2m,a4m,⋯,a2qm
只要其中某一项不满足$x^2=(1\mod n)$x2=(1modn)时，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 误判概率

​ 结论：上界$2^{-s}$2−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;
}