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

/*
    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 G := [{(f - gh)/p} * b mod g] p + g.

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

    Only supports aliasing between G and g.
 */
#define lift(G, g, lenG, b, lenB)                                     \
do {                                                                  \
    _fmpz_mod_vec_set_fmpz_vec(M, g, lenG, p1ctx);                    \
    _fmpz_mod_poly_rem(D, C, lenF, 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_vec_add(G, g, M, lenG - 1);                                 \
    fmpz_one(G + lenG - 1);                                           \
} while (0)

void _fmpz_poly_hensel_lift_without_inverse(fmpz *G, fmpz *H,
    const fmpz *f, slong lenF,
    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] = {1l};
    const slong lenM = FLINT_MAX(lenG, lenH);
    const slong lenE = FLINT_MAX(lenG + lenB - 2, lenH + lenA - 2);
    const slong lenD = FLINT_MAX(lenE, lenF);
    fmpz *C, *D, *E, *M;
    fmpz_mod_ctx_t p1ctx;

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

    if (lenG >= lenH)
        _fmpz_poly_mul(C, g,lenG, h, lenH);
    else
        _fmpz_poly_mul(C, h, lenH, g, lenG);
    _fmpz_vec_sub(C, f, C, lenF);
    _fmpz_vec_scalar_divexact_fmpz(D, C, lenF, p);

    fmpz_mod_ctx_init(p1ctx, p1);
    _fmpz_mod_vec_set_fmpz_vec(C, D, lenF, p1ctx);

    lift(G, g, lenG, b, lenB);
    lift(H, h, lenH, a, lenA);

    fmpz_mod_ctx_clear(p1ctx);

    _fmpz_vec_clear(C, lenF + lenD + lenE + lenM);
}

void fmpz_poly_hensel_lift_without_inverse(fmpz_poly_t Gout, fmpz_poly_t Hout,
	const fmpz_poly_t f, 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(Gout, g->length);
    fmpz_poly_fit_length(Hout, h->length);
    _fmpz_poly_set_length(Gout, g->length);
    _fmpz_poly_set_length(Hout, h->length);

    _fmpz_poly_hensel_lift_without_inverse(Gout->coeffs, Hout->coeffs,
        f->coeffs, f->length, g->coeffs, g->length, h->coeffs, h->length,
        a->coeffs, a->length, b->coeffs, b->length, p, p1);
}