31.2

GCD Euclid's algorithm

$O(\log b)$ 

1
2
3
4
5
6
7
int EUCLID(int a, int b)
{
    if (b == 0)
        return a;
    else
        return EUCLID(b, a % b);
}

EXTENDED_EUCLID

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
#include<tuple>

std::tuple<int, int, int> EXTENDED_EUCLID(int a, int b)
{
    if (b == 0)
    {
        std::tuple<int, int, int> x(a, 1, 0);
        return x;
    }
    std::tuple<int, int, int> x = EXTENDED_EUCLID(b, a % b);//d x y
    std::tuple<int, int, int> y =
        std::make_tuple(std::get<0>(x), std::get<2>(x), std::get<1>(x) - (a / b) * std::get<2>(x));
    return y;
}

31.4

MODULAR_LINEAR_EQUATION_SOLVER

$O(\log n + \gcd(a,n))$ 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
void MODULAR_LINEAR_EQUATION_SOLVER(int a, int b, int n)//ax = b (mod n)
{
    std::tuple<int, int, int> set = EXTENDED_EUCLID(a, n);
    int d = std::get<0>(set);
    if (b/d)
    {
        int x_0 = (((std::get<1>(set) * (b / d))%n) + n)%n;
        //x_0 %= n;
        for (int i = 0; i <= d -1; i++)
        {
            std::cout << (x_0 + (i * (n / d))) % n << ' ';
        }
    }
    else
    {
        std::cout << "no solution";
    }
}

modulo 연산에대한 역

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
int extended_Euclid_for_multiple_inverse(const int a, const int mod_n)
{
    if (gcd(a, mod_n) != 1)
        return -1;
    r1 = a, r2 = mod_n;
     t1 = 0, t2 = 1;
    u, r, t;
    while (r2 > 0)
    {
        u = r1 / r2;

        r = r1 % r2;
        r1 = r2; r2 = r;

        t = t1 - u * t2;
        t1 = t2; t2 = t;
    }
    if (t1 < 0)
        t1 += mod_n;

    return t1;  //e
}

31.5 The Chinese remainder theorem

https://www.acmicpc.net/problem/1476

31.6

고속 거듭제곱 모듈러 연산

CLRS에 소개된 의사코드는 잘 작동하지 않는다.

코드를 살펴보면 c를 사용하지않음 d - bit $O(d)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int MODULAR_EXPONENTIATION(int a, int b, int n)//a^b mod n
{
    int x = a, y = 1;
    while(b != 0)
    {
        if (b & 1)
        {
            y = (x * y) % n;
        }
        x = (x * x) % n;
        b = b >> 1;
    }
    return y;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
int EXPONENTIATION(int a, int b)//a^b
    int x = a, y = 1;
    while(b != 0)
    {
        if (b & 1)
        {
            y = (x * y);
        }
        x = (x * x);
        b = b >> 1;
    }
    return y;
}

31.7 The RSA public-key crytosystem

  1. Select at random two large prime numbers p and q such that p != q. The primes p and q might be, say, 1024 bits each.

  2. Compute n = pq.

  3. Select a small odd integer e that is relatively prime to pi(n), which, by equation (31.20), equals (p-1)(q-1)

  4. Compute d as the multiplicative inverse of e, modulo pi(n). (Corollary 31.26 guarantees that d exists and is uniquely defined. We can use the technique of Section 31.4 to compute d, given e and pi(n))

  5. Publish the pair P = (e,n) as the participant’s RSA public key.

  6. Keep secret the pair S = (d, n) as the participant’s RSA secret key.

go to RSA.h

31.8 Primality tetsting

$O(\sqrt{n})$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
bool trial_division(int n)
{
    if (n == 2)
    {
        return true;
    }

    if ((n % 2 == 0) | (n == 1))
    {
        return false;
    }
    for(int i = 3; i*i <= n ; i += 2)
    {
        if(n%i == 0)
        {
            return false;
        }
    }
    return true;
}

PSEUDOPRIME(n)

Carmichael numbers 561 1105 1729 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
constexpr bool PRIME = true;
constexpr bool COMPOSITE = false;

bool PSEUDOPRIME(int n)
{
    if (MODULAR_EXPONENTIATION(2, n - 1, n) != 1)
    {
        return COMPOSITE;
    }
    return PRIME;
}

MILLER_RABIN_primality_test

https://casterian.net/archives/396

https://www.acmicpc.net/problem/5615

