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

/*
    Copyright (C) 2013 Mike Hansen
    Copyright (C) 2024 Albin Ahlbäck

    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/>.
*/

#ifdef T

#include "templates.h"

void
TEMPLATE(T, poly_randtest_irreducible) (TEMPLATE(T, poly_t) f,
                                        flint_rand_t state, slong len,
                                        const TEMPLATE(T, ctx_t) ctx)
{
    TEMPLATE(T, poly_t) xq, xqi, x, g_i, finv;
    fmpz_t q;
    slong i, restart;

    /* Compute q */
#if defined(FQ_NMOD_POLY_H) || defined(FQ_ZECH_POLY_H)
    fmpz_init(q);
    fmpz_ui_pow_ui(q, TEMPLATE(T, ctx_prime)(ctx), TEMPLATE(T, ctx_degree)(ctx));
#else
    fmpz_init_set(q, TEMPLATE(T, ctx_prime)(ctx));
    fmpz_pow_ui(q, q, TEMPLATE(T, ctx_degree)(ctx));
#endif

    TEMPLATE(T, poly_init) (x, ctx);
    TEMPLATE(T, poly_gen) (x, ctx);
    TEMPLATE(T, poly_init) (xq, ctx);
    TEMPLATE(T, poly_init) (xqi, ctx);
    TEMPLATE(T, poly_init) (g_i, ctx);
    TEMPLATE(T, poly_init) (finv, ctx);

    while (1)
    {
        restart = 0;

        /* Generate random monic polynomial of length len */
        TEMPLATE(T, poly_randtest_monic) (f, state, len, ctx);

        TEMPLATE(T, poly_reverse) (finv, f, f->length, ctx);
        TEMPLATE(T, poly_inv_series_newton) (finv, finv, f->length, ctx);

        /* Compute xq = x^q mod f */
        TEMPLATE(T, poly_powmod_fmpz_binexp_preinv) (xq, x, q, f, finv, ctx);
        TEMPLATE(T, poly_set) (xqi, xq, ctx);

        for (i = 1; i <= (len - 1) / 2; i++)
        {
            TEMPLATE(T, poly_sub) (xqi, xqi, x, ctx);
            TEMPLATE(T, poly_gcd) (g_i, xqi, f, ctx);
            TEMPLATE(T, poly_add) (xqi, xqi, x, ctx);
            if (!TEMPLATE(T, poly_is_one) (g_i, ctx))
            {
                restart = 1;
                break;
            }
            TEMPLATE(T, poly_compose_mod_brent_kung_preinv) (xqi, xqi, xq, f,
                                                             finv, ctx);

        }
        if (!restart)
        {
            break;
        }
    }

    TEMPLATE(T, poly_clear) (x, ctx);
    TEMPLATE(T, poly_clear) (xq, ctx);
    TEMPLATE(T, poly_clear) (xqi, ctx);
    TEMPLATE(T, poly_clear) (g_i, ctx);
    TEMPLATE(T, poly_clear) (finv, ctx);
    fmpz_clear(q);
}


#endif