LMCAS::berlekamp_detail 命名空间参考

函数
std::vector< std::vector< int64_t > >	bk_build_q_matrix (const std::vector< int64_t > &f, int64_t p)
	构造 F_p 上的 Berlekamp 矩阵 Q。
static std::vector< int64_t >	bk_derivative_mod (const std::vector< int64_t > &f, int64_t p)
	计算模 p 多项式的形式导数.
void	bk_div_mod (const std::vector< int64_t > &a, const std::vector< int64_t > &b, int64_t p, std::vector< int64_t > &q, std::vector< int64_t > &r)
	模 p 多项式带余除法.
static void	bk_eliminate_column (std::vector< std::vector< int64_t > > &matrix, int current_row, int col, int64_t p)
std::vector< int64_t >	bk_gcd_mod (std::vector< int64_t > a, std::vector< int64_t > b, int64_t p)
	计算两个模 p 多项式的最大公因式.
static bool	bk_is_square_free_mod (const std::vector< int64_t > &f, int64_t p)
	检查模 p 多项式是否为 无平方因子.
bool	bk_is_suitable_prime (const Polynomial< Rational > &poly, int64_t prime)
	判断素数是否保持多项式次数和无平方性质。
int64_t	bk_mod_inverse (int64_t a, int64_t p)
	模 p 下求乘法逆元.
std::vector< std::vector< int64_t > >	bk_null_space (const std::vector< std::vector< int64_t > > &Q, int64_t p)
static std::vector< int64_t >	bk_poly_mul_mod (const std::vector< int64_t > &a, const std::vector< int64_t > &b, const std::vector< int64_t > &f, int64_t p)
	在 F_p 上计算 a(x) * b(x) mod f(x)。
static std::vector< int64_t >	bk_poly_pow_mod (const std::vector< int64_t > &base, int64_t exp, const std::vector< int64_t > &f, int64_t p)
	在 F_p 上用平方乘法计算 base^exp mod f(x)。
static void	bk_reduce_matrix (std::vector< std::vector< int64_t > > &M, int64_t p, std::vector< int > &pivot_col, std::vector< int > &pivot_row)
std::vector< int64_t >	bk_reduce_to_mod_coeffs (const Polynomial< Rational > &poly, int64_t p)
	以系数分母的 LCM 清除分母，再逐项取模 p。
int64_t	bk_select_prime (const Polynomial< Rational > &poly)
	从小素数表中选取适合 Berlekamp 分解的素数。
std::vector< std::vector< int64_t > >	bk_split_factors (const std::vector< int64_t > &f_coeffs, const std::vector< std::vector< int64_t > > &null_basis, int null_dim, int64_t p)
static bool	bk_split_one_factor (std::vector< std::vector< int64_t > > &factor_list, size_t fi, const std::vector< int64_t > &v_poly, int null_dim, int64_t p)

变量
static constexpr size_t	BK_NUM_SMALL_PRIMES
static constexpr int64_t	BK_SMALL_PRIMES []
	Berlekamp 模分解的小素数候选表。 按升序选取首个不整除首项系数且使模约化结果无平方因子的素数。

函数说明

bk_build_q_matrix()

std::vector< std::vector< int64_t > > LMCAS::berlekamp_detail::bk_build_q_matrix	(	const std::vector< int64_t > &	f,
		int64_t	p )

构造 F_p 上的 Berlekamp 矩阵 Q。

对次数为 n 的首一多项式 f，Q 的第 i 行为 x^(i*p) mod f(x) 的系数向量。 先用平方乘法求 h = x^p mod f，再由第 0 行 [1, 0, ..., 0] 逐行乘 h 并取余。

参数

[in]	f	首一多项式系数向量(升幂排列,deg(f) = n)
[in]	p	素数模数

返回

nxn Berlekamp 矩阵(行优先存储)

参见

Berlekamp, E.R. "Factoring polynomials over finite fields." Bell System Technical Journal, 46(8), 1967.

< f 的次数。

