LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
trialdiv.h
浏览该文件的文档.
1/**
2 * Copyright (C) 2026 HJimmyK (Jericho Knox)
3 *
4 * This file is part of LMMP.
5 *
6 * LMMP is free software: you can redistribute it and/or modify it
7 * under the terms of the GNU Lesser General Public License as
8 * published by the Free Software Foundation; either version 3 of
9 * the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library. If not, see
18 * <https://www.gnu.org/licenses/>.
19 *
20 * SPDX-License-Identifier: LGPL-3.0-or-later
21 */
22
23#ifndef __LMMP_TRIALDIV_H__
24#define __LMMP_TRIALDIV_H__
25
26#include "lmmp/numth.h"
27#include "lmmp/lmmpn.h"
28
29/**
30 * @brief 试除法:判定 [np,nn] 是否存在小奇素数因子
31 * @param np 被除数(长度为 nn 个limb)
32 * @param nn 被除数的 limb 长度
33 * @param N 试除上界提示
34 * @warning np!=NULL, nn>0
35 * @note 试除素数自 3 起(因子 2 由调用方自理);N 仅为上界提示——实际试除
36 * 范围为所有含 <=N 素数的块之并(块粒度向上取整,可能试除 N 之后的
37 * 素数),需要精确 N 边界者勿用
38 * @return 存在能整除 [np,nn] 的试除素数则返回true,否则返回false
39 */
41
42/* 全局试除块表释放(lmmp_global_entries 钩子;表本身首次试除时惰性构建) */
44
45/**
46 * @brief 4 链折叠取模:r = [numa,na] mod d
47 * @param numa 被除数(长度为 na 个limb)
48 * @param na 被除数的 limb 长度
49 * @param d 除数(单个 limb)
50 * @param dinv 除数的逆元(d*dinv==1 mod 2^64)
51 * @param r2 蒙域预处理(r2=B^2 mod d)
52 * @param base 蒙域预处理(base=B mod d)
53 * @param mi 蒙域预处理(mi=-dinv mod 2^64)
54 * @warning na>0, numa!=NULL, d%2==1, d<2^63, d*dinv==1 mod 2^64,
55 * dinv+mi==0 (mod B), r2=B^2 mod d, base=B mod d
56 * @return [numa,na] mod d
57 */
60
61/**
62 * @brief 8 链折叠取模:r = [numa,na] mod d
63 * @param numa 被除数(长度为 na 个limb)
64 * @param na 被除数的 limb 长度
65 * @param d 除数(单个 limb)
66 * @param dinv 除数的逆元(d*dinv==1 mod 2^64)
67 * @param r2 蒙域预处理(r2=B^2 mod d)
68 * @param base 蒙域预处理(base=B mod d)
69 * @param mi 蒙域预处理(mi=-dinv mod 2^64)
70 * @warning na>0, numa!=NULL, d%2==1, d<2^63, d*dinv==1 mod 2^64,
71 * dinv+mi==0 (mod B), r2=B^2 mod d, base=B mod d
72 * @return [numa,na] mod d
73 */
76
77// 3,5,7,11的余数掩码表
78extern const mp_limb_t r35711_mask_map[19];
79
80/**
81 * @brief 校验是否能被3,5,7,11整除,能够整除则返回1,否则返回0
82 */
83static inline int trial_div35711(ulong n) {
84 uint rem = n % 1155; // 1155 = 3 * 5 * 7 * 11
85 uint idx = rem / LIMB_BITS;
86 uint bit = rem % LIMB_BITS;
87 return (r35711_mask_map[idx] >> bit) & 1ULL;
88}
89
90#endif /* __LMMP_TRIALDIV_H__ */
uint64_t mp_size_t
定义 lmmp.h:93
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
uint64_t mp_limb_t
定义 lmmp.h:92
#define LIMB_BITS
定义 lmmp.h:102
#define r2
#define n
uint32_t uint
定义 numth.h:38
uint16_t ushort
定义 numth.h:36
uint64_t ulong
定义 numth.h:39
static int trial_div35711(ulong n)
校验是否能被3,5,7,11整除,能够整除则返回1,否则返回0
mp_limb_t lmmp_mod_8chunk_1_(mp_srcptr numa, mp_size_t na, mp_limb_t d, mp_limb_t dinv, mp_limb_t r2, mp_limb_t base, mp_limb_t mi)
8 链折叠取模:r = [numa,na] mod d
const mp_limb_t r35711_mask_map[19]
void lmmp_trialdiv_table_free_(void)
bool lmmp_trialdiv_(mp_srcptr np, mp_size_t nn, ushort N)
Copyright (C) 2026 HJimmyK (Jericho Knox)
mp_limb_t lmmp_mod_4chunk_1_(mp_srcptr numa, mp_size_t na, mp_limb_t d, mp_limb_t dinv, mp_limb_t r2, mp_limb_t base, mp_limb_t mi)
4 链折叠取模:r = [numa,na] mod d