1 /*
2 Copyright (C) 2011 Fredrik Johansson
3 Copyright (C) 2014 William Hart
4
5 This file is part of FLINT.
6
7 FLINT is free software: you can redistribute it and/or modify it under
8 the terms of the GNU Lesser General Public License (LGPL) as published
9 by the Free Software Foundation; either version 2.1 of the License, or
10 (at your option) any later version. See <https://www.gnu.org/licenses/>.
11 */
12
13 #include <stdio.h>
14 #include <stdlib.h>
15 #include <gmp.h>
16 #include "flint.h"
17 #include "fmpz.h"
18 #include "ulong_extras.h"
19
20
main()21 int main()
22 {
23 slong i, j;
24 int sign;
25
26 fmpz_t input;
27 fmpz_t result;
28 fmpz_t r1;
29 fmpz_t m1;
30 fmpz_t mprod;
31 fmpz_t r2, m2;
32
33 FLINT_TEST_INIT(state);
34
35 flint_printf("CRT....");
36 fflush(stdout);
37
38 fmpz_init(input);
39 fmpz_init(result);
40 fmpz_init(r1);
41 fmpz_init(m1);
42 fmpz_init(r2);
43 fmpz_init(m2);
44 fmpz_init(mprod);
45
46
47 for (i = 0; i < 1000 * flint_test_multiplier(); i++)
48 {
49 slong nprimes;
50
51 fmpz_set_ui(m2, n_randtest_prime(state, 0));
52 nprimes = 1 + n_randint(state, 4);
53
54 fmpz_set_ui(m1, UWORD(1));
55 for (j = 0; j < nprimes; )
56 {
57 ulong t = n_randtest_prime(state, 0);
58 if (t != fmpz_get_ui(m2))
59 {
60 fmpz_mul_ui(m1, m1, t);
61 j++;
62 }
63 }
64
65 fmpz_mul(mprod, m1, m2);
66
67 sign = n_randint(state, 2);
68
69 if (sign)
70 fmpz_randtest_mod_signed(input, state, mprod);
71 else
72 fmpz_randtest_mod(input, state, mprod);
73
74 fmpz_mod(r1, input, m1);
75 fmpz_mod(r2, input, m2);
76
77 fmpz_CRT(result, r1, m1, r2, m2, sign);
78
79 if (!fmpz_equal(result, input))
80 {
81 flint_printf("FAIL:\n");
82 flint_printf("m1: "); fmpz_print(m1); flint_printf("\n");
83 flint_printf("m2: "); fmpz_print(m2); flint_printf("\n");
84 flint_printf("m1*m2: "); fmpz_print(mprod); flint_printf("\n");
85 flint_printf("input: "); fmpz_print(input); flint_printf("\n");
86 flint_printf("r1: "); fmpz_print(r1); flint_printf("\n");
87 flint_printf("r2: "); fmpz_print(r2); flint_printf("\n");
88 flint_printf("result: "); fmpz_print(result); flint_printf("\n");
89 flint_printf("%wd Equalness: %d\n", i, fmpz_equal(result, input));
90 flint_printf("\n");
91 abort();
92 }
93 }
94
95 fmpz_clear(input);
96 fmpz_clear(result);
97 fmpz_clear(r1);
98 fmpz_clear(m1);
99 fmpz_clear(r2);
100 fmpz_clear(m2);
101 fmpz_clear(mprod);
102
103
104 FLINT_TEST_CLEANUP(state);
105
106 flint_printf("PASS\n");
107 return 0;
108 }
109