在文件 berlekamp_basis.cpp 第 106 行定义.

               {
 
    int n = static_cast<int>(f.size()) - 1;  /**< f 的次数。 */
 
    std::vector<std::vector<int64_t>> Q(n, std::vector<int64_t>(n, 0));
 
    if (n <= 0) {
        return Q;
    }
    Q[0][0] = 1;
 
    if (n == 1) {
        return Q;
    }
    std::vector<int64_t> x_poly = {0, 1};
    std::vector<int64_t> h = bk_poly_pow_mod(x_poly, p, f, p);
    for (size_t j = 0; j < h.size() && j < static_cast<size_t>(n); ++j) {
        Q[1][j] = h[j];
    }
    std::vector<int64_t> current = h;
    for (int i = 2; i < n; ++i) {
        current = bk_poly_mul_mod(current, h, f, p);
        for (size_t j = 0; j < current.size() && j < static_cast<size_t>(n); ++j) {
            Q[i][j] = current[j];
        }
    }
 
    return Q;
}

引用了 bk_build_q_matrix(), bk_poly_mul_mod() , 以及 bk_poly_pow_mod().

被这些函数引用 LMCAS::berlekamp_factor() , 以及 bk_build_q_matrix().

函数调用图:

这是这个函数的调用关系图:

bk_derivative_mod()

std::vector< int64_t > LMCAS::berlekamp_detail::bk_derivative_mod ( const std::vector< int64_t > & f, int64_t p )

static

计算模 p 多项式的形式导数.

参数

[in]	f	模 p 系数向量
[in]	p	素数模数

返回

f' 的系数向量

在文件 berlekamp_modular.cpp 第 76 行定义.

               {
 
    if (f.size() <= 1) {
        return {};
    }
 
    std::vector<int64_t> deriv;
    deriv.reserve(f.size() - 1);
 
    for (size_t i = 1; i < f.size(); ++i) {
        const auto index_residue = static_cast<std::int64_t>(
            i % static_cast<std::uint64_t>(p));
        int64_t coeff = (f[i] * index_residue) % p;
        deriv.push_back(coeff);
    }
 
    while (!deriv.empty() && deriv.back() == 0) {
        deriv.pop_back();
    }
 
    return deriv;
}

引用了 bk_derivative_mod().

被这些函数引用 bk_derivative_mod() , 以及 bk_is_square_free_mod().

函数调用图:

这是这个函数的调用关系图:

bk_div_mod()

void LMCAS::berlekamp_detail::bk_div_mod	(	const std::vector< int64_t > &	a,
		const std::vector< int64_t > &	b,
		int64_t	p,
		std::vector< int64_t > &	q,
		std::vector< int64_t > &	r )

模 p 多项式带余除法.

计算 a / b 的商和余数,使得 a = q * b + r,deg(r) < deg(b).

参数

[in]	a	被除数系数向量
[in]	b	除数系数向量(非空)
[in]	p	素数模数
[out]	q	商系数向量
[out]	r	余数系数向量

在文件 berlekamp_modular.cpp 第 129 行定义.

                           {
 
    q.clear();
    r = a;
 
    if (b.empty()) return;
 
    int deg_b = static_cast<int>(b.size()) - 1;
    int64_t lc_b_inv = bk_mod_inverse(b.back(), p);
 
    int deg_r = static_cast<int>(r.size()) - 1;
 
    if (deg_r < deg_b) {
        return;
    }
 
    q.resize(deg_r - deg_b + 1, 0);
 
    while (deg_r >= deg_b) {
        int64_t factor = (r[deg_r] * lc_b_inv) % p;
        int shift = deg_r - deg_b;
        q[shift] = factor;
 
        for (int i = 0; i <= deg_b; ++i) {
            r[shift + i] = (r[shift + i] - factor * b[i] % p + p) % p;
        }
 
        while (deg_r >= 0 && r[deg_r] == 0) {
            r.pop_back();
            deg_r--;
        }
    }
}

引用了 LMCAS::a, LMCAS::b, bk_div_mod(), bk_mod_inverse() , 以及 LMCAS::r.

