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 /*
15 Computes f such that \sigma_x(f) = g.
16 */
17 void
unity_zp_aut_inv(unity_zp f,const unity_zp g,ulong x)18 unity_zp_aut_inv(unity_zp f, const unity_zp g, ulong x)
19 {
20 ulong i, j, p_pow1, p_pow2, m, p_pow_preinv;
21 fmpz_t f_coeff, g_coeff;
22
23 fmpz_init(f_coeff);
24 fmpz_init(g_coeff);
25 p_pow1 = n_pow(f->p, f->exp - 1); /* p_pow1 = p^{k - 1} */
26 p_pow2 = p_pow1 * f->p; /* p_pow2 = p^k */
27 m = (f->p - 1) * p_pow1; /* m = (p - 1) * p^{k - 1} */
28 p_pow_preinv = n_preinvert_limb(p_pow2);
29 unity_zp_set_zero(f);
30
31 /* for i = 0, 1,..., m - 1 set f[i] = g[xi mod p^k] */
32 for (i = 0; i < m; i++)
33 {
34 /* set g_ind = x * i mod p^k */
35 ulong g_ind = n_mulmod2_preinv(x, i, p_pow2, p_pow_preinv);
36
37 /* set g_coeff to g[g_ind] */
38 fmpz_mod_poly_get_coeff_fmpz(g_coeff, g->poly, g_ind);
39
40 /* set f[i] = g[x * i mod p^k] */
41 unity_zp_coeff_set_fmpz(f, i, g_coeff);
42 }
43
44 /*
45 for i = m, m + 1,..., p^k - 1
46 for j = 1, 2,..., p - 1
47 set f[i - j * p^{k - 1}] =
48 (f[i - j * p^{k - 1}] - g[x * i mod p^k]) mod n
49 */
50 for (i = m; i < p_pow2; i++)
51 {
52 /* set g_ind = x * i mod p^k */
53 ulong g_ind = n_mulmod2_preinv(x, i, p_pow2, p_pow_preinv);
54
55 for (j = 1; j < f->p; j++)
56 {
57 /* set f_ind = i - j * p^{k - 1} */
58 ulong f_ind = i - j * p_pow1;
59
60 /* set g_coeff = g[x * i mod p^k] */
61 fmpz_mod_poly_get_coeff_fmpz(g_coeff, g->poly, g_ind);
62
63 /* set f_coeff = f[i - j * p^{k - 1}] */
64 fmpz_mod_poly_get_coeff_fmpz(f_coeff, f->poly, f_ind);
65
66 /* set f_coeff = f[i - j * p^{k - 1}] - g[x * i mod p^k] */
67 fmpz_sub(f_coeff, f_coeff, g_coeff);
68
69 /* set f[i - j * p^{k - 1}] = f_coeff */
70 unity_zp_coeff_set_fmpz(f, f_ind, f_coeff);
71 }
72 }
73
74 fmpz_clear(f_coeff);
75 fmpz_clear(g_coeff);
76 }
77
78