File Coverage

factor.h

Criterion	Covered	Total	%
statement	2	2	100.0
branch			n/a
condition			n/a
subroutine			n/a
pod			n/a
total	2	2	100.0

line	stmt	code
1		#ifndef MPU_FACTOR_H
2		#define MPU_FACTOR_H
3
4		#include "ptypes.h"
5
6		#if BITS_PER_WORD == 64
7		#define MPU_MAX_FACTORS 64
8		#define MPU_MAX_DFACTORS 15
9		#else
10		#define MPU_MAX_FACTORS 32
11		#define MPU_MAX_DFACTORS 9
12		#endif
13
14		/* These all return the number of factors set in factors[].
15		* Nothing found: returns 1 and factors[0] = n
16		* One factor found: returns 2 and factors[0] = f, factors[1] = n/f
17		* ...
18		*/
19
20		extern int factor(UV n, UV *factors);
21		extern int factor_one(UV n, UV *factors, bool primality, bool trial);
22
23		typedef struct {
24		UV n;
25		UV f[MPU_MAX_DFACTORS];
26		uint8_t e[MPU_MAX_DFACTORS];
27		uint16_t nfactors;
28		} factored_t;
29		extern void factorintp(factored_t *nf, UV n);
30
31		extern void factoredp_validate(const factored_t *nf);
32		extern uint32_t factoredp_total_factors(const factored_t *nf);
33		extern bool factoredp_is_square_free(const factored_t *nf);
34		extern signed char factoredp_moebius(const factored_t *nf);
35		extern uint32_t factoredp_linear_factors(UV fac[], const factored_t *nf);
36
37	587	static INLINE factored_t factorint(UV n)
38	587	{ factored_t nf; factorintp(&nf, n); return nf; }
39		static INLINE void factored_validate(const factored_t nf)
40		{ factoredp_validate(&nf); }
41		static INLINE uint32_t factored_total_factors(const factored_t nf)
42		{ return factoredp_total_factors(&nf); }
43		static INLINE bool factored_is_square_free(const factored_t nf)
44		{ return factoredp_is_square_free(&nf); }
45		static INLINE signed char factored_moebius(const factored_t nf)
46		{ return factoredp_moebius(&nf); }
47		static INLINE uint32_t factored_linear_factors(UV fac[], const factored_t nf)
48		{ return factoredp_linear_factors(fac, &nf); }
49
50		extern int trial_factor(UV n, UV *factors, UV first, UV last);
51		extern int fermat_factor(UV n, UV *factors, UV rounds);
52		extern int holf_factor(UV n, UV *factors, UV rounds);
53		extern int pbrent_factor(UV n, UV *factors, UV maxrounds, UV a);
54		extern int prho_factor(UV n, UV *factors, UV maxrounds);
55		extern int pminus1_factor(UV n, UV *factors, UV B1, UV B2);
56		extern int pplus1_factor(UV n, UV *factors, UV B);
57		extern int squfof_factor(UV n, UV *factors, UV rounds);
58		extern int lehman_factor(UV n, UV *factors, bool dotrial);
59		extern int cheb_factor(UV n, UV *factors, UV B, UV initx);
60
61		extern UV* divisor_list(UV n, UV *num_divisors, UV maxd);
62
63		extern UV divisor_sum(UV n, UV k);
64
65		extern int prime_omega(UV n); /* number of distinct prime factors */
66		extern int prime_bigomega(UV n); /* number of prime factors w/ multiplicity */
67		/* bigomega => with_multiplicity=1 omega => with_multiplicity=0 */
68		extern unsigned char* range_nfactor_sieve(UV lo, UV hi, bool with_multiplicity);
69
70		/* Factoring all numbers in a range. */
71		typedef struct {
72		UV lo;
73		UV hi;
74		UV n;
75		bool is_square_free;
76		UV *factors;
77		UV _coffset;
78		UV _noffset;
79		UV *_farray;
80		UV *_nfactors;
81		} factor_range_context_t;
82		extern factor_range_context_t factor_range_init(UV lo, UV hi, bool square_free);
83		extern int factor_range_next(factor_range_context_t *ctx);
84		extern void factor_range_destroy(factor_range_context_t *ctx);
85
86		/*
87		extern UV dlp_trial(UV a, UV g, UV p, UV maxrounds);
88		extern UV dlp_prho(UV a, UV g, UV p, UV n, UV maxrounds);
89		extern UV dlp_bsgs(UV a, UV g, UV p, UV n, UV maxent);
90		*/
91		/* Generic znlog returns k that solves a = g^k mod p */
92		extern UV znlog(UV a, UV g, UV p);
93		/* znlog given prime gorder = znorder(g,p) */
94		extern UV znlog_solve(UV a, UV g, UV p, UV gorder);
95
96		#endif