被这些函数引用 bk_div_mod(), bk_gcd_mod(), bk_poly_mul_mod(), bk_poly_pow_mod() , 以及 bk_split_one_factor().

函数调用图:

这是这个函数的调用关系图:

bk_eliminate_column()

void LMCAS::berlekamp_detail::bk_eliminate_column ( std::vector< std::vector< int64_t > > & matrix, int current_row, int col, int64_t p )

static

在文件 berlekamp_basis.cpp 第 138 行定义.

                                                                     {
    const int n = static_cast<int>(matrix.size());
    int64_t inverse = bk_mod_inverse(matrix[current_row][col], p);
    for (int j = 0; j < n; ++j) {
        matrix[current_row][j] = (matrix[current_row][j] * inverse) % p;
    }
    for (int row = 0; row < n; ++row) {
        if (row == current_row) continue;
        int64_t factor = matrix[row][col];
        if (factor == 0) continue;
        for (int j = 0; j < n; ++j) {
            matrix[row][j] =
                (matrix[row][j] - factor * matrix[current_row][j] % p + p) % p;
        }
    }
}

引用了 bk_eliminate_column() , 以及 bk_mod_inverse().

被这些函数引用 bk_eliminate_column() , 以及 bk_reduce_matrix().

函数调用图:

这是这个函数的调用关系图:

bk_gcd_mod()

std::vector< int64_t > LMCAS::berlekamp_detail::bk_gcd_mod	(	std::vector< int64_t >	a,
		std::vector< int64_t >	b,
		int64_t	p )

计算两个模 p 多项式的最大公因式.

使用欧几里得算法.结果为首一多项式.

参数

[in]	a	第一个多项式系数向量
[in]	b	第二个多项式系数向量
[in]	p	素数模数

返回

gcd(a, b) 的首一化系数向量

在文件 berlekamp_modular.cpp 第 179 行定义.

               {
 
    while (!b.empty()) {
        std::vector<int64_t> q, r;
        bk_div_mod(a, b, p, q, r);
        a = std::move(b);
        b = std::move(r);
    }
 
    if (!a.empty()) {
        int64_t lc_inv = bk_mod_inverse(a.back(), p);
        for (auto& c : a) {
            c = (c * lc_inv) % p;
        }
    }
 
    return a;
}

引用了 LMCAS::a, LMCAS::b, bk_div_mod(), bk_gcd_mod(), bk_mod_inverse(), LMCAS::c , 以及 LMCAS::r.

被这些函数引用 bk_gcd_mod(), bk_is_square_free_mod() , 以及 bk_split_one_factor().

函数调用图:

这是这个函数的调用关系图:

bk_is_square_free_mod()

bool LMCAS::berlekamp_detail::bk_is_square_free_mod ( const std::vector< int64_t > & f, int64_t p )

static

检查模 p 多项式是否为 无平方因子.

