1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/*
Copyright (C) 2015 Vladimir Glazachev
This file is part of FLINT.
FLINT is free software: you can redistribute it and/or modify it under
the terms of the GNU Lesser General Public License (LGPL) as published
by the Free Software Foundation; either version 3 of the License, or
(at your option) any later version. See <https://www.gnu.org/licenses/>.
*/
#include "ulong_extras.h"
#include "nmod_vec.h"
#include "aprcl.h"
/*
Computes sum \zeta_{p^k}^{a * x + b * f(x)} for x = 1, 2, ..., q - 2.
*/
void
_unity_zp_jacobi_sum_pq_general(unity_zp f, const nn_ptr table,
ulong p, ulong q, ulong k, ulong a, ulong b)
{
int i, j;
ulong size, pow, pow_dec;
unity_zp_set_zero(f);
pow_dec = n_pow(p, k - 1);
size = (p - 1) * pow_dec;
pow = pow_dec * p;
for (i = 1; i < q - 1; i++)
{
/* l = a * i + b * f[i] */
ulong l = (a * (i) + b * table[i]) % pow;
/* if l < (p - 1)p^{k - 1} increase f[l] by one */
if (l < size)
{
unity_zp_coeff_inc(f, l);
}
else /* else decrease f[l - jp^{k - 1}] by one for j in [0; p - 2] */
{
for (j = 0; j < p - 1; j++)
{
l -= pow_dec;
unity_zp_coeff_dec(f, l);
}
}
}
}
/*
Computes sum \zeta_{p^k}^{x + f(x)} for x = 1, 2, ..., q - 2.
*/
void
unity_zp_jacobi_sum_pq(unity_zp f, ulong q, ulong p)
{
ulong k;
nn_ptr table;
table = aprcl_f_table(q);
k = aprcl_p_power_in_q(q - 1, p);
_unity_zp_jacobi_sum_pq_general(f, table, p, q, k, 1, 1);
_nmod_vec_clear(table);
}
/*
Computes sum \zeta_{p^k}^{2 * x + b * f(x)} for x = 1, 2, ..., q - 2.
*/
void
unity_zp_jacobi_sum_2q_one(unity_zp f, ulong q)
{
ulong k;
nn_ptr table;
table = aprcl_f_table(q);
k = aprcl_p_power_in_q(q - 1, 2);
_unity_zp_jacobi_sum_pq_general(f, table, 2, q, k, 2, 1);
_nmod_vec_clear(table);
}
/*
Computes sum \zeta_{p^k}^{3 * 2^{k - 3} * x + 2^{k - 3} * f(x)}
for x = 1, 2, ..., q - 2.
*/
void
unity_zp_jacobi_sum_2q_two(unity_zp f, ulong q)
{
ulong a, b, k;
nn_ptr table;
table = aprcl_f_table(q);
k = aprcl_p_power_in_q(q - 1, 2);
b = n_pow(2, k - 3); /* b = 2^{k - 3} */
a = 3 * b; /* a = 3 * 2^{k - 3} */
_unity_zp_jacobi_sum_pq_general(f, table, 2, q, k, a, b);
_nmod_vec_clear(table);
}