1 /*
2 Copyright (C) 2015 Vladimir Glazachev
3
4 This file is part of FLINT.
5
6 FLINT is free software: you can redistribute it and/or modify it under
7 the terms of the GNU Lesser General Public License (LGPL) as published
8 by the Free Software Foundation; either version 2.1 of the License, or
9 (at your option) any later version. See <http://www.gnu.org/licenses/>.
10 */
11
12 #include "aprcl.h"
13
14 int
aprcl_is_prime_divisors_in_residue(const fmpz_t n,const fmpz_t s,ulong r)15 aprcl_is_prime_divisors_in_residue(const fmpz_t n, const fmpz_t s, ulong r)
16 {
17 int result;
18 ulong i;
19 fmpz_t npow, nmul, fac;
20
21 fmpz_init(fac);
22 fmpz_init_set(npow, n);
23 fmpz_mod(npow, npow, s); /* npow = n mod s */
24 fmpz_init_set(nmul, npow);
25
26 result = 1;
27 for (i = 1; i < r; i++)
28 {
29 /* if find divisor then n is composite */
30 if (fmpz_divisor_in_residue_class_lenstra(fac, n, npow, s) == 1)
31 {
32 result = 0;
33 break;
34 }
35 /* npow = n^i mod s */
36 fmpz_mul(npow, npow, nmul);
37 fmpz_mod(npow, npow, s);
38 }
39
40 fmpz_clear(fac);
41 fmpz_clear(npow);
42 fmpz_clear(nmul);
43
44 return result;
45 }
46
47