include/flint/dirichlet.h

0001 /*
0002     Copyright (C) 2016 Pascal Molin
0003
0004     This file is part of FLINT.
0005
0006     FLINT is free software: you can redistribute it and/or modify it under
0007     the terms of the GNU Lesser General Public License (LGPL) as published
0008     by the Free Software Foundation; either version 3 of the License, or
0009     (at your option) any later version.  See <https://www.gnu.org/licenses/>.
0010 */
0011
0012 #ifndef DIRICHLET_H
0013 #define DIRICHLET_H
0014
0015 #ifdef DIRICHLET_INLINES_C
0016 #define DIRICHLET_INLINE
0017 #else
0018 #define DIRICHLET_INLINE static inline
0019 #endif
0020
0021 #include "nmod.h"
0022 #include "dlog.h"
0023
0024 #ifdef __cplusplus
0025 extern "C" {
0026 #endif
0027
0028 #define MAX_FACTORS 15
0029
0030 /* should this dlog pointer be in the prime or the global group? */
0031 typedef struct
0032 {
0033     ulong p;    /* underlying prime */
0034     int e;      /* exponent */
0035     nmod_t pe;  /* modulus */
0036     nmod_t phi;  /* phi(p^e) */
0037     ulong g;    /* conrey generator */
0038     dlog_precomp_struct * dlog;  /* precomputed data for discrete log mod p^e */
0039 }
0040 dirichlet_prime_group_struct;
0041
0042 typedef struct
0043 {
0044     ulong q;                /* modulus */
0045     ulong q_even;           /* even part of modulus */
0046     nmod_t mod;             /* modulus with precomputed inverse */
0047     ulong rad_q;            /* radical = product of odd primes */
0048     ulong phi_q;            /* phi(q) = group size */
0049     slong neven;            /* number of even components (in 0,1,2)*/
0050     slong num;              /* number of prime components (even + odd) */
0051     ulong expo;             /* exponent = largest order in G */
0052     dirichlet_prime_group_struct * P;
0053     ulong * generators;     /* generators lifted mod q */
0054     ulong * PHI;            /* PHI(k) = expo / phi(k)        */
0055 }
0056 dirichlet_group_struct;
0057
0058 typedef dirichlet_group_struct dirichlet_group_t[1];
0059
0060 DIRICHLET_INLINE ulong
0061 dirichlet_group_size(const dirichlet_group_t G)
0062 {
0063     return G->phi_q;
0064 }
0065
0066 ulong dirichlet_group_num_primitive(const dirichlet_group_t G);
0067
0068 int dirichlet_group_init(dirichlet_group_t G, ulong q);
0069 void dirichlet_subgroup_init(dirichlet_group_t H, const dirichlet_group_t G, ulong h);
0070 void dirichlet_group_clear(dirichlet_group_t G);
0071 void dirichlet_group_dlog_precompute(dirichlet_group_t G, ulong num);
0072 void dirichlet_group_dlog_clear(dirichlet_group_t G);
0073
0074 /* properties of elements without log */
0075
0076 ulong dirichlet_conductor_ui(const dirichlet_group_t G, ulong a);
0077 int dirichlet_parity_ui(const dirichlet_group_t G, ulong a);
0078 ulong dirichlet_order_ui(const dirichlet_group_t G, ulong a);
0079
0080 /* characters, keep both number and log */
0081 typedef struct
0082 {
0083     ulong n;           /* number */
0084     ulong * log;       /* s.t. prod generators[k]^log[k] = number */
0085 }
0086 dirichlet_char_struct;
0087
0088 typedef dirichlet_char_struct dirichlet_char_t[1];
0089
0090 void dirichlet_char_init(dirichlet_char_t x, const dirichlet_group_t G);
0091 void dirichlet_char_clear(dirichlet_char_t x);
0092 void dirichlet_char_print(const dirichlet_group_t G, const dirichlet_char_t x);
0093
0094 DIRICHLET_INLINE void
0095 dirichlet_char_set(dirichlet_char_t x, const dirichlet_group_t G, const dirichlet_char_t y)
0096 {
0097     slong k;
0098     x->n = y->n;
0099     for (k = 0; k < G->num; k++)
0100         x->log[k] = y->log[k];
0101 }
0102
0103 DIRICHLET_INLINE int
0104 dirichlet_char_eq(const dirichlet_char_t x, const dirichlet_char_t y)
0105 {
0106     return (x->n == y->n);
0107 }
0108
0109 int dirichlet_char_eq_deep(const dirichlet_group_t G, const dirichlet_char_t x, const dirichlet_char_t y);
0110 int dirichlet_parity_char(const dirichlet_group_t G, const dirichlet_char_t x);
0111 ulong dirichlet_conductor_char(const dirichlet_group_t G, const dirichlet_char_t x);
0112 ulong dirichlet_order_char(const dirichlet_group_t G, const dirichlet_char_t x);
0113
0114 void dirichlet_char_log(dirichlet_char_t x, const dirichlet_group_t G, ulong m);
0115
0116 DIRICHLET_INLINE ulong
0117 dirichlet_char_exp(const dirichlet_group_t FLINT_UNUSED(G), const dirichlet_char_t x)
0118 {
0119     return x->n;
0120 }
0121
0122 ulong _dirichlet_char_exp(dirichlet_char_t x, const dirichlet_group_t G);
0123
0124 void dirichlet_char_index(dirichlet_char_t x, const dirichlet_group_t G, ulong j);
0125 ulong dirichlet_index_char(const dirichlet_group_t G, const dirichlet_char_t x);
0126
0127 void dirichlet_char_one(dirichlet_char_t x, const dirichlet_group_t G);
0128 void dirichlet_char_first_primitive(dirichlet_char_t x, const dirichlet_group_t G);
0129
0130 int dirichlet_char_next(dirichlet_char_t x, const dirichlet_group_t G);
0131 int dirichlet_char_next_primitive(dirichlet_char_t x, const dirichlet_group_t G);
0132
0133 void dirichlet_char_mul(dirichlet_char_t c, const dirichlet_group_t G, const dirichlet_char_t a, const dirichlet_char_t b);
0134 void dirichlet_char_pow(dirichlet_char_t c, const dirichlet_group_t G, const dirichlet_char_t a, ulong n);
0135
0136 void dirichlet_char_lower(dirichlet_char_t y, const dirichlet_group_t H, const dirichlet_char_t x, const dirichlet_group_t G);
0137 void dirichlet_char_lift(dirichlet_char_t y, const dirichlet_group_t G, const dirichlet_char_t x, const dirichlet_group_t H);
0138
0139 #define DIRICHLET_CHI_NULL UWORD_MAX
0140
0141 ulong dirichlet_pairing(const dirichlet_group_t G, ulong m, ulong n);
0142 ulong dirichlet_pairing_char(const dirichlet_group_t G, const dirichlet_char_t a, const dirichlet_char_t b);
0143
0144 DIRICHLET_INLINE int
0145 dirichlet_char_is_principal(const dirichlet_group_t FLINT_UNUSED(G), const dirichlet_char_t chi)
0146 {
0147     return (chi->n == 1);
0148 }
0149
0150 DIRICHLET_INLINE int
0151 dirichlet_char_is_real(const dirichlet_group_t G, const dirichlet_char_t chi)
0152 {
0153     return G->q <= 4 || (nmod_mul(chi->n, chi->n, G->mod) == 1);
0154 }
0155
0156 DIRICHLET_INLINE int
0157 dirichlet_char_is_primitive(const dirichlet_group_t G, const dirichlet_char_t chi)
0158 {
0159     return (dirichlet_conductor_char(G, chi) == G->q);
0160 }
0161
0162 ulong dirichlet_chi(const dirichlet_group_t G, const dirichlet_char_t chi, ulong n);
0163
0164 void dirichlet_vec_set_null(ulong *v, const dirichlet_group_t G, slong nv);
0165 void dirichlet_chi_vec_loop(ulong *v, const dirichlet_group_t G, const dirichlet_char_t chi, slong nv);
0166 void dirichlet_chi_vec_primeloop(ulong *v, const dirichlet_group_t G, const dirichlet_char_t chi, slong nv);
0167 void dirichlet_chi_vec(ulong *v, const dirichlet_group_t G, const dirichlet_char_t chi, slong nv);
0168 void dirichlet_chi_vec_loop_order(ulong *v, const dirichlet_group_t G, const dirichlet_char_t chi, ulong order, slong nv);
0169 void dirichlet_chi_vec_primeloop_order(ulong *v, const dirichlet_group_t G, const dirichlet_char_t chi, ulong order, slong nv);
0170 void dirichlet_chi_vec_order(ulong *v, const dirichlet_group_t G, const dirichlet_char_t chi, ulong order, slong nv);
0171
0172 #ifdef __cplusplus
0173 }
0174 #endif
0175
0176 #endif