include/flint/qfb.h

0001 /*
0002     Copyright (C) 2012 William Hart
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 QFB_H
0013 #define QFB_H
0014
0015 #ifdef QFB_INLINES_C
0016 #define QFB_INLINE
0017 #else
0018 #define QFB_INLINE static inline
0019 #endif
0020
0021 #include "fmpz.h"
0022
0023 #ifdef __cplusplus
0024  extern "C" {
0025 #endif
0026
0027 typedef struct qfb
0028 {
0029     fmpz_t a;
0030     fmpz_t b;
0031     fmpz_t c;
0032 } qfb;
0033
0034 typedef qfb qfb_t[1];
0035
0036 typedef struct
0037 {
0038    qfb_t q;
0039    qfb_t q2;
0040    slong iter;
0041 } qfb_hash_t;
0042
0043 QFB_INLINE
0044 void qfb_init(qfb_t q)
0045 {
0046    fmpz_init(q->a);
0047    fmpz_init(q->b);
0048    fmpz_init(q->c);
0049 }
0050
0051 QFB_INLINE
0052 void qfb_clear(qfb_t q)
0053 {
0054    fmpz_clear(q->a);
0055    fmpz_clear(q->b);
0056    fmpz_clear(q->c);
0057 }
0058
0059 QFB_INLINE
0060 int qfb_equal(qfb_t f, qfb_t g)
0061 {
0062    return (fmpz_equal(f->a, g->a)
0063         && fmpz_equal(f->b, g->b)
0064         && fmpz_equal(f->c, g->c));
0065 }
0066
0067 QFB_INLINE
0068 void qfb_set(qfb_t f, qfb_t g)
0069 {
0070    fmpz_set(f->a, g->a);
0071    fmpz_set(f->b, g->b);
0072    fmpz_set(f->c, g->c);
0073 }
0074
0075 QFB_INLINE
0076 void qfb_discriminant(fmpz_t D, qfb_t f)
0077 {
0078    fmpz_t t;
0079    fmpz_init(t);
0080
0081    fmpz_mul(t, f->a, f->c);
0082    fmpz_mul_2exp(t, t, 2);
0083    fmpz_mul(D, f->b, f->b);
0084    fmpz_sub(D, D, t);
0085
0086    fmpz_clear(t);
0087 }
0088
0089 void qfb_print(qfb_t q);
0090
0091 QFB_INLINE
0092 void qfb_array_clear(qfb ** forms, slong num)
0093 {
0094    slong k;
0095
0096    for (k = 0; k < num; k++)
0097    {
0098       fmpz_clear((*forms)[k].a);
0099       fmpz_clear((*forms)[k].b);
0100       fmpz_clear((*forms)[k].c);
0101    }
0102    flint_free(*forms);
0103 }
0104
0105 qfb_hash_t * qfb_hash_init(slong depth);
0106
0107 void qfb_hash_clear(qfb_hash_t * qhash, slong depth);
0108
0109 void qfb_hash_insert(qfb_hash_t * qhash, qfb_t q,
0110                      qfb_t q2, slong iter, slong depth);
0111
0112 slong qfb_hash_find(qfb_hash_t * qhash, qfb_t q, slong depth);
0113
0114 void qfb_reduce(qfb_t r, qfb_t f, fmpz_t D);
0115
0116 int qfb_is_reduced(qfb_t r);
0117
0118 slong qfb_reduced_forms(qfb ** forms, slong d);
0119
0120 slong qfb_reduced_forms_large(qfb ** forms, slong d);
0121
0122 void qfb_nucomp(qfb_t r, const qfb_t f, const qfb_t g, fmpz_t D, fmpz_t L);
0123
0124 void qfb_nudupl(qfb_t r, const qfb_t f, fmpz_t D, fmpz_t L);
0125
0126 void qfb_pow_ui(qfb_t r, qfb_t f, fmpz_t D, ulong exp);
0127
0128 void qfb_pow(qfb_t r, qfb_t f, fmpz_t D, fmpz_t exp);
0129
0130 void qfb_pow_with_root(qfb_t r, qfb_t f, fmpz_t D, fmpz_t e, fmpz_t L);
0131
0132 QFB_INLINE
0133 void qfb_inverse(qfb_t r, qfb_t f)
0134 {
0135    qfb_set(r, f);
0136
0137    if (fmpz_equal(f->a, f->c)
0138     || fmpz_equal(f->a, f->b))
0139     return;
0140
0141    fmpz_neg(r->b, r->b);
0142 }
0143
0144 QFB_INLINE
0145 int qfb_is_principal_form(qfb_t f, fmpz_t D)
0146 {
0147    if (!fmpz_is_one(f->a))
0148       return 0;
0149
0150    if (fmpz_is_odd(D)) /* D = 1 mod 4 */
0151       return fmpz_is_one(f->b);
0152
0153    return fmpz_is_zero(f->b); /* D = 0 mod 4 */
0154 }
0155
0156 QFB_INLINE
0157 void qfb_principal_form(qfb_t f, fmpz_t D)
0158 {
0159    fmpz_set_ui(f->a, 1);
0160
0161    if (fmpz_is_odd(D)) /* D = 1 mod 4 */
0162       fmpz_set_ui(f->b, 1);
0163    else /* D = 0 mod 4 */
0164       fmpz_set_ui(f->b, 0);
0165
0166    fmpz_sub(f->c, f->b, D);
0167    fmpz_fdiv_q_2exp(f->c, f->c, 2);
0168 }
0169
0170 QFB_INLINE
0171 int qfb_is_primitive(qfb_t f)
0172 {
0173    fmpz_t g;
0174    int res;
0175
0176    fmpz_init(g);
0177    fmpz_gcd3(g, f->a, f->b, f->c);
0178    res = fmpz_is_pm1(g);
0179    fmpz_clear(g);
0180
0181    return res;
0182 }
0183
0184 void qfb_prime_form(qfb_t r, fmpz_t D, fmpz_t p);
0185
0186 int qfb_exponent_element(fmpz_t exponent, qfb_t f,
0187                                           fmpz_t n, ulong B1, ulong B2_sqrt);
0188
0189 int qfb_exponent(fmpz_t exponent, fmpz_t n, ulong B1, ulong B2_sqrt, slong c);
0190
0191 int qfb_exponent_grh(fmpz_t exponent, fmpz_t n, ulong B1, ulong B2_sqrt);
0192
0193 #ifdef __cplusplus
0194 }
0195 #endif
0196
0197 #endif