hensel_lift.cpp 文件参考

Hensel 提升算法实现:Mignotte 界计算与二次提升. 更多...

#include "exact_factorization.hpp"
#include "internal/exact_factorization_support.hpp"
#include <vector>
#include <cstdint>
#include <cmath>
#include <algorithm>
#include <exception>

hensel_lift.cpp 的引用(Include)关系图:

浏览该文件的源代码.

命名空间
namespace	LMCAS

函数
HenselLiftResult	LMCAS::hensel_lift_checked (const Polynomial< BigInt > &poly, const std::vector< Polynomial< ModInt > > &mod_factors, int64_t prime, int lift_bound)
	Hensel 提升:将模 p 因子提升到 mod p^k.
static BigInt	LMCAS::hl_binomial (int n, int k)
	计算二项式系数 C(n, k).
static bool	LMCAS::hl_coeff_vectors_equal (std::vector< BigInt > left, std::vector< BigInt > right)
static int	LMCAS::hl_compute_lift_height (const Polynomial< BigInt > &poly, int64_t prime)
	计算 Hensel 提升所需的高度 k.
static std::pair< std::vector< BigInt >, std::vector< BigInt > >	LMCAS::hl_extended_gcd_poly (const std::vector< BigInt > &g, const std::vector< BigInt > &h, const BigInt &m)
	计算两个多项式在模 m 下的扩展 GCD 的 Bezout 系数.
static bool	LMCAS::hl_is_prime (int64_t value)
static BigInt	LMCAS::hl_l2_norm_squared (const Polynomial< BigInt > &poly)
	计算多项式系数的 L2 范数的平方.
static BigInt	LMCAS::hl_mignotte_bound (const Polynomial< BigInt > &poly)
	计算多项式的 Mignotte 界.
static BigInt	LMCAS::hl_mod_inverse (const BigInt &a, const BigInt &m)
	计算 BigInt 在模 m 下的乘法逆元.
static std::vector< std::vector< BigInt > >	LMCAS::hl_multi_factor_lift (const std::vector< BigInt > &f, const std::vector< std::vector< BigInt > > &factors, int64_t prime, int target_k)
	多因子 Hensel 提升:将 k 个模 p 因子同时提升到 mod p^target_k.
static std::vector< BigInt >	LMCAS::hl_poly_add_mod (const std::vector< BigInt > &a, const std::vector< BigInt > &b, const BigInt &m)
	多项式加法(BigInt 系数),结果模 m 归约.
static std::pair< std::vector< BigInt >, std::vector< BigInt > >	LMCAS::hl_poly_divmod (const std::vector< BigInt > &a, const std::vector< BigInt > &b, const BigInt &m)
	多项式带余除法(BigInt 系数),模 m 下运算.
static std::vector< BigInt >	LMCAS::hl_poly_mul_mod (const std::vector< BigInt > &a, const std::vector< BigInt > &b, const BigInt &m)
	多项式乘法(BigInt 系数),结果模 m 归约.
static std::vector< BigInt >	LMCAS::hl_poly_sub_mod (const std::vector< BigInt > &a, const std::vector< BigInt > &b, const BigInt &m)
	多项式减法(BigInt 系数),结果模 m 归约.
static void	LMCAS::hl_reduce_coeffs (std::vector< BigInt > &poly, const BigInt &m)
	对多项式系数向量执行模归约(对称表示).
HenselLiftPair	LMCAS::hl_two_factor_lift (const std::vector< BigInt > &f, const HenselLiftPair &current)
	执行一步二次 Hensel 提升:mod m -> mod m^2.
static Result< void >	LMCAS::hl_validate_lift_inputs (const Polynomial< BigInt > &poly, const std::vector< std::vector< BigInt > > &factor_vecs, int64_t prime)

详细描述

Hensel 提升算法实现:Mignotte 界计算与二次提升.

本文件实现 Phase 4(Hensel 提升)的核心逻辑:

• Mignotte 界计算:确定提升高度 k 使得 p^k 足以恢复真因子系数
• 二次 Hensel 提升:将模 p 因子逐步提升到 mod p^k
• 多因子提升:通过二叉树结构递归配对提升

参见

Mignotte, M. "An inequality about factors of polynomials." Mathematics of Computation, 28(128), 1974.

Zassenhaus, H. "On Hensel factorization, I." Journal of Number Theory, 1(3), 1969.

在文件 hensel_lift.cpp 中定义.