include/flint/aprcl.h

0001 /*
0002     Copyright (C) 2015, Vladimir Glazchev
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 APRCL_H
0013 #define APRCL_H
0014
0015 #include "limb_types.h"
0016 #include "fmpz_types.h"
0017 #include "fmpz_mod_types.h"
0018
0019 #ifdef __cplusplus
0020 extern "C" {
0021 #endif
0022
0023 #define SQUARING_SPACE 70
0024
0025 /* Configuration struct */
0026 typedef struct
0027 {
0028     ulong R;
0029     fmpz_t s;
0030     n_factor_t rs;
0031     fmpz_factor_t qs;
0032     int * qs_used;
0033 } _aprcl_config;
0034
0035 typedef _aprcl_config aprcl_config[1];
0036
0037 /* Z[unity_root_q, unity_root_p]/(n) struct */
0038 typedef struct
0039 {
0040     fmpz_mod_poly_t *polys;
0041     ulong p;
0042     ulong q;
0043     fmpz_mod_ctx_t ctx;
0044 } _unity_zpq;
0045
0046 typedef _unity_zpq unity_zpq[1];
0047
0048 /* Z[unity_root]/(n) struct */
0049 typedef struct
0050 {
0051     fmpz_mod_poly_t poly;
0052     ulong p;
0053     ulong exp;
0054     fmpz_mod_ctx_t ctx;
0055 } _unity_zp;
0056
0057 typedef _unity_zp unity_zp[1];
0058
0059 /* Primality test status */
0060 typedef enum
0061 {
0062     UNKNOWN,
0063     PRIME,
0064     COMPOSITE,
0065     PROBABPRIME
0066 } primality_test_status;
0067
0068 int _aprcl_p_ind(const aprcl_config conf, ulong p);
0069
0070 ulong aprcl_p_power_in_q(ulong q, ulong p);
0071
0072 int aprcl_is_mul_coprime_ui_ui(ulong x, ulong y, const fmpz_t n);
0073
0074 int aprcl_is_mul_coprime_ui_fmpz(ulong x, const fmpz_t y, const fmpz_t n);
0075
0076 /* primality tests ***********************************************************/
0077
0078 int aprcl_is_prime(const fmpz_t n);
0079
0080 /* Gauss test configuration */
0081 void aprcl_config_gauss_init(aprcl_config conf, const fmpz_t n);
0082 void aprcl_config_gauss_init_min_R(aprcl_config conf, const fmpz_t n, ulong R);
0083 void aprcl_config_gauss_clear(aprcl_config conf);
0084
0085 /* Jacobi test configuration */
0086 ulong aprcl_R_value(const fmpz_t n);
0087 void aprcl_config_jacobi_init(aprcl_config conf, const fmpz_t n);
0088 void aprcl_config_jacobi_clear(aprcl_config conf);
0089
0090 /*  Gauss sums primality test */
0091 int aprcl_is_prime_gauss(const fmpz_t n);
0092 int aprcl_is_prime_gauss_min_R(const fmpz_t n, ulong R);
0093
0094 primality_test_status _aprcl_is_prime_gauss(const fmpz_t n, const aprcl_config config);
0095
0096 int _aprcl_is_gausspower_2q_equal_first(ulong q, const fmpz_t n);
0097 int _aprcl_is_gausspower_2q_equal_second(ulong q, const fmpz_t n);
0098
0099 slong _aprcl_is_gausspower_from_unity_p(ulong q, ulong r, const fmpz_t n);
0100
0101 /* Jacobi sums primality test */
0102 int aprcl_is_prime_jacobi(const fmpz_t n);
0103
0104 primality_test_status _aprcl_is_prime_jacobi(const fmpz_t n, const aprcl_config config);
0105
0106 slong _aprcl_is_prime_jacobi_check_pk(const unity_zp j, const fmpz_t u, ulong v);
0107 slong _aprcl_is_prime_jacobi_check_21(ulong q, const fmpz_t n);
0108 slong _aprcl_is_prime_jacobi_check_22(const unity_zp j, const fmpz_t u, ulong v, ulong q);
0109 slong _aprcl_is_prime_jacobi_check_2k(const unity_zp j, const unity_zp j2_1, const unity_zp j2_2, const fmpz_t u, ulong v);
0110
0111 int _aprcl_is_prime_jacobi_additional_test(const fmpz_t n, ulong p);
0112
0113 /* Final division function */
0114 int aprcl_is_prime_final_division(const fmpz_t n, const fmpz_t s, ulong r);
0115
0116 /* Z[unity_root]/(n) operations **********************************************/
0117
0118 /* Memory management */
0119 void unity_zp_init(unity_zp f, ulong p, ulong exp, const fmpz_t n);
0120 void unity_zp_clear(unity_zp f);
0121
0122 void unity_zp_copy(unity_zp f, const unity_zp g);
0123 void unity_zp_swap(unity_zp f, unity_zp g);
0124
0125 void unity_zp_set_zero(unity_zp f);
0126
0127 /* Comparison */
0128 slong unity_zp_is_unity(unity_zp f);
0129
0130 int unity_zp_equal(unity_zp f, unity_zp g);
0131
0132 /* Coefficient management */
0133 void unity_zp_coeff_set_fmpz(unity_zp f, ulong ind, const fmpz_t x);
0134 void unity_zp_coeff_set_ui(unity_zp f, ulong ind, ulong x);
0135
0136 void unity_zp_coeff_add_fmpz(unity_zp f, ulong ind, const fmpz_t x);
0137 void unity_zp_coeff_add_ui(unity_zp f, ulong ind, ulong x);
0138
0139 void unity_zp_coeff_inc(unity_zp f, ulong ind);
0140 void unity_zp_coeff_dec(unity_zp f, ulong ind);
0141
0142 /* Scalar multiplication */
0143 void unity_zp_mul_scalar_ui(unity_zp f, const unity_zp g, ulong s);
0144
0145 /* Addition */
0146 void unity_zp_add(unity_zp f, const unity_zp g, const unity_zp h);
0147
0148 /* General multiplication and squaring */
0149 void unity_zp_mul(unity_zp f, const unity_zp g, const unity_zp h);
0150
0151 void unity_zp_sqr(unity_zp f, const unity_zp g);
0152
0153 /* Special multiplication and squaring */
0154 void unity_zp_mul_inplace(unity_zp f, const unity_zp g, const unity_zp h, fmpz_t * t);
0155
0156 void unity_zp_sqr_inplace(unity_zp f, const unity_zp g, fmpz_t * t);
0157
0158 void unity_zp_ar1(fmpz_t * t);
0159 void unity_zp_ar2(fmpz_t * t);
0160 void unity_zp_ar3(fmpz_t * t);
0161 void unity_zp_ar4(fmpz_t * t);
0162
0163 void unity_zp_mul3(unity_zp f, const unity_zp g, const unity_zp h, fmpz_t * t);
0164 void unity_zp_mul4(unity_zp f, const unity_zp g, const unity_zp h, fmpz_t * t);
0165 void unity_zp_mul5(unity_zp f, const unity_zp g, const unity_zp h, fmpz_t * t);
0166 void unity_zp_mul7(unity_zp f, const unity_zp g, const unity_zp h, fmpz_t * t);
0167 void unity_zp_mul8(unity_zp f, const unity_zp g, const unity_zp h, fmpz_t * t);
0168 void unity_zp_mul9(unity_zp f, const unity_zp g, const unity_zp h, fmpz_t * t);
0169 void unity_zp_mul11(unity_zp f, const unity_zp g, const unity_zp h, fmpz_t * t);
0170 void unity_zp_mul16(unity_zp f, const unity_zp g, const unity_zp h, fmpz_t * t);
0171
0172 void unity_zp_sqr3(unity_zp f, const unity_zp g, fmpz_t * t);
0173 void unity_zp_sqr4(unity_zp f, const unity_zp g, fmpz_t * t);
0174 void unity_zp_sqr5(unity_zp f, const unity_zp g, fmpz_t * t);
0175 void unity_zp_sqr7(unity_zp f, const unity_zp g, fmpz_t * t);
0176 void unity_zp_sqr8(unity_zp f, const unity_zp g, fmpz_t * t);
0177 void unity_zp_sqr9(unity_zp f, const unity_zp g, fmpz_t * t);
0178 void unity_zp_sqr11(unity_zp f, const unity_zp g, fmpz_t * t);
0179 void unity_zp_sqr16(unity_zp f, const unity_zp g, fmpz_t * t);
0180
0181 /* Powering functions */
0182 void unity_zp_pow_fmpz(unity_zp f, const unity_zp g, const fmpz_t pow);
0183 void unity_zp_pow_ui(unity_zp f, const unity_zp g, ulong pow);
0184
0185 ulong _unity_zp_pow_select_k(const fmpz_t n);
0186
0187 void unity_zp_pow_2k_fmpz(unity_zp f, const unity_zp g, const fmpz_t pow);
0188 void unity_zp_pow_2k_ui(unity_zp f, const unity_zp g, ulong pow);
0189
0190 void unity_zp_pow_sliding_fmpz(unity_zp f, unity_zp g, const fmpz_t pow);
0191
0192 /* Cyclotomic reduction */
0193 void _unity_zp_reduce_cyclotomic_divmod(unity_zp f);
0194
0195 void _unity_zp_reduce_cyclotomic(unity_zp f);
0196 void unity_zp_reduce_cyclotomic(unity_zp f, const unity_zp g);
0197
0198 /* Automorphism and inverse computation */
0199 void unity_zp_aut(unity_zp f, const unity_zp g, ulong x);
0200
0201 void unity_zp_aut_inv(unity_zp f, const unity_zp g, ulong x);
0202
0203 /* Jacobi sum computation. */
0204 nn_ptr aprcl_f_table(const ulong q);
0205
0206 void _unity_zp_jacobi_sum_pq_general(unity_zp f, const nn_ptr table, ulong p, ulong q, ulong k, ulong a, ulong b);
0207 void unity_zp_jacobi_sum_pq(unity_zp f, ulong q, ulong p);
0208
0209 void unity_zp_jacobi_sum_2q_one(unity_zp f, ulong q);
0210 void unity_zp_jacobi_sum_2q_two(unity_zp f, ulong q);
0211
0212 /* Z[unity_root_q, unity_root_p]/(n) operations ******************************/
0213
0214 /* Memory management */
0215 void unity_zpq_init(unity_zpq f, ulong q, ulong p, const fmpz_t n);
0216 void unity_zpq_clear(unity_zpq f);
0217
0218 void unity_zpq_copy(unity_zpq f, const unity_zpq g);
0219
0220 void unity_zpq_swap(unity_zpq f, unity_zpq g);
0221
0222 /* Comparison */
0223 int unity_zpq_equal(const unity_zpq f, const unity_zpq g);
0224
0225 /* Coefficient management */
0226 void unity_zpq_coeff_set_fmpz(unity_zpq f, slong i, slong j, const fmpz_t x);
0227 void unity_zpq_coeff_set_ui(unity_zpq f, slong i, slong j, ulong x);
0228
0229 void unity_zpq_coeff_add(unity_zpq f, slong i, slong j, const fmpz_t x);
0230 void unity_zpq_coeff_add_ui(unity_zpq f, slong i, slong j, ulong x);
0231
0232 /* Addition and multiplication */
0233 void unity_zpq_add(unity_zpq f, const unity_zpq g, const unity_zpq h);
0234
0235 void unity_zpq_mul(unity_zpq f, const unity_zpq g, const unity_zpq h);
0236
0237 void _unity_zpq_mul_unity_p(unity_zpq f);
0238
0239 void unity_zpq_mul_unity_p_pow(unity_zpq f, const unity_zpq g, slong p);
0240
0241 /* Powering */
0242 void unity_zpq_pow(unity_zpq f, const unity_zpq g, const fmpz_t p);
0243 void unity_zpq_pow_ui(unity_zpq f, const unity_zpq g, ulong pow);
0244
0245 /* Gauss sum computation */
0246 void unity_zpq_gauss_sum(unity_zpq f, ulong q, ulong p);
0247 void unity_zpq_gauss_sum_character_pow(unity_zpq f, ulong q, ulong p, ulong pow);
0248 void unity_zpq_gauss_sum_sigma_pow(unity_zpq f, ulong q, ulong p);
0249
0250 #ifdef __cplusplus
0251 }
0252 #endif
0253
0254 #endif