当前位置：网站首页>Using the primitive root of module m to judge and solve

Using the primitive root of module m to judge and solve

2022-07-26 08:32:00 【biyezuopin】

Using the model m The existence judgment and solution of the primitive root of

One 、 subject ：

model m The existence judgment and solution of the primitive root of . Judge m Whether the original root exists , If there is one primitive root and all primitive roots .

Two 、 Problem description

First of all, we must judge the given module m Whether there is an original root , Then we need to solve its original root .

3、 ... and 、 Mathematical basis

① Ethmoidal method , Solve the primes in a given range in the form of a table
② Determine whether there is a primitive root
③ For a given module m, Solve the Euler function φ(m)
④ Use Euclidean division to determine the base a Sum module m Mutual prime or not
⑤ Use modular square repetition method to calculate the result of congruence , Judge whether there is congruence 1

Four 、 Algorithm description

① Ethmoidal method ： First set the size to n The array of is all set to 1, from 2 Start traversing the array , Encountered value is 1 The subscript , Set the element of its subscript multiple to 0（1 As a prime number ,0 As composite ）
② Judge the given module m, Primitive root existence ： model m yes 2、4、pα、2pα One of the , There will be original roots
③ Solve the Euler function , Solve through Euler function formula
④ Use Euclidean division to judge coprime ： Solve the greatest common factor of two numbers , If the greatest common factor is greater than 1 They are not mutually exclusive , If the greatest common factor is equal to 1 Then mutual prime

⑤ Modular square repetition method ： The algorithm here is implemented in ：answer It is... In modular square repetition method a,base by b, The binary form of the index is transformed by bit operation and 1, Plus the binary shift right operator , Thus, the lowest bit of exponential binary is operated every time , Realize the traversal of binary bits . When binary is 1 and 0 when ,answer and base There are different solutions .

5、 ... and 、 Algorithm implementation

① Ethmoidal method ：

void Eratosthenes(const int &num, vector<int> &prime)
{
    prime.resize(num + 1);
    for (auto &i : prime)
            = 1;
    prime[0] = 0, prime[1] = 0;
    for (int i = 1; i <= num + 1; ++i)
    {
        if (prime[i] == 0)
            continue;
// The number is prime , Set his multiples to composite 
        int composite = i;
        while ((composite += i) <= num)
            prime[composite] = 0;
    }
}

② Judge the existence of primitive roots ：

bool judge_exist_root(const int &num)
{
    if (num == 2 || num == 4)
        return true;
    Eratosthenes(num, prime);
    for (int element = 3; element < prime.size(); ++element)
    {
        if (prime[element] == 0)
            continue;
        for (int i = 1;; ++i)
        {
            int target = pow(element, i);
            if (target > num)
                break;
            if (target == num || target * 2 == num)
                return true;
        }
    }
    return false;
}

③ Euler function ：

int Euler(const int &num)
{
// Find Euler functions 
    if (prime[num] == 1)
        return num - 1;
    int result = num, n = num;
    for (int i = 2; i * i <= n; ++i)
    {
        if (n % i == 0)
        {
// Find a prime factor 
            result = result / i * (i - 1);
            while (n % i == 0)
// Remove all the prime factors 
                /= i;
        }
    }
    if (n > 1)
// Check whether there is any omission 
        result = result / n * (n - 1);
    return result;
}

④ Judge whether two numbers are mutually prime ：

bool coprime(int i, int num)
{
// Euclidean division judges coprime 
    if (i == 1 || num == 1)
//  In two positive integers , Only one of the values is 1, Two positive integers are coprime numbers 
        return true;
    while (1)
    {
// Find the greatest common divisor of two numbers 
        int temp = i % num;
        if (temp == 0)
            break;
        else
                = num, num = temp;
    }
    if (num > 1)
//  If the greatest common divisor is greater than 1, Indicates that two positive integers are not coprime 
        return false;
    return true;
}

⑤ Modular square repetition method ：

int quick_pow(const int &a, int b, const int &mod)
{
// Modular square repetition method 
    int answer = 1, base = a % mod; //answer It is... In modular square repetition method a,base by b
    while (b != 0)
    {
// An operation and, The calculation result is a Whether the lowest binary bit of is 1, Update the lowest order through the shift right operator 
        if (b & 1)
            answer = (answer * base) % mod;
        base = (base * base) % mod;
        >>= 1;
    }
    return answer;
}