LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
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
41
typedef
enum
{
PRIME_POOL_ODD
,
PRIME_POOL_PRIME
,
PRIME_POOL_COPRIME
}
PrimePool
;
42
43
enum
{
POOL
= 512 };
44
45
static
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
*/
52
static
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) */
68
static
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_ptr
mp_limb_t * mp_ptr
定义
lmmp.h:96
mp_size_t
uint64_t mp_size_t
定义
lmmp.h:93
mp_srcptr
const mp_limb_t * mp_srcptr
定义
lmmp.h:97
lmmp_free
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
定义
memory.c:437
mp_limb_t
uint64_t mp_limb_t
定义
lmmp.h:92
lmmpn.h
lmmp_seed_random_
mp_size_t lmmp_seed_random_(mp_ptr dst, mp_size_t n, mp_limb_t seed, unsigned seed_type)
生成随机大整数(0 - B^n-1 均匀分布)
n
#define n
numth.h
lmmp_primefac_size_
mp_size_t lmmp_primefac_size_(uint n)
计算质数阶乘的 limb 缓冲区长度
定义
factorial_extra.c:446
lmmp_gcd_
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
lmmp_primefac_
mp_size_t lmmp_primefac_(mp_ptr dst, mp_size_t rn, uint n)
计算质数阶乘(不超过n的质数累乘)
lmmp_is_prime_n_
int lmmp_is_prime_n_(mp_srcptr np, mp_size_t nn, int strength)
大整数素性检验(强度分档,大于 128 位)
定义
is_prime_n.c:646
perf.h
pool_n
static mp_ptr pool_n(mp_size_t n, int cnt, mp_limb_t seed, PrimePool kind)
定义
prime_pool.h:68
small_factor_q
static bool small_factor_q(mp_srcptr x, mp_size_t n)
COPRIME 输入池的预筛
定义
prime_pool.h:52
pool_cnt
static int pool_cnt(mp_size_t n)
定义
prime_pool.h:45
PrimePool
PrimePool
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
prime_pool.h:41
PRIME_POOL_PRIME
@ PRIME_POOL_PRIME
定义
prime_pool.h:41
PRIME_POOL_ODD
@ PRIME_POOL_ODD
定义
prime_pool.h:41
PRIME_POOL_COPRIME
@ PRIME_POOL_COPRIME
定义
prime_pool.h:41
POOL
@ POOL
定义
prime_pool.h:43
src
lmmp
numth
perf
prime_pool.h
生成于
, 为 LMMP使用
1.18.0