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