LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
prime_pool.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_PERF_PRIME_POOL_H
24#define LMMP_PERF_PRIME_POOL_H
25
26#include "support/perf.h"
27#include "lmmp/lmmpn.h"
28#include "lmmp/numth.h"
29
30/*
31 素性检验的输入池:单次判定成本对输入性质极度敏感(小因子合数
32 试除即拒、素数全基底执行),故以池轮转代替单输入,保证测得
33 目标总体的齐次负载:
34 ODD 随机奇数(合数为主,平均负载)
35 PRIME 素数(全轮完整执行的最坏情形)
36 COPRIME 试除幸存者(无 <=1000 素因子;强 Lucas 对含小因子输入
37 经 Jacobi gcd 提前退出,且 measure 取最小值会被任一
38 快速元素掩盖,须过滤到试除上界之上保证池内齐次)
39*/
40
42
43enum { POOL = 512 };
44
45static inline int pool_cnt(mp_size_t n) { return n <= 64 ? 32 : 8; }
46
47/**
48 * @brief COPRIME 输入池的预筛
49 * @note 与 <=1000 素数之积取 gcd,gcd!=1 等价于存在 <=1000 素因子(池元素
50 * 恒奇,素数 2 无关)
51 */
52static inline bool small_factor_q(mp_srcptr x, mp_size_t n) {
53 static mp_ptr pr = NULL;
54 static mp_size_t prn = 0;
55 if (pr == NULL) {
56 mp_size_t need = lmmp_primefac_size_(1000);
57 pr = alloc_limbs(need);
58 prn = lmmp_primefac_(pr, need, 1000);
59 }
60 mp_ptr g = alloc_limbs(prn);
61 mp_size_t gn = (n >= prn) ? lmmp_gcd_(g, x, n, pr, prn) : lmmp_gcd_(g, pr, prn, x, n);
62 bool has = !(gn == 1 && g[0] == 1);
63 lmmp_free(g);
64 return has;
65}
66
67/* n limbs 归一化奇数池(元素个数 cnt) */
68static inline mp_ptr pool_n(mp_size_t n, int cnt, mp_limb_t seed, PrimePool kind) {
69 mp_ptr a = alloc_limbs((size_t)n * cnt);
70 for (int i = 0; i < cnt; i++) {
71 mp_ptr cur = a + n * i;
72 lmmp_seed_random_(cur, n, seed + i * 131, 1);
73 cur[n - 1] |= (mp_limb_t)1 << 63;
74 cur[0] |= 1;
75 if (kind == PRIME_POOL_COPRIME) {
76 while (small_factor_q(cur, n)) cur[0] += 2;
77 } else if (kind == PRIME_POOL_PRIME) {
78 while (lmmp_is_prime_n_(cur, n, 4) == 0) cur[0] += 2;
79 }
80 }
81 return a;
82}
83
84#endif
mp_limb_t * mp_ptr
定义 lmmp.h:96
uint64_t mp_size_t
定义 lmmp.h:93
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
uint64_t mp_limb_t
定义 lmmp.h:92
mp_size_t lmmp_seed_random_(mp_ptr dst, mp_size_t n, mp_limb_t seed, unsigned seed_type)
生成随机大整数(0 - B^n-1 均匀分布)
#define n
mp_size_t lmmp_primefac_size_(uint n)
计算质数阶乘的 limb 缓冲区长度
mp_size_t lmmp_gcd_(mp_ptr dst, mp_srcptr up, mp_size_t un, mp_srcptr vp, mp_size_t vn)
计算两个无符号整数的最大公约数(通用分发入口)
定义 gcd.c:27
mp_size_t lmmp_primefac_(mp_ptr dst, mp_size_t rn, uint n)
计算质数阶乘(不超过n的质数累乘)
int lmmp_is_prime_n_(mp_srcptr np, mp_size_t nn, int strength)
大整数素性检验(强度分档,大于 128 位)
static mp_ptr pool_n(mp_size_t n, int cnt, mp_limb_t seed, PrimePool kind)
static bool small_factor_q(mp_srcptr x, mp_size_t n)
COPRIME 输入池的预筛
static int pool_cnt(mp_size_t n)
PrimePool
Copyright (C) 2026 HJimmyK (Jericho Knox)
@ PRIME_POOL_PRIME
@ PRIME_POOL_ODD
@ PRIME_POOL_COPRIME
@ POOL