include/flint/dlog.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 DLOG_H
0013 #define DLOG_H
0014
0015 #ifdef DLOG_INLINES_C
0016 #define DLOG_INLINE
0017 #else
0018 #define DLOG_INLINE static inline
0019 #endif
0020
0021 #include "ulong_extras.h"
0022
0023 #ifdef __cplusplus
0024 extern "C" {
0025 #endif
0026
0027 enum
0028 {
0029     DLOG_MODPE, DLOG_CRT, DLOG_POWER, DLOG_BSGS, DLOG_TABLE, DLOG_23
0030 };
0031
0032 typedef struct dlog_precomp_struct dlog_precomp_struct;
0033 typedef struct dlog_precomp_struct * dlog_preconn_ptr;
0034
0035 /* log in (1+pZ/p^eZ), e small: use recursion formulas
0036  * could use padic log instead but exponent is small
0037  * for ulongs */
0038 typedef struct
0039 {
0040     ulong inv1p;         /* 1 / (1 + p) */
0041     ulong invloga1;      /* 1 / log(a^(p-1),1+p) */
0042 }
0043 dlog_1modpe_struct;
0044
0045 typedef dlog_1modpe_struct dlog_1modpe_t[1];
0046
0047 /* log in (Z/p^eZ)^* */
0048 typedef struct
0049 {
0050     ulong p;
0051     ulong e;
0052     ulong pe1;                   /* p^(e-1) */
0053     ulong inva;
0054     nmod_t pe;
0055     dlog_precomp_struct * modp;
0056     dlog_1modpe_t modpe;
0057 }
0058 dlog_modpe_struct;
0059
0060 typedef dlog_modpe_struct dlog_modpe_t[1];
0061
0062 /* all logs precomputed in (Z/modZ)^ast */
0063 typedef struct
0064 {
0065     ulong mod;
0066     ulong * table;
0067 }
0068 dlog_table_struct;
0069
0070 typedef dlog_table_struct dlog_table_t[1];
0071
0072 /* bsgs table, already in flint */
0073
0074 typedef struct apow {
0075     ulong k;
0076     ulong ak;
0077 } apow_t;
0078
0079 int apow_cmp(const apow_t * x, const apow_t * y);
0080
0081 typedef struct {
0082     nmod_t mod;
0083     ulong m;
0084     ulong am;
0085     ulong g;
0086     apow_t * table;
0087 } dlog_bsgs_struct;
0088
0089 typedef dlog_bsgs_struct dlog_bsgs_t[1];
0090 /* typedef bsgs_t dlog_bsgs_t; */
0091
0092 /* Pollard rho */
0093 typedef struct {
0094     ulong a;
0095     nmod_t n;
0096     nmod_t mod;
0097     int nisprime;
0098 } dlog_rho_struct;
0099
0100 typedef dlog_rho_struct dlog_rho_t[1];
0101
0102 /* CRT decomposition (Pohlig-Hellman) */
0103 typedef struct
0104 {
0105     nmod_t mod;
0106     nmod_t n;
0107     ulong num;
0108     ulong * expo;
0109     ulong * crt_coeffs;
0110     dlog_preconn_ptr pre;
0111 }
0112 dlog_crt_struct;
0113
0114 typedef dlog_crt_struct dlog_crt_t[1];
0115
0116 /* dlog when generator has prime power order */
0117 typedef struct
0118 {
0119     nmod_t mod;
0120     ulong p;
0121     ulong e;
0122     ulong * apk;
0123     dlog_precomp_struct * pre;
0124 }
0125 dlog_power_struct;
0126
0127 typedef dlog_power_struct dlog_power_t[1];
0128
0129 typedef ulong dlog_order23_t[1];
0130
0131 /* generic decomposition */
0132 /*typedef */
0133 struct
0134 dlog_precomp_struct
0135 {
0136     int type;
0137     ulong cost;
0138     union
0139     {
0140         dlog_table_t table;
0141         dlog_bsgs_t bsgs;
0142         dlog_crt_t crt;
0143         dlog_power_t power;
0144         dlog_modpe_t modpe;
0145         dlog_order23_t order23;
0146     } t;
0147 };
0148
0149 typedef dlog_precomp_struct dlog_precomp_t[1];
0150
0151 void dlog_precomp_modpe_init(dlog_precomp_t pre, ulong a, ulong p, ulong e, ulong pe, ulong num);
0152 void dlog_precomp_small_init(dlog_precomp_t pre, ulong a, ulong mod, ulong n, ulong num);
0153 void dlog_precomp_n_init(dlog_precomp_t pre, ulong a, ulong mod, ulong n, ulong num);
0154 void dlog_precomp_p_init(dlog_precomp_t pre, ulong a, ulong mod, ulong p, ulong num);
0155 void dlog_precomp_pe_init(dlog_precomp_t pre, ulong a, ulong mod, ulong p, ulong e, ulong pe, ulong num);
0156 void dlog_precomp_clear(dlog_precomp_t pre);
0157
0158 ulong dlog_precomp(const dlog_precomp_t pre, ulong b);
0159
0160 ulong dlog_order23_init(dlog_order23_t t, ulong a);
0161 ulong dlog_table_init(dlog_table_t t, ulong a, ulong mod);
0162 ulong dlog_crt_init(dlog_crt_t t, ulong a, ulong mod, ulong n, ulong num);
0163 ulong dlog_power_init(dlog_power_t t, ulong a, ulong mod, ulong p, ulong e, ulong num);
0164 ulong dlog_modpe_init(dlog_modpe_t t, ulong a, ulong p, ulong e, ulong pe, ulong num);
0165 ulong dlog_bsgs_init(dlog_bsgs_t t, ulong a, ulong mod, ulong n, ulong m);
0166 void dlog_1modpe_init(dlog_1modpe_t t, ulong a1, ulong p, ulong e, nmod_t pe);
0167 void dlog_rho_init(dlog_rho_t t, ulong a, ulong mod, ulong n);
0168 /*#define dlog_bsgs_init(t, a, n, m) bsgs_table_init(t, a, n, m)*/
0169
0170 ulong dlog_once(ulong b, ulong a, const nmod_t mod, ulong n);
0171
0172 DLOG_INLINE void
0173 dlog_order23_clear(dlog_order23_t FLINT_UNUSED(t))
0174 {
0175     return;
0176 }
0177
0178 DLOG_INLINE void
0179 dlog_table_clear(dlog_table_t t)
0180 {
0181     flint_free(t->table);
0182 }
0183
0184 void dlog_crt_clear(dlog_crt_t t);
0185
0186 DLOG_INLINE void
0187 dlog_power_clear(dlog_power_t t)
0188 {
0189     flint_free(t->apk);
0190     dlog_precomp_clear(t->pre);
0191     flint_free(t->pre);
0192 }
0193
0194 DLOG_INLINE void
0195 dlog_modpe_clear(dlog_modpe_t t)
0196 {
0197     dlog_precomp_clear(t->modp);
0198     flint_free(t->modp);
0199 }
0200
0201 DLOG_INLINE void
0202 dlog_bsgs_clear(dlog_bsgs_t t)
0203 {
0204     flint_free(t->table);
0205 }
0206
0207 DLOG_INLINE void
0208 dlog_rho_clear(dlog_rho_t FLINT_UNUSED(t))
0209 {
0210     return;
0211 }
0212
0213 DLOG_INLINE ulong
0214 dlog_bsgs_size(ulong n, ulong num)
0215 {
0216     if (2 * num < n)
0217         return (1 + n_sqrt(n)) * (1 + n_sqrt(num));
0218     else
0219         return n;
0220 }
0221
0222 /*#define dlog_bsgs_clear(t) bsgs_table_clear(t)*/
0223
0224 ulong dlog_order23(const dlog_order23_t t, ulong b);
0225 ulong dlog_table(const dlog_table_t t, ulong b);
0226 ulong dlog_crt(const dlog_crt_t t, ulong b);
0227 ulong dlog_power(const dlog_power_t t, ulong b);
0228 ulong dlog_modpe(const dlog_modpe_t t, ulong b);
0229 ulong dlog_bsgs(const dlog_bsgs_t t, ulong b);
0230 ulong dlog_rho(const dlog_rho_t t, ulong b);
0231 ulong dlog_1modpe_1modp(ulong b1, ulong p, ulong e, ulong inv1p, nmod_t pe);
0232 ulong dlog_1modpe(const dlog_1modpe_t t, ulong b1, ulong p, ulong e, nmod_t pe);
0233 ulong dlog_mod2e_1mod4(ulong b1, ulong e, ulong inva, nmod_t pe);
0234 ulong dlog_mod2e(const dlog_modpe_t t, ulong b);
0235 /*#define dlog_bsgs(t, b) n_discrete_log_bsgs_table(t, b)*/
0236
0237 #define DLOG_SMALL_LIM 50
0238 #define DLOG_TABLE_LIM 50
0239 #define DLOG_TABLE_P_LIM 50
0240 #define DLOG_TABLE_MODPE_LIM 50
0241 #define DLOG_TABLE_PE_LIM 50
0242 #define DLOG_TABLE_N_LIM 50
0243 #define DLOG_BSGS_LIM  500
0244
0245 #define DLOG_LOOP_MAX_FACTOR 6
0246 #define DLOG_G_SMALL 0
0247 #define DLOG_G_BIG 1
0248 void dlog_n_factor_group(n_factor_t * fac, ulong bound);
0249
0250 #define DLOG_NOT_FOUND UWORD_MAX
0251 #define DLOG_NONE UWORD_MAX
0252
0253 ulong dlog_vec_pindex_factorgcd(ulong * v, ulong nv, ulong p, nmod_t mod, ulong a, ulong na, ulong loga, ulong logm1, nmod_t order, int maxtry);
0254 void dlog_vec_fill(ulong * v, ulong nv, ulong x);
0255 void dlog_vec_set_not_found(ulong *v, ulong nv, nmod_t mod);
0256 void dlog_vec_loop(ulong * v, ulong nv, ulong a, ulong va, nmod_t mod, ulong na, nmod_t order);
0257 void dlog_vec_loop_add(ulong * v, ulong nv, ulong a, ulong va, nmod_t mod, ulong na, nmod_t order);
0258 void dlog_vec_eratos_add(ulong * v, ulong nv, ulong a, ulong va, nmod_t mod, ulong na, nmod_t order);
0259 void dlog_vec_eratos(ulong * v, ulong nv, ulong a, ulong va, nmod_t mod, ulong na, nmod_t order);
0260 void dlog_vec_sieve_add(ulong * v, ulong nv, ulong a, ulong va, nmod_t mod, ulong na, nmod_t order);
0261 void dlog_vec_sieve(ulong * v, ulong nv, ulong a, ulong va, nmod_t mod, ulong na, nmod_t order);
0262 void dlog_vec_add(ulong * v, ulong nv, ulong a, ulong va, nmod_t mod, ulong na, nmod_t order);
0263 void dlog_vec(ulong * v, ulong nv, ulong a, ulong va, nmod_t mod, ulong na, nmod_t order);
0264
0265
0266 void dlog_vec_sieve_precomp(ulong *v, ulong nv, dlog_precomp_t pre,  ulong a, ulong va, nmod_t mod, ulong na, nmod_t order);
0267 void dlog_vec_sieve_add_precomp(ulong *v, ulong nv, dlog_precomp_t pre, ulong a, ulong va, nmod_t mod, ulong na, nmod_t order);
0268 void dlog_vec_add_precomp(ulong *v, ulong nv, dlog_precomp_t pre, ulong a, ulong va, nmod_t mod, ulong na, nmod_t order);
0269
0270 #ifdef __cplusplus
0271 }
0272 #endif
0273
0274 #endif