多项式 f 在 F_p 上 无平方因子 当且仅当 gcd(f, f') 的次数为 0.

参数

[in]	f	模 p 系数向量
[in]	p	素数模数

返回

f 为 无平方因子 返回 true

在文件 berlekamp_modular.cpp 第 211 行定义.

               {
 
    if (f.size() <= 1) return true;
 
    std::vector<int64_t> f_prime = bk_derivative_mod(f, p);
    if (f_prime.empty()) return false;
 
    std::vector<int64_t> g = bk_gcd_mod(f, f_prime, p);
    return g.size() <= 1;
}

引用了 bk_derivative_mod(), bk_gcd_mod() , 以及 bk_is_square_free_mod().

被这些函数引用 bk_is_square_free_mod() , 以及 bk_is_suitable_prime().

函数调用图:

这是这个函数的调用关系图:

bk_is_suitable_prime()

bool LMCAS::berlekamp_detail::bk_is_suitable_prime	(	const Polynomial< Rational > &	poly,
		int64_t	prime )

判断素数是否保持多项式次数和无平方性质。

Berlekamp 分解要求模约化仍位于同一次数的多项式环中，并且 gcd(f mod p, f' mod p) 为常数。显式和自动素数选择共用此检查。

参数

[in]	poly	非零有理系数多项式，次数 >= 1。
[in]	prime	候选模数。

返回

候选为内核支持的素数且满足分解前置条件时返回 true。

在文件 berlekamp_modular.cpp 第 235 行定义.

                   {
    if (poly.is_zero() || poly.degree() < 1 ||
        prime < 2 ||
        prime > std::numeric_limits<std::int64_t>::max() / prime ||
        !lmmp_is_prime_ulong_(static_cast<ulong>(prime))) {
        return false;
    }
 
    auto reduced = bk_reduce_to_mod_coeffs(poly, prime);
    if (static_cast<int>(reduced.size()) - 1 != poly.degree()) {
        return false;
    }
    return bk_is_square_free_mod(reduced, prime);
}

引用了 bk_is_square_free_mod(), bk_is_suitable_prime(), bk_reduce_to_mod_coeffs(), LMCAS::Polynomial< CoeffType >::degree(), LMCAS::Polynomial< CoeffType >::is_zero() , 以及 LMCAS::prime.

被这些函数引用 LMCAS::berlekamp_factor(), bk_is_suitable_prime() , 以及 bk_select_prime().

函数调用图:

这是这个函数的调用关系图:

bk_mod_inverse()

int64_t LMCAS::berlekamp_detail::bk_mod_inverse	(	int64_t	a,
		int64_t	p )

模 p 下求乘法逆元.

使用扩展欧几里得算法计算 a^(-1) mod p.

参数

[in]	a	待求逆的值(非零)
[in]	p	素数模数

返回

a 在模 p 下的逆元

在文件 berlekamp_modular.cpp 第 111 行定义.

                                             {
    int64_t s, t;
    extended_gcd(((a % p) + p) % p, p, s, t);
    return ((s % p) + p) % p;
}

引用了 LMCAS::a, bk_mod_inverse(), LMCAS::extended_gcd() , 以及 LMCAS::t.

被这些函数引用 LMCAS::berlekamp_factor(), bk_div_mod(), bk_eliminate_column(), bk_gcd_mod() , 以及 bk_mod_inverse().

函数调用图:

这是这个函数的调用关系图:

bk_null_space()

std::vector< std::vector< int64_t > > LMCAS::berlekamp_detail::bk_null_space	(	const std::vector< std::vector< int64_t > > &	Q,
		int64_t	p )

< 当前自由变量取 1，其余自由变量取 0。

由行简化阶梯形回代约束分量。 M[row][pc] = 1，故 x[pc] + sum_{自由列 j} M[row][j] * x[j] = 0， 当前基向量满足 x[pc] = -M[row][col] mod p。

在文件 berlekamp_basis.cpp 第 184 行定义.

               {
 
    int n = static_cast<int>(Q.size());
    if (n == 0) {
        return {};
    }
    std::vector<std::vector<int64_t>> M(n, std::vector<int64_t>(n, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int64_t val = Q[j][i];
            if (i == j) {
                val = (val - 1 + p) % p;
            }
            M[i][j] = val;
        }
    }
    std::vector<int> pivot_col(n, -1);
    std::vector<int> pivot_row(n, -1);
 
    bk_reduce_matrix(M, p, pivot_col, pivot_row);
    std::vector<std::vector<int64_t>> basis;
 
    for (int col = 0; col < n; ++col) {
        if (pivot_row[col] != -1) {
            continue;
        }
 
        std::vector<int64_t> vec(n, 0);
        vec[col] = 1;  /**< 当前自由变量取 1，其余自由变量取 0。 */
 
        for (int row = 0; row < n; ++row) {
            int pc = pivot_col[row];
            if (pc == -1) continue;
            /**
             * @brief 由行简化阶梯形回代约束分量。
             * M[row][pc] = 1，故 x[pc] + sum_{自由列 j} M[row][j] * x[j] = 0，
             * 当前基向量满足 x[pc] = -M[row][col] mod p。
             */
            vec[pc] = (p - M[row][col]) % p;
        }
 
        basis.push_back(std::move(vec));
    }
 
    return basis;
}

引用了 LMCAS::basis, bk_null_space() , 以及 bk_reduce_matrix().

被这些函数引用 LMCAS::berlekamp_factor() , 以及 bk_null_space().

函数调用图:

这是这个函数的调用关系图:

bk_poly_mul_mod()

std::vector< int64_t > LMCAS::berlekamp_detail::bk_poly_mul_mod ( const std::vector< int64_t > & a, const std::vector< int64_t > & b, const std::vector< int64_t > & f, int64_t p )

static

在 F_p 上计算 a(x) * b(x) mod f(x)。

参数

[in]	a	第一个多项式系数向量(升幂排列)
[in]	b	第二个多项式系数向量(升幂排列)
[in]	f	模多项式系数向量(首一,升幂排列)
[in]	p	素数模数

返回

a * b mod f 的系数向量

在文件 berlekamp_basis.cpp 第 17 行定义.

               {
 
    if (a.empty() || b.empty()) {
        return {};
    }
    size_t prod_size = a.size() + b.size() - 1;
    std::vector<int64_t> product(prod_size, 0);
 
    for (size_t i = 0; i < a.size(); ++i) {
        if (a[i] == 0) continue;
        for (size_t j = 0; j < b.size(); ++j) {
            product[i + j] = (product[i + j] + a[i] * b[j]) % p;
            if (product[i + j] < 0) product[i + j] += p;
        }
    }
 
    std::vector<int64_t> q, r;
    bk_div_mod(product, f, p, q, r);
 
    return r;
}

引用了 LMCAS::a, LMCAS::b, bk_div_mod(), bk_poly_mul_mod() , 以及 LMCAS::r.

被这些函数引用 bk_build_q_matrix(), bk_poly_mul_mod() , 以及 bk_poly_pow_mod().

函数调用图:

这是这个函数的调用关系图:

bk_poly_pow_mod()

std::vector< int64_t > LMCAS::berlekamp_detail::bk_poly_pow_mod ( const std::vector< int64_t > & base, int64_t exp, const std::vector< int64_t > & f, int64_t p )

static

在 F_p 上用平方乘法计算 base^exp mod f(x)。

参数

[in]	base	底多项式系数向量(升幂排列)
[in]	exp	指数(非负整数)
[in]	f	模多项式系数向量(首一,升幂排列)
[in]	p	素数模数

返回

base^exp mod f 的系数向量

参见

Berlekamp, E.R. "Factoring polynomials over finite fields."

在文件 berlekamp_basis.cpp 第 55 行定义.

               {
 
    if (exp == 0) {
        return {1};
    }
 
    if (exp == 1) {
        std::vector<int64_t> q, r;
        bk_div_mod(base, f, p, q, r);
        return r;
    }
    std::vector<int64_t> result = {1};
    std::vector<int64_t> cur = base;
    {
        std::vector<int64_t> q, r;
        bk_div_mod(cur, f, p, q, r);
        cur = std::move(r);
    }
 
    int64_t e = exp;
    while (e > 0) {
        if (e & 1) {
            result = bk_poly_mul_mod(result, cur, f, p);
        }
        e >>= 1;
        if (e > 0) {
            cur = bk_poly_mul_mod(cur, cur, f, p);
        }
    }
 
    return result;
}

引用了 bk_div_mod(), bk_poly_mul_mod(), bk_poly_pow_mod(), LMCAS::e(), LMCAS::exp() , 以及 LMCAS::r.

被这些函数引用 bk_build_q_matrix() , 以及 bk_poly_pow_mod().

函数调用图:

这是这个函数的调用关系图:

bk_reduce_matrix()

void LMCAS::berlekamp_detail::bk_reduce_matrix ( std::vector< std::vector< int64_t > > & M, int64_t p, std::vector< int > & pivot_col, std::vector< int > & pivot_row )

static

在文件 berlekamp_basis.cpp 第 156 行定义.

                                                                                   {
    const int n = static_cast<int>(M.size());
    int current_row = 0;
    for (int col = 0; col < n && current_row < n; ++col) {
        int pivot = -1;
        for (int row = current_row; row < n; ++row) {
            if (M[row][col] != 0) {
                pivot = row;
                break;
            }
        }
 
        if (pivot == -1) {
            continue;
        }
 
        if (pivot != current_row) {
            std::swap(M[pivot], M[current_row]);
        }
 
        pivot_col[current_row] = col;
        pivot_row[col] = current_row;
        bk_eliminate_column(M, current_row, col, p);
        ++current_row;
    }
}

引用了 bk_eliminate_column() , 以及 bk_reduce_matrix().

被这些函数引用 bk_null_space() , 以及 bk_reduce_matrix().

函数调用图:

这是这个函数的调用关系图:

bk_reduce_to_mod_coeffs()

std::vector< int64_t > LMCAS::berlekamp_detail::bk_reduce_to_mod_coeffs	(	const Polynomial< Rational > &	poly,
		int64_t	p )

以系数分母的 LCM 清除分母，再逐项取模 p。

参数

[in]	poly	有理系数多项式
[in]	p	素数模数

返回

升幂排列的模 p 系数向量，去除高次零系数。

在文件 berlekamp_modular.cpp 第 29 行定义.

               {
 
    if (poly.is_zero()) {
        return {};
    }
 
    BigInt lcm_den(1);
    for (const auto& c : poly.coeffs) {
        BigInt den = c.get_denominator();
        BigInt g = BigInt::gcd(lcm_den, den);
        lcm_den = lcm_den * (den / g);
    }
 
    BigInt big_p(static_cast<std::int64_t>(p));
 
    std::vector<int64_t> mod_coeffs;
    mod_coeffs.reserve(poly.coeffs.size());
 
    for (const auto& c : poly.coeffs) {
        BigInt num = c.get_numerator();
        BigInt den = c.get_denominator();
        BigInt integer_coeff = num * (lcm_den / den);
 
        BigInt rem = integer_coeff % big_p;
        int64_t rem_val = rem.try_to_int64().value();
        if (rem_val < 0) rem_val += p;
 
        mod_coeffs.push_back(rem_val);
    }
 
    while (!mod_coeffs.empty() && mod_coeffs.back() == 0) {
        mod_coeffs.pop_back();
    }
 
    return mod_coeffs;
}

引用了 bk_reduce_to_mod_coeffs(), LMCAS::c, LMCAS::Polynomial< CoeffType >::coeffs, LMCAS::Polynomial< CoeffType >::is_zero() , 以及 LMCAS::polynomial_solver_detail::num().

被这些函数引用 LMCAS::berlekamp_factor(), bk_is_suitable_prime() , 以及 bk_reduce_to_mod_coeffs().

函数调用图:

这是这个函数的调用关系图:

bk_select_prime()

int64_t LMCAS::berlekamp_detail::bk_select_prime

(

const Polynomial< Rational > &

poly

)

从小素数表中选取适合 Berlekamp 分解的素数。

参数

[in]

poly

非零有理系数多项式，次数 >= 1。

返回

首个合适的素数 p；候选均不满足时返回 -1。

在文件 berlekamp_modular.cpp 第 258 行定义.

                                                          {
    if (poly.is_zero() || poly.degree() < 1) {
        return -1;
    }
    for (size_t i = 0; i < BK_NUM_SMALL_PRIMES; ++i) {
        if (bk_is_suitable_prime(poly, BK_SMALL_PRIMES[i])) {
            return BK_SMALL_PRIMES[i];
        }
    }
    return -1;
}

引用了 bk_is_suitable_prime(), BK_NUM_SMALL_PRIMES, bk_select_prime(), BK_SMALL_PRIMES, LMCAS::Polynomial< CoeffType >::degree() , 以及 LMCAS::Polynomial< CoeffType >::is_zero().

被这些函数引用 LMCAS::berlekamp_factor() , 以及 bk_select_prime().

函数调用图:

这是这个函数的调用关系图:

bk_split_factors()

std::vector< std::vector< int64_t > > LMCAS::berlekamp_detail::bk_split_factors	(	const std::vector< int64_t > &	f_coeffs,
		const std::vector< std::vector< int64_t > > &	null_basis,
		int	null_dim,
		int64_t	p )

在文件 berlekamp_split.cpp 第 40 行定义.

               {
 
    std::vector<std::vector<int64_t>> factor_list;
    factor_list.push_back(f_coeffs);
 
    for (const auto& basis_vec : null_basis) {
        bool is_trivial = true;
        if (!basis_vec.empty() && basis_vec[0] == 1) {
            for (size_t i = 1; i < basis_vec.size(); ++i) {
                if (basis_vec[i] != 0) {
                    is_trivial = false;
                    break;
                }
            }
        } else {
            is_trivial = false;
        }
        if (is_trivial) continue;
 
        if (static_cast<int>(factor_list.size()) >= null_dim) break;
        std::vector<int64_t> v_poly = basis_vec;
        while (!v_poly.empty() && v_poly.back() == 0) {
            v_poly.pop_back();
        }
        for (size_t fi = 0; fi < factor_list.size(); ++fi) {
            if (static_cast<int>(factor_list.size()) >= null_dim) break;
            if (factor_list[fi].size() <= 2) continue;
            bk_split_one_factor(factor_list, fi, v_poly, null_dim, p);
        }
    }
    return factor_list;
}

引用了 bk_split_factors() , 以及 bk_split_one_factor().

被这些函数引用 LMCAS::berlekamp_factor() , 以及 bk_split_factors().

函数调用图:

这是这个函数的调用关系图:

bk_split_one_factor()

bool LMCAS::berlekamp_detail::bk_split_one_factor ( std::vector< std::vector< int64_t > > & factor_list, size_t fi, const std::vector< int64_t > & v_poly, int null_dim, int64_t p )

static

在文件 berlekamp_split.cpp 第 7 行定义.

                                                         {
    for (int64_t c = 0; c < p; ++c) {
        if (static_cast<int>(factor_list.size()) >= null_dim) return false;
        std::vector<int64_t> v_minus_c = v_poly;
        if (v_minus_c.empty()) {
            v_minus_c.push_back((p - c) % p);
        } else {
            v_minus_c[0] = (v_minus_c[0] - c % p + p) % p;
        }
        while (!v_minus_c.empty() && v_minus_c.back() == 0) {
            v_minus_c.pop_back();
        }
 
        if (v_minus_c.empty()) continue;
        std::vector<int64_t> h = bk_gcd_mod(factor_list[fi], v_minus_c, p);
        int deg_h = static_cast<int>(h.size()) - 1;
        int deg_g = static_cast<int>(factor_list[fi].size()) - 1;
 
        if (deg_h > 0 && deg_h < deg_g) {
            std::vector<int64_t> quotient, remainder;
            bk_div_mod(factor_list[fi], h, p, quotient, remainder);
 
            factor_list[fi] = h;
            factor_list.push_back(quotient);
 
            return true;
        }
    }
    return false;
}

引用了 bk_div_mod(), bk_gcd_mod(), bk_split_one_factor() , 以及 LMCAS::c.

被这些函数引用 bk_split_factors() , 以及 bk_split_one_factor().

函数调用图:

这是这个函数的调用关系图:

变量说明

BK_NUM_SMALL_PRIMES

size_t LMCAS::berlekamp_detail::BK_NUM_SMALL_PRIMES

staticconstexpr

初始值:

                                        =
sizeof(BK_SMALL_PRIMES) / sizeof(BK_SMALL_PRIMES[0])

在文件 berlekamp_modular.cpp 第 19 行定义.

被这些函数引用 bk_select_prime().

BK_SMALL_PRIMES

int64_t LMCAS::berlekamp_detail::BK_SMALL_PRIMES[]

staticconstexpr

初始值:

                                         = {
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
    31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
    73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
    127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
    179, 181, 191, 193, 197, 199, 211, 223, 227, 229
}

Berlekamp 模分解的小素数候选表。 按升序选取首个不整除首项系数且使模约化结果无平方因子的素数。

在文件 berlekamp_modular.cpp 第 12 行定义.

被这些函数引用 bk_select_prime().