1#![allow(non_camel_case_types)]
2#![allow(non_snake_case)]
3
4use crate::deps::*;
7use crate::flint::*;
8use libc::{c_char, c_int, c_uchar, c_uint};
9
10#[repr(C)]
11#[derive(Debug, Copy, Clone)]
12pub struct pair_s {
13 pub x: mp_limb_t,
14 pub y: mp_limb_t,
15}
16
17pub type n_pair_t = pair_s;
18
19#[repr(C)]
20#[derive(Debug, Copy, Clone)]
21pub struct n_factor_t {
22 pub num: c_int,
23 pub exp: [c_int; 15usize],
24 pub p: [mp_limb_t; 15usize],
25}
26
27#[repr(C)]
28#[derive(Debug, Copy, Clone)]
29pub struct n_primes_struct {
30 pub small_i: mp_limb_signed_t,
31 pub small_num: mp_limb_signed_t,
32 pub small_primes: *mut c_uint,
33 pub sieve_a: mp_limb_t,
34 pub sieve_b: mp_limb_t,
35 pub sieve_i: mp_limb_signed_t,
36 pub sieve_num: mp_limb_signed_t,
37 pub sieve: *mut c_char,
38}
39
40pub type n_primes_t = [n_primes_struct; 1usize];
41
42#[repr(C)]
43#[derive(Debug, Copy, Clone)]
44pub struct n_ecm_s {
45 pub x: mp_limb_t,
46 pub z: mp_limb_t,
47 pub a24: mp_limb_t,
48 pub ninv: mp_limb_t,
49 pub normbits: mp_limb_t,
50 pub one: mp_limb_t,
51 pub GCD_table: *mut c_uchar,
52 pub prime_table: *mut *mut c_uchar,
53}
54
55pub type n_ecm_t = [n_ecm_s; 1usize];
56
57extern "C" {
58 pub fn n_primes_init(iter: *mut n_primes_struct);
59 pub fn n_primes_clear(iter: *mut n_primes_struct);
60 pub fn n_primes_extend_small(iter: *mut n_primes_struct, bound: mp_limb_t);
61 pub fn n_primes_sieve_range(iter: *mut n_primes_struct, a: mp_limb_t, b: mp_limb_t);
62 pub fn n_primes_jump_after(iter: *mut n_primes_struct, n: mp_limb_t);
63 pub fn n_primes_next(iter: *mut n_primes_struct) -> mp_limb_t;
64 pub static mut flint_primes_small: [c_uint; 0usize];
65 pub static mut _flint_primes: [*mut mp_limb_t; 64usize];
66 pub static mut _flint_prime_inverses: [*mut f64; 64usize];
67 pub static mut _flint_primes_used: c_int;
68 pub fn n_compute_primes(num_primes: mp_limb_t);
69 pub fn n_cleanup_primes();
70 pub fn n_primes_arr_readonly(n: mp_limb_t) -> *const mp_limb_t;
71 pub fn n_prime_inverses_arr_readonly(n: mp_limb_t) -> *const f64;
72 pub fn n_mul_checked(a: *mut mp_limb_t, b: mp_limb_t, c: mp_limb_t) -> c_int;
73 pub fn n_add_checked(a: *mut mp_limb_t, b: mp_limb_t, c: mp_limb_t) -> c_int;
74 pub fn n_randlimb(state: *mut flint_rand_s) -> mp_limb_t;
75 pub fn n_randint(state: *mut flint_rand_s, limit: mp_limb_t) -> mp_limb_t;
76 pub fn n_urandint(state: *mut flint_rand_s, limit: mp_limb_t) -> mp_limb_t;
77 pub fn n_randbits(state: *mut flint_rand_s, bits: c_uint) -> mp_limb_t;
78 pub fn n_randtest_bits(state: *mut flint_rand_s, bits: c_int) -> mp_limb_t;
79 pub fn n_randtest(state: *mut flint_rand_s) -> mp_limb_t;
80 pub fn n_randtest_not_zero(state: *mut flint_rand_s) -> mp_limb_t;
81 pub fn n_randprime(state: *mut flint_rand_s, bits: mp_limb_t, proved: c_int) -> mp_limb_t;
82 pub fn n_randtest_prime(state: *mut flint_rand_s, proved: c_int) -> mp_limb_t;
83 pub fn n_pow(n: mp_limb_t, exp: mp_limb_t) -> mp_limb_t;
84 pub fn n_flog(n: mp_limb_t, b: mp_limb_t) -> mp_limb_t;
85 pub fn n_clog(n: mp_limb_t, b: mp_limb_t) -> mp_limb_t;
86 pub fn n_precompute_inverse(n: mp_limb_t) -> f64;
87 pub fn n_preinvert_limb(n: mp_limb_t) -> mp_limb_t;
88 pub fn n_mod_precomp(a: mp_limb_t, n: mp_limb_t, ninv: f64) -> mp_limb_t;
89 pub fn n_mod2_precomp(a: mp_limb_t, n: mp_limb_t, ninv: f64) -> mp_limb_t;
90 pub fn n_divrem2_precomp(q: *mut mp_limb_t, a: mp_limb_t, n: mp_limb_t, npre: f64)
91 -> mp_limb_t;
92 pub fn n_divrem2_preinv(
93 q: *mut mp_limb_t,
94 a: mp_limb_t,
95 n: mp_limb_t,
96 ninv: mp_limb_t,
97 ) -> mp_limb_t;
98 pub fn n_div2_preinv(a: mp_limb_t, n: mp_limb_t, ninv: mp_limb_t) -> mp_limb_t;
99 pub fn n_mod2_preinv(a: mp_limb_t, n: mp_limb_t, ninv: mp_limb_t) -> mp_limb_t;
100 pub fn n_ll_mod_preinv(
101 a_hi: mp_limb_t,
102 a_lo: mp_limb_t,
103 n: mp_limb_t,
104 ninv: mp_limb_t,
105 ) -> mp_limb_t;
106 pub fn n_lll_mod_preinv(
107 a_hi: mp_limb_t,
108 a_mi: mp_limb_t,
109 a_lo: mp_limb_t,
110 n: mp_limb_t,
111 ninv: mp_limb_t,
112 ) -> mp_limb_t;
113 pub fn n_mulmod_precomp(a: mp_limb_t, b: mp_limb_t, n: mp_limb_t, ninv: f64) -> mp_limb_t;
114 pub fn n_mulmod2_preinv(a: mp_limb_t, b: mp_limb_t, n: mp_limb_t, ninv: mp_limb_t)
115 -> mp_limb_t;
116 pub fn n_mulmod2(a: mp_limb_t, b: mp_limb_t, n: mp_limb_t) -> mp_limb_t;
117 pub fn n_mulmod_preinv(
118 a: mp_limb_t,
119 b: mp_limb_t,
120 n: mp_limb_t,
121 ninv: mp_limb_t,
122 norm: mp_limb_t,
123 ) -> mp_limb_t;
124 pub fn n_powmod_ui_precomp(a: mp_limb_t, exp: mp_limb_t, n: mp_limb_t, npre: f64) -> mp_limb_t;
125 pub fn n_powmod_precomp(
126 a: mp_limb_t,
127 exp: mp_limb_signed_t,
128 n: mp_limb_t,
129 npre: f64,
130 ) -> mp_limb_t;
131 pub fn n_powmod(a: mp_limb_t, exp: mp_limb_signed_t, n: mp_limb_t) -> mp_limb_t;
132 pub fn n_powmod2_preinv(
133 a: mp_limb_t,
134 exp: mp_limb_signed_t,
135 n: mp_limb_t,
136 ninv: mp_limb_t,
137 ) -> mp_limb_t;
138 pub fn n_powmod2_ui_preinv(
139 a: mp_limb_t,
140 exp: mp_limb_t,
141 n: mp_limb_t,
142 ninv: mp_limb_t,
143 ) -> mp_limb_t;
144 pub fn n_powmod_ui_preinv(
145 a: mp_limb_t,
146 exp: mp_limb_t,
147 n: mp_limb_t,
148 ninv: mp_limb_t,
149 norm: mp_limb_t,
150 ) -> mp_limb_t;
151 pub fn n_powmod2(a: mp_limb_t, exp: mp_limb_signed_t, n: mp_limb_t) -> mp_limb_t;
152 pub fn n_addmod(x: mp_limb_t, y: mp_limb_t, n: mp_limb_t) -> mp_limb_t;
153 pub fn n_submod(x: mp_limb_t, y: mp_limb_t, n: mp_limb_t) -> mp_limb_t;
154 pub fn n_negmod(x: mp_limb_t, n: mp_limb_t) -> mp_limb_t;
155 pub fn n_sqrtmod(a: mp_limb_t, p: mp_limb_t) -> mp_limb_t;
156 pub fn n_sqrtmod_2pow(
157 sqrt: *mut *mut mp_limb_t,
158 a: mp_limb_t,
159 exp: mp_limb_signed_t,
160 ) -> mp_limb_signed_t;
161 pub fn n_sqrtmod_primepow(
162 sqrt: *mut *mut mp_limb_t,
163 a: mp_limb_t,
164 p: mp_limb_t,
165 exp: mp_limb_signed_t,
166 ) -> mp_limb_signed_t;
167 pub fn n_sqrtmodn(
168 sqrt: *mut *mut mp_limb_t,
169 a: mp_limb_t,
170 fac: *mut n_factor_t,
171 ) -> mp_limb_signed_t;
172 pub fn n_gcd(x: mp_limb_t, y: mp_limb_t) -> mp_limb_t;
173 pub fn n_xgcd(a: *mut mp_limb_t, b: *mut mp_limb_t, x: mp_limb_t, y: mp_limb_t) -> mp_limb_t;
174 pub fn n_gcdinv(a: *mut mp_limb_t, x: mp_limb_t, y: mp_limb_t) -> mp_limb_t;
175 pub fn n_invmod(x: mp_limb_t, y: mp_limb_t) -> mp_limb_t;
176 pub fn n_CRT(r1: mp_limb_t, m1: mp_limb_t, r2: mp_limb_t, m2: mp_limb_t) -> mp_limb_t;
177 pub fn n_revbin(in_: mp_limb_t, bits: mp_limb_t) -> mp_limb_t;
178 pub fn n_jacobi(x: mp_limb_signed_t, y: mp_limb_t) -> c_int;
179 pub fn n_jacobi_unsigned(x: mp_limb_t, y: mp_limb_t) -> c_int;
180 pub fn n_sqrt(a: mp_limb_t) -> mp_limb_t;
181 pub fn n_sqrtrem(r: *mut mp_limb_t, a: mp_limb_t) -> mp_limb_t;
182 pub fn n_is_square(x: mp_limb_t) -> c_int;
183 pub fn n_cbrt_estimate(a: f64) -> f64;
184 pub fn n_cbrt(a: mp_limb_t) -> mp_limb_t;
185 pub fn n_cbrt_binary_search(x: mp_limb_t) -> mp_limb_t;
186 pub fn n_cbrt_newton_iteration(n: mp_limb_t) -> mp_limb_t;
187 pub fn n_cbrt_chebyshev_approx(n: mp_limb_t) -> mp_limb_t;
188 pub fn n_cbrtrem(remainder: *mut mp_limb_t, n: mp_limb_t) -> mp_limb_t;
189 pub fn n_is_perfect_power235(n: mp_limb_t) -> c_int;
190 pub fn n_is_perfect_power(root: *mut mp_limb_t, n: mp_limb_t) -> c_int;
191 pub fn n_is_oddprime_small(n: mp_limb_t) -> c_int;
192 pub fn n_is_oddprime_binary(n: mp_limb_t) -> c_int;
193 pub fn n_is_probabprime_fermat(n: mp_limb_t, i: mp_limb_t) -> c_int;
194 pub fn n_is_probabprime_fibonacci(n: mp_limb_t) -> c_int;
195 pub fn n_is_probabprime_lucas(n: mp_limb_t) -> c_int;
196 pub fn n_is_probabprime_BPSW(n: mp_limb_t) -> c_int;
197 pub fn n_is_strong_probabprime_precomp(
198 n: mp_limb_t,
199 npre: f64,
200 a: mp_limb_t,
201 d: mp_limb_t,
202 ) -> c_int;
203 pub fn n_is_strong_probabprime2_preinv(
204 n: mp_limb_t,
205 ninv: mp_limb_t,
206 a: mp_limb_t,
207 d: mp_limb_t,
208 ) -> c_int;
209 pub fn n_is_probabprime(n: mp_limb_t) -> c_int;
210 pub fn n_is_prime_pseudosquare(n: mp_limb_t) -> c_int;
211 pub fn n_is_prime_pocklington(n: mp_limb_t, iterations: mp_limb_t) -> c_int;
212 pub fn n_is_prime(n: mp_limb_t) -> c_int;
213 pub fn n_nth_prime(n: mp_limb_t) -> mp_limb_t;
214 pub fn n_nth_prime_bounds(lo: *mut mp_limb_t, hi: *mut mp_limb_t, n: mp_limb_t);
215 pub fn n_prime_pi(n: mp_limb_t) -> mp_limb_t;
216 pub fn n_prime_pi_bounds(lo: *mut mp_limb_t, hi: *mut mp_limb_t, n: mp_limb_t);
217 pub fn n_remove(n: *mut mp_limb_t, p: mp_limb_t) -> c_int;
218 pub fn n_remove2_precomp(n: *mut mp_limb_t, p: mp_limb_t, ppre: f64) -> c_int;
219 pub fn n_factor_init(factors: *mut n_factor_t);
220 pub fn n_factor_insert(factors: *mut n_factor_t, p: mp_limb_t, exp: mp_limb_t);
221 pub fn n_factor_trial_range(
222 factors: *mut n_factor_t,
223 n: mp_limb_t,
224 start: mp_limb_t,
225 num_primes: mp_limb_t,
226 ) -> mp_limb_t;
227 pub fn n_factor_trial_partial(
228 factors: *mut n_factor_t,
229 n: mp_limb_t,
230 prod: *mut mp_limb_t,
231 num_primes: mp_limb_t,
232 limit: mp_limb_t,
233 ) -> mp_limb_t;
234 pub fn n_factor_trial(
235 factors: *mut n_factor_t,
236 n: mp_limb_t,
237 num_primes: mp_limb_t,
238 ) -> mp_limb_t;
239 pub fn n_factor_partial(
240 factors: *mut n_factor_t,
241 n: mp_limb_t,
242 limit: mp_limb_t,
243 proved: c_int,
244 ) -> mp_limb_t;
245 pub fn n_factor_power235(exp: *mut mp_limb_t, n: mp_limb_t) -> mp_limb_t;
246 pub fn n_factor_one_line(n: mp_limb_t, iters: mp_limb_t) -> mp_limb_t;
247 pub fn n_factor_lehman(n: mp_limb_t) -> mp_limb_t;
248 pub fn n_factor_SQUFOF(n: mp_limb_t, iters: mp_limb_t) -> mp_limb_t;
249 pub fn n_factor(factors: *mut n_factor_t, n: mp_limb_t, proved: c_int);
250 pub fn n_factor_pp1(n: mp_limb_t, B1: mp_limb_t, c: mp_limb_t) -> mp_limb_t;
251 pub fn n_factor_pp1_wrapper(n: mp_limb_t) -> mp_limb_t;
252 pub fn n_factor_pp1_table_insert(
253 bits: mp_limb_signed_t,
254 B1: mp_limb_signed_t,
255 count: mp_limb_signed_t,
256 );
257 pub fn n_factor_pollard_brent_single(
258 factor: *mut mp_limb_t,
259 n: mp_limb_t,
260 ninv: mp_limb_t,
261 ai: mp_limb_t,
262 xi: mp_limb_t,
263 normbits: mp_limb_t,
264 max_iters: mp_limb_t,
265 ) -> c_int;
266 pub fn n_factor_pollard_brent(
267 factor: *mut mp_limb_t,
268 state: *mut flint_rand_s,
269 n_in: mp_limb_t,
270 max_tries: mp_limb_t,
271 max_iters: mp_limb_t,
272 ) -> c_int;
273 pub fn n_is_squarefree(n: mp_limb_t) -> c_int;
274 pub fn n_moebius_mu(n: mp_limb_t) -> c_int;
275 pub fn n_moebius_mu_vec(mu: *mut c_int, len: mp_limb_t);
276 pub fn n_euler_phi(n: mp_limb_t) -> mp_limb_t;
277 pub fn n_sizeinbase(n: mp_limb_t, base: c_int) -> c_int;
278 pub fn n_nextprime(n: mp_limb_t, proved: c_int) -> mp_limb_t;
279 pub fn n_factorial_mod2_preinv(n: mp_limb_t, p: mp_limb_t, pinv: mp_limb_t) -> mp_limb_t;
280 pub fn n_factorial_fast_mod2_preinv(n: mp_limb_t, p: mp_limb_t, pinv: mp_limb_t) -> mp_limb_t;
281 pub fn n_primitive_root_prime_prefactor(p: mp_limb_t, factors: *mut n_factor_t) -> mp_limb_t;
282 pub fn n_primitive_root_prime(p: mp_limb_t) -> mp_limb_t;
283 pub fn n_discrete_log_bsgs(b: mp_limb_t, a: mp_limb_t, n: mp_limb_t) -> mp_limb_t;
284 pub fn n_root_estimate(a: f64, n: c_int) -> mp_limb_t;
285 pub fn n_rootrem(remainder: *mut mp_limb_t, n: mp_limb_t, root: mp_limb_t) -> mp_limb_t;
286 pub fn n_root(n: mp_limb_t, root: mp_limb_t) -> mp_limb_t;
287 pub fn n_factor_ecm_double(
288 x: *mut mp_limb_t,
289 z: *mut mp_limb_t,
290 x0: mp_limb_t,
291 z0: mp_limb_t,
292 n: mp_limb_t,
293 n_ecm_inf: *mut n_ecm_s,
294 );
295 pub fn n_factor_ecm_add(
296 x: *mut mp_limb_t,
297 z: *mut mp_limb_t,
298 x1: mp_limb_t,
299 z1: mp_limb_t,
300 x2: mp_limb_t,
301 z2: mp_limb_t,
302 x0: mp_limb_t,
303 z0: mp_limb_t,
304 n: mp_limb_t,
305 n_ecm_inf: *mut n_ecm_s,
306 );
307 pub fn n_factor_ecm_mul_montgomery_ladder(
308 x: *mut mp_limb_t,
309 z: *mut mp_limb_t,
310 x0: mp_limb_t,
311 z0: mp_limb_t,
312 k: mp_limb_t,
313 n: mp_limb_t,
314 n_ecm_inf: *mut n_ecm_s,
315 );
316 pub fn n_factor_ecm_select_curve(
317 f: *mut mp_limb_t,
318 sig: mp_limb_t,
319 n: mp_limb_t,
320 n_ecm_inf: *mut n_ecm_s,
321 ) -> c_int;
322 pub fn n_factor_ecm_stage_I(
323 f: *mut mp_limb_t,
324 prime_array: *const mp_limb_t,
325 num: mp_limb_t,
326 B1: mp_limb_t,
327 n: mp_limb_t,
328 n_ecm_inf: *mut n_ecm_s,
329 ) -> c_int;
330 pub fn n_factor_ecm_stage_II(
331 f: *mut mp_limb_t,
332 B1: mp_limb_t,
333 B2: mp_limb_t,
334 P: mp_limb_t,
335 n: mp_limb_t,
336 n_ecm_inf: *mut n_ecm_s,
337 ) -> c_int;
338 pub fn n_factor_ecm(
339 f: *mut mp_limb_t,
340 curves: mp_limb_t,
341 B1: mp_limb_t,
342 B2: mp_limb_t,
343 state: *mut flint_rand_s,
344 n: mp_limb_t,
345 ) -> c_int;
346 pub fn n_mulmod_precomp_shoup(w: mp_limb_t, p: mp_limb_t) -> mp_limb_t;
347 pub fn n_mulmod_shoup(
348 w: mp_limb_t,
349 t: mp_limb_t,
350 w_precomp: mp_limb_t,
351 p: mp_limb_t,
352 ) -> mp_limb_t;
353}