LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
is_prime.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_IS_PRIME_H__
24#define __LMMP_IS_PRIME_H__
25
26#include "lmmp/numth.h"
27
28/*
29 from http://probableprime.org/download/example-primality.c
30 Deterministic Miller-Rabin tests for 64-bit.
31 Hashed 2-bases for n < 684630005672341 (slightly more than 2^49)
32 Hashed 3-bases for n < 2^64
33
34 Based on Steve Worley's 2^32 example:
35 http://www.mersenneforum.org/showthread.php?t=12209
36 With a 3-base encoding idea from Bradley Berg.
37
38 Copyright 2014, Dana Jacobsen <[email protected]>
39
40 表定义在 is_prime_table.c(单副本,extern 避免各编译单元重复实体)。
41*/
42
43/* 4kb hash table:dj_base49[h] + 3 为第二基底,h = hash(n),确定性覆盖 n < 2^49.3 */
44extern const uint16_t dj_base49[2048];
45
46/* 32kb hash table:dj_base64[h] 编码 2/3 基底(bit15 选大基底,低 15 位 + 3 为第三基底) */
47extern const uint16_t dj_base64[16384];
48
49/**
50 * @brief u32 档双基底强伪素数内核(基底 2 + dj_base49 哈希基底,普通域免蒙域算术)
51 * @param n 待判断的数
52 * @warning n>2, n%2==1
53 * @note 建议调用前已过 3,5,7,11 试除(内部不试除);
54 * 供 lmmp_is_prime_uint_ 与 lmmp_is_prime_ulong_notrial_ 的 n≤2^32-1 档共享;
55 * 判定集合与 mont63 双链旧实现精确一致(同基底同强 MR 语义)
56 * @return 若 n 为素数,返回 true,否则返回 false
57 */
59
60#endif // __LMMP_IS_PRIME_H__
const uint16_t dj_base49[2048]
Copyright (C) 2026 HJimmyK (Jericho Knox)
const uint16_t dj_base64[16384]
bool lmmp_is_prime_uint_notrial_(uint n)
u32 档双基底强伪素数内核(基底 2 + dj_base49 哈希基底,普通域免蒙域算术)
#define LMMP_NOINLINE
定义 lmmp.h:216
#define n
uint32_t uint
定义 numth.h:38