$O(k \log^3 n)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
bool WITNESS(ull a, ull n, ull u, ull t)
{
    ull x_pre = MODULAR_EXPONENTIATION(a, u, n);
    ull x = x_pre;
    for (int i = 0; i < t; i++)
    {
        x = (x_pre * x_pre) % n;
        if (x == 1 && x_pre != 1 && x_pre != n - 1)
        {
            return true;
        }
        x_pre = x;
    }
    if (x != 1)
        return true;
    return false;
}
a = 2,3,5,7,11,13,17, 31,61 ,73 정도로할때 정수표현가능한 모든 소수를 판ㄴ별할수있다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
typedef unsigned long long ull;
constexpr bool PRIME = true;
constexpr bool COMPOSITE = false;

bool MILLER_RABIN(ull n)
{
    if (n == 2)
    {
        return PRIME;
    }
    if (n == 1 || n % 2 == 0)
    {
        return COMPOSITE;
    }

    ull t = 0;
    ull u = n - 1;
    while (u % 2 == 0) 
    {
        t++;
        u = u >> 1;
    }

    //, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 61, 73
    ull test[] = { 2, 3};

    for(auto a : test)
    {
        if (n == a)
        {
            return PRIME;
        }
        if (WITNESS(a, n, u, t)) //합성수일시 true 반환
        {
            return COMPOSITE;
        }
    }
    return PRIME; //probably
}

31.9 Integer factorization

https://www.acmicpc.net/problem/4149

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void POLLARED_RHO(int n)
{
    int i = 1;
    int x = 2;// random n
    int y = x;
    int k = 2;
    int x_n = 0;
    int d = 0;
    while (1)
    {
        i++;
        x_n = (x * x - 1) % n;
        d = EUCLID(abs(y - x_n), n); 
        if (d != 1 && d != n)
        {
            std::cout << d << '\n';
        }
        if (i == k)
        {
            y = x_n;
            k = 2 * k;
        }
        x = x_n;
    }
}

Problems

31-2 Binary gcd algorithm

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
unsigned int gcd(unsigned int u, unsigned int v)
{
    if (u == 0)
    {
        return v;
    }
    if (v == 0)
    {
        return u;
    }

    if (((u & v) & 1) == 0) // 짝수
    {
        return (gcd(u >> 1, v >> 1)) << 1;
    }
    if ((u & 1) == 0) // 짝수
    {
        return gcd(u >> 1, v );
    }
    if((v & 1) == 0)
    {
        return gcd(u, v >> 1);
    }
    if (v > u)
    {
        int a = v;
        v = u;
        u = a;
    }

    else
    {
        return gcd((u-v)>>1, v);
    }
}

31-3 Three algorighms for Fibonacci numbers

(a) $O(2^n)$ 

1
2
3
4
5
6
7
8
int Fibonacci_numbers(int n)
{
    if (n == 1 || n == 2)
    {
        return 1;
    }
    return Fibonacci_numbers(n - 1) + Fibonacci_numbers(n - 2);
}

(b) memoization

$O(n)$ 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
int Fibonacci_numbers(int n)
{

    if (n == 1 || n == 2)
    {
        return 1;
    }
    int x = 1, y = 1;

    int Fibonacci = 1;
        for (int i = 3; i <= n; i++)
        {

            Fibonacci = x + y;
            x = y;
            y = Fibonacci;

        }
    return Fibonacci;
}

(c) $O(\log n)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int Fibonacci_numbers(int n)
{
    int mat[2][2] = { 0,1,1,1 };
    int y[2][2] = { 0,1,1,1 };
    int z[2][2] = { 0,1,1,1 };
    if (n == 1 || n == 2)
    {
        return 1;
    }
    int a = n - 1;
    while (a != 0)
    {
        if (a & 1)
        {
            y[0][0] = z[0][0];
            y[0][1] = z[0][1];
            y[1][0] = z[1][0];
            y[1][1] = z[1][1];
            z[0][0] = y[0][0] * mat[0][0] + y[1][0] * mat[0][1];
            z[0][1] = y[0][0] * mat[0][1] + y[0][1] * mat[1][1];
            z[1][0] = y[1][0] * mat[0][0] + y[1][1] * mat[1][0];
            z[1][1] = y[1][0] * mat[0][1] + y[1][1] * mat[1][1];
        }
        y[0][0] = mat[0][0];
        y[0][1] = mat[0][1];
        y[1][0] = mat[1][0];
        y[1][1] = mat[1][1];
        mat[0][0] = y[0][0] * y[0][0] + y[1][0] * y[0][1];
        mat[0][1] = y[0][0] * y[0][1] + y[0][1] * y[1][1];
        mat[1][0] = y[0][0] * y[1][0] + y[1][0] * y[1][1];
        mat[1][1] = y[1][0] * y[0][1] + y[1][1] * y[1][1];
        a = a >> 1;
    }
    return z[1][0];
}