1 /*
2 Copyright (C) 2009 William Hart
3 Copyright (C) 2011 Sebastian Pancratz
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 <http://www.gnu.org/licenses/>.
11 */
12
13 #include <gmp.h>
14 #include "flint.h"
15 #include "fmpz.h"
16 #include "ulong_extras.h"
17
fmpz_powm(fmpz_t f,const fmpz_t g,const fmpz_t e,const fmpz_t m)18 void fmpz_powm(fmpz_t f, const fmpz_t g, const fmpz_t e, const fmpz_t m)
19 {
20 if (fmpz_sgn(m) <= 0)
21 {
22 flint_throw(FLINT_ERROR, "Exception in fmpz_powm: "
23 "Modulus is less than 1.\n");
24 }
25 else if (!COEFF_IS_MPZ(*e)) /* e is small */
26 {
27 if (*e >= 0)
28 {
29 fmpz_powm_ui(f, g, *e, m);
30 }
31 else
32 {
33 fmpz_t g_inv;
34 fmpz_init(g_inv);
35 if (!fmpz_invmod(g_inv, g, m))
36 {
37 fmpz_clear(g_inv);
38 flint_throw(FLINT_ERROR, "Exception in fmpz_powm: "
39 "Base is not invertible.\n");
40 }
41 else
42 {
43 fmpz_powm_ui(f, g_inv, -*e, m);
44 fmpz_clear(g_inv);
45 }
46 }
47 }
48 else /* e is large */
49 {
50 if (!COEFF_IS_MPZ(*m)) /* m is small */
51 {
52 ulong g1 = fmpz_fdiv_ui(g, *m);
53 mpz_t g2, m2;
54 __mpz_struct *mpz_ptr;
55
56 flint_mpz_init_set_ui(g2, g1);
57 flint_mpz_init_set_ui(m2, *m);
58 mpz_ptr = _fmpz_promote(f);
59
60 mpz_powm(mpz_ptr, g2, COEFF_TO_PTR(*e), m2);
61
62 mpz_clear(g2);
63 mpz_clear(m2);
64 _fmpz_demote_val(f);
65 }
66 else /* m is large */
67 {
68 if (!COEFF_IS_MPZ(*g)) /* g is small */
69 {
70 mpz_t g2;
71 __mpz_struct *mpz_ptr;
72
73 flint_mpz_init_set_si(g2, *g);
74 mpz_ptr = _fmpz_promote(f);
75
76 mpz_powm(mpz_ptr, g2, COEFF_TO_PTR(*e), COEFF_TO_PTR(*m));
77
78 mpz_clear(g2);
79 _fmpz_demote_val(f);
80 }
81 else /* g is large */
82 {
83 __mpz_struct *mpz_ptr = _fmpz_promote(f);
84
85 mpz_powm(mpz_ptr,
86 COEFF_TO_PTR(*g), COEFF_TO_PTR(*e), COEFF_TO_PTR(*m));
87 _fmpz_demote_val(f);
88 }
89 }
90 }
91 }
92
93