flint-sys 0.9.0

Bindings to the FLINT C library
Documentation 
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
106
107
108
109
110
111
112

/*
    Copyright (C) 2011 Andy Novocin
    Copyright (C) 2011 Sebastian Pancratz

    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 "fmpz.h"
#include "fmpz_vec.h"
#include "fmpz_poly.h"
#include "fmpz_mod.h"
#include "fmpz_mod_vec.h"
#include "fmpz_mod_poly.h"

/*
    Macro for the lift B := [{(1 - aG - bH)/p} * b mod g] p + b,
    of length at most lenG - 1.

    Assumes that {C, lenC} contains the inner part {(1 - aG - bH)/p} mod p1,
    where lenC = max(lenA + lenG - 1, lenB + lenH - 1).  Requires temporary
    space M, D, E.  We really only need
        lenM = max(lenG, lenH)
        lenE = max(lenG + lenB - 2, lenH + lenA - 2)
        lenD = max(lenC, lenE)

    Writes {B, lenG - 1}.  The cofactor that is lifted is the
    polynomial {b, lenB}, which may be aliased with B.  Although
    it suffices to have g modulo p, there is no harm in supplying
    {g, lenG} only reduced modulo p p1.
 */
#define liftinv(B, b, lenB, g, lenG)                                  \
do {                                                                  \
    _fmpz_mod_vec_set_fmpz_vec(M, g, lenG, p1ctx);                    \
    _fmpz_mod_poly_rem(D, C, lenC, M, lenG, one, p1ctx);              \
    _fmpz_mod_poly_mul(E, D, lenG - 1, b, lenB, p1ctx);               \
    if (lenB > 1)                                                     \
    {                                                                 \
        _fmpz_mod_poly_rem(D, E, lenG + lenB - 2, M, lenG, one, p1ctx);  \
        _fmpz_vec_scalar_mul_fmpz(M, D, lenG - 1, p);                 \
    }                                                                 \
    else                                                              \
    {                                                                 \
        _fmpz_vec_scalar_mul_fmpz(M, E, lenG - 1, p);                 \
    }                                                                 \
    _fmpz_poly_add(B, M, lenG - 1, b, lenB);                          \
} while (0)

void _fmpz_poly_hensel_lift_only_inverse(fmpz *A, fmpz *B,
    const fmpz *G, slong lenG, const fmpz *H, slong lenH,
    const fmpz *a, slong lenA, const fmpz *b, slong lenB,
    const fmpz_t p, const fmpz_t p1)
{
    const fmpz one[1] = {WORD(1)};
    const slong lenC = FLINT_MAX(lenA + lenG - 1, lenB + lenH - 1);
    const slong lenM = FLINT_MAX(lenG, lenH);
    const slong lenE = FLINT_MAX(lenG + lenB - 2, lenH + lenA - 2);
    const slong lenD = FLINT_MAX(lenC, lenE);
    fmpz *C, *D, *E, *M;
    fmpz_mod_ctx_t p1ctx;

    C = _fmpz_vec_init(lenC + lenD + lenD + lenM);
    D = C + lenC;
    E = D + lenD;
    M = E + lenE;

    if (lenG >= lenA)
        _fmpz_poly_mul(C, G, lenG, a, lenA);
    else
        _fmpz_poly_mul(C, a, lenA, G, lenG);
    if (lenH >= lenB)
        _fmpz_poly_mul(D, H, lenH, b, lenB);
    else
        _fmpz_poly_mul(D, b, lenB, H, lenH);
    _fmpz_vec_add(C, C, D, lenC);
    fmpz_sub_ui(C, C, 1);
    _fmpz_vec_neg(C, C, lenC);
    _fmpz_vec_scalar_divexact_fmpz(D, C, lenC, p);

    fmpz_mod_ctx_init(p1ctx, p1);

    _fmpz_mod_vec_set_fmpz_vec(C, D, lenC, p1ctx);

    liftinv(B, b, lenB, G, lenG);
    liftinv(A, a, lenA, H, lenH);

    fmpz_mod_ctx_clear(p1ctx);

    _fmpz_vec_clear(C, lenC + lenD + lenD + lenM);
}

void fmpz_poly_hensel_lift_only_inverse(fmpz_poly_t Aout, fmpz_poly_t Bout,
    const fmpz_poly_t G, const fmpz_poly_t H,
    const fmpz_poly_t a, const fmpz_poly_t b,
    const fmpz_t p, const fmpz_t p1)
{
    fmpz_poly_fit_length(Aout, H->length - 1);
    fmpz_poly_fit_length(Bout, G->length - 1);

    _fmpz_poly_hensel_lift_only_inverse(Aout->coeffs, Bout->coeffs,
        G->coeffs, G->length, H->coeffs, H->length,
        a->coeffs, a->length, b->coeffs, b->length, p, p1);

    _fmpz_poly_set_length(Aout, H->length - 1);
    _fmpz_poly_set_length(Bout, G->length - 1);
    _fmpz_poly_normalise(Aout);
    _fmpz_poly_normalise(Bout);
}