| line |
stmt |
bran |
cond |
sub |
pod |
time |
code |
|
1
|
|
|
|
|
|
|
#ifndef MPU_PRIMALITY_H |
|
2
|
|
|
|
|
|
|
#define MPU_PRIMALITY_H |
|
3
|
|
|
|
|
|
|
|
|
4
|
|
|
|
|
|
|
#include "ptypes.h" |
|
5
|
|
|
|
|
|
|
|
|
6
|
|
|
|
|
|
|
extern int is_pseudoprime(UV const n, UV a); |
|
7
|
|
|
|
|
|
|
extern int is_euler_pseudoprime(UV const n, UV a); |
|
8
|
|
|
|
|
|
|
extern int is_euler_plumb_pseudoprime(UV const n); |
|
9
|
|
|
|
|
|
|
extern int miller_rabin(UV const n, const UV *bases, int nbases); |
|
10
|
|
|
|
|
|
|
extern void lucas_seq(UV* U, UV* V, UV* Qk, UV n, IV P, IV Q, UV k); |
|
11
|
|
|
|
|
|
|
extern int is_lucas_pseudoprime(UV n, int strength); |
|
12
|
|
|
|
|
|
|
extern int is_almost_extra_strong_lucas_pseudoprime(UV n, UV increment); |
|
13
|
|
|
|
|
|
|
extern int is_frobenius_pseudoprime(UV n, IV P, IV Q); |
|
14
|
|
|
|
|
|
|
extern int is_frobenius_underwood_pseudoprime(UV n); |
|
15
|
|
|
|
|
|
|
extern int is_frobenius_khashin_pseudoprime(UV n); |
|
16
|
|
|
|
|
|
|
extern int is_perrin_pseudoprime(UV n, int restricted); |
|
17
|
|
|
|
|
|
|
extern int is_mersenne_prime(UV p); |
|
18
|
|
|
|
|
|
|
extern int lucas_lehmer(UV p); |
|
19
|
|
|
|
|
|
|
extern int lucasu(IV* U, IV P, IV Q, UV k); |
|
20
|
|
|
|
|
|
|
extern int lucasv(IV* V, IV P, IV Q, UV k); |
|
21
|
|
|
|
|
|
|
|
|
22
|
|
|
|
|
|
|
#if defined(FUNC_is_strong_pseudoprime) |
|
23
|
77802
|
|
|
|
|
|
static int is_strong_pseudoprime(UV n, UV base) { |
|
24
|
77802
|
|
|
|
|
|
return miller_rabin(n, &base, 1); |
|
25
|
|
|
|
|
|
|
} |
|
26
|
|
|
|
|
|
|
#endif |
|
27
|
|
|
|
|
|
|
|
|
28
|
|
|
|
|
|
|
extern int BPSW(UV const n); |
|
29
|
|
|
|
|
|
|
extern int MR32(uint32_t n); |
|
30
|
|
|
|
|
|
|
|
|
31
|
|
|
|
|
|
|
/* General purpose primality test. Does small-prime divisibility. */ |
|
32
|
|
|
|
|
|
|
extern int is_prob_prime(UV n); |
|
33
|
|
|
|
|
|
|
|
|
34
|
|
|
|
|
|
|
/* General purpose primality test without small divisibility tests. */ |
|
35
|
|
|
|
|
|
|
#if BITS_PER_WORD == 32 |
|
36
|
|
|
|
|
|
|
#define is_def_prime(n) MR32(n) |
|
37
|
|
|
|
|
|
|
#else |
|
38
|
|
|
|
|
|
|
#define is_def_prime(n) ((n <= 4294967295U) ? MR32(n) : BPSW(n)) |
|
39
|
|
|
|
|
|
|
#endif |
|
40
|
|
|
|
|
|
|
|
|
41
|
|
|
|
|
|
|
#endif |