1 /*
2 Copyright (C) 2012 Sebastian Pancratz
3 Copyright (C) 2013 Mike Hansen
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 "fq_nmod.h"
14
_fq_nmod_trace(fmpz_t rop2,const mp_limb_t * op,slong len,const fq_nmod_ctx_t ctx)15 void _fq_nmod_trace(fmpz_t rop2, const mp_limb_t *op, slong len,
16 const fq_nmod_ctx_t ctx)
17 {
18 const slong d = fq_nmod_ctx_degree(ctx);
19
20 slong i, l;
21 mp_limb_t *t, rop;
22
23 t = _nmod_vec_init(d);
24 _nmod_vec_zero(t, d);
25
26 t[0] = n_mod2_preinv(d, ctx->mod.n, ctx->mod.ninv);
27
28 for (i = 1; i < d; i++)
29 {
30 for (l = ctx->len - 2; l >= 0 && ctx->j[l] >= d - (i - 1); l--)
31 {
32 t[i] = n_addmod(t[i],
33 n_mulmod2_preinv(t[ctx->j[l] + i - d], ctx->a[l], ctx->mod.n, ctx->mod.ninv),
34 ctx->mod.n);
35 }
36
37 if (l >= 0 && ctx->j[l] == d - i)
38 {
39 t[i] = n_addmod(t[i],
40 n_mulmod2_preinv(ctx->a[l], i, ctx->mod.n, ctx->mod.ninv),
41 ctx->mod.n);
42 }
43
44 t[i] = n_negmod(t[i], ctx->mod.n);
45 }
46
47
48 rop = WORD(0);
49 for (i = 0; i < len; i++)
50 {
51 rop = n_addmod(rop,
52 n_mulmod2_preinv(op[i], t[i], ctx->mod.n, ctx->mod.ninv),
53 ctx->mod.n);
54 }
55
56 _nmod_vec_clear(t);
57
58 fmpz_set_ui(rop2, rop);
59 }
60
fq_nmod_trace(fmpz_t rop,const fq_nmod_t op,const fq_nmod_ctx_t ctx)61 void fq_nmod_trace(fmpz_t rop, const fq_nmod_t op, const fq_nmod_ctx_t ctx)
62 {
63 if (fq_nmod_is_zero(op, ctx))
64 {
65 fmpz_zero(rop);
66 return;
67 }
68
69 _fq_nmod_trace(rop, op->coeffs, op->length, ctx);
70 }
71
72