source: git/factory/fac_cantzass.cc @ d1427e8

fieker-DuValspielwiese
Last change on this file since d1427e8 was d1427e8, checked in by Hans Schoenemann <hannes@…>, 4 years ago
factory: support FLINT 2.5.2
  • Property mode set to 100644
File size: 8.4 KB
Line 
1/* emacs edit mode for this file is -*- C++ -*- */
2
3#include <config.h>
4
5#include "factory/cf_gmp.h"
6
7#include "assert.h"
8
9#include "cf_defs.h"
10#include "cf_random.h"
11#include "cf_util.h"
12#include "fac_cantzass.h"
13#include "fac_sqrfree.h"
14#include "gmpext.h"
15
16#ifdef HAVE_FLINT
17#include"FLINTconvert.h"
18#endif
19
20#if !defined(HAVE_NTL)
21#if !defined(HAVE_FLINT)||(__FLINT_RELEASE<=20600)
22static CanonicalForm randomPoly( int n, const Variable & x, const CFRandom & gen );
23
24static CFFList CantorZassenhausFactorFFGF( const CanonicalForm & f, int d, int q, const CFRandom & );
25
26static CFFList CantorZassenhausFactorExt( const CanonicalForm & g, int s, mpz_t q, const CFRandom & gen );
27
28static CFFList distinctDegreeFactorFFGF ( const CanonicalForm & f, int q );
29
30static CFFList distinctDegreeFactorExt ( const CanonicalForm & f, int p, int n );
31
32// calculates f^m % d
33
34static CanonicalForm powerMod( const CanonicalForm & f, int m, const CanonicalForm & d );
35
36// calculates f^(p^s) % d
37
38static CanonicalForm powerMod( const CanonicalForm & f, int p, int s, const CanonicalForm & d );
39
40// calculates f^((p^s-1)/2) % d
41
42static CanonicalForm powerMod2( const CanonicalForm & f, int p, int s, const CanonicalForm & d );
43
44static CanonicalForm powerMod2( const CanonicalForm & f, mpz_t q, int s, const CanonicalForm & d );
45
46CFFList FpFactorizeUnivariateCZ( const CanonicalForm& f, bool issqrfree, int numext, const Variable alpha, const Variable beta )
47{
48    CFFList F, G, H, HH;
49    CanonicalForm fac;
50    ListIterator<CFFactor> i, j, k;
51    int d, q, n = 0;
52    bool galoisfield = getGFDegree() > 1;
53    mpz_t qq;
54
55    if ( galoisfield )
56        q = ipower( getCharacteristic(), getGFDegree() );
57    else
58        q = getCharacteristic();
59    if ( numext > 0 ) {
60        if ( numext == 1 )
61            n = getMipo( alpha ).degree();
62        else
63            n = getMipo( alpha ).degree() * getMipo( beta ).degree();
64        mpz_init( qq );
65        mpz_ui_pow_ui ( qq, q, n );
66    }
67    if ( LC( f ).isOne() )
68        if ( issqrfree )
69            F.append( CFFactor( f, 1 ) );
70        else
71            F = sqrFreeFp( f );
72    else {
73        if ( issqrfree )
74            F.append( CFFactor( f / LC( f ), 1 ) );
75        else
76            F = sqrFreeFp( f / LC( f ) );
77        H.append( LC( f ) );
78    }
79    for ( i = F; i.hasItem(); ++i ) {
80        d = i.getItem().exp();
81        if ( numext > 0 )
82            G = distinctDegreeFactorExt( i.getItem().factor(), q, n );
83        else
84            G = distinctDegreeFactorFFGF( i.getItem().factor(), q );
85        for ( j = G; j.hasItem(); ++j ) {
86            if ( numext > 0 ) {
87             if ( numext == 1 ) {
88                   AlgExtRandomF tmpalpha( alpha );
89                    HH = CantorZassenhausFactorExt( j.getItem().factor(), j.getItem().exp(), qq, tmpalpha );
90             }
91             else {
92                   AlgExtRandomF tmpalphabeta( alpha, beta );
93                    HH = CantorZassenhausFactorExt( j.getItem().factor(), j.getItem().exp(), qq, tmpalphabeta );
94             }
95            }
96            else  if ( galoisfield )
97                HH = CantorZassenhausFactorFFGF( j.getItem().factor(), j.getItem().exp(), q, GFRandom() );
98            else
99                HH = CantorZassenhausFactorFFGF( j.getItem().factor(), j.getItem().exp(), q, FFRandom() );
100            for ( k = HH; k.hasItem(); ++k ) {
101                fac = k.getItem().factor();
102                H.append( CFFactor( fac / LC( fac ), d ) );
103            }
104        }
105    }
106    if ( numext > 0 )
107        mpz_clear( qq );
108    return H;
109}
110
111CFFList distinctDegreeFactorFFGF ( const CanonicalForm & f, int q )
112{
113    int i;
114    Variable x = f.mvar();
115    CanonicalForm g = f, h, r = x;
116    CFFList F;
117    i = 1;
118    while ( g.degree(x) > 0 && i <= g.degree(x) ) {
119        r = powerMod( r, q, g );
120        h = gcd( g, r - x );
121        if ( h.degree(x) > 0 ) {
122            F.append( CFFactor( h, i ) );
123            g /= h;
124        }
125        i++;
126    }
127    ASSERT( g.degree(x) == 0, "fatal fatal" );
128    return F;
129}
130
131CFFList distinctDegreeFactorExt ( const CanonicalForm & f, int p, int n )
132{
133    int i;
134    Variable x = f.mvar();
135    CanonicalForm g = f, h, r = x;
136    CFFList F;
137    i = 1;
138    while ( g.degree(x) > 0 && i <= g.degree(x) ) {
139        r = powerMod( r, p, n, g );
140        h = gcd( g, r - x );
141        if ( h.degree(x) > 0 ) {
142            F.append( CFFactor( h, i ) );
143            g /= h;
144        }
145        i++;
146    }
147    ASSERT( g.degree(x) == 0, "fatal fatal" );
148    return F;
149}
150
151CFFList CantorZassenhausFactorFFGF( const CanonicalForm & g, int s, int q, const CFRandom & gen )
152{
153    CanonicalForm f = g;
154    CanonicalForm b, f1;
155    int d, d1;
156    Variable x = f.mvar();
157
158    if ( (d=f.degree(x)) == s )
159        return CFFactor( f, 1 );
160    else while ( 1 ) {
161        b = randomPoly( d, x, gen );
162        f1 = gcd( b, f );
163        if ( (d1 = f1.degree(x)) > 0 && d1 < d ) {
164            CFFList firstFactor = CantorZassenhausFactorFFGF( f1, s, q, gen );
165            CFFList secondFactor = CantorZassenhausFactorFFGF( f/f1, s, q, gen );
166            return Union( firstFactor, secondFactor );
167        } else {
168            f1 = gcd( f, powerMod2( b, q, s, f ) - 1 );
169            if ( (d1 = f1.degree(x)) > 0 && d1 < d ) {
170                CFFList firstFactor = CantorZassenhausFactorFFGF( f1, s, q, gen );
171                CFFList secondFactor = CantorZassenhausFactorFFGF( f/f1, s, q, gen );
172                return Union( firstFactor, secondFactor );
173            }
174        }
175    }
176}
177
178CFFList CantorZassenhausFactorExt( const CanonicalForm & g, int s, mpz_t q, const CFRandom & gen )
179{
180    CanonicalForm f = g;
181    CanonicalForm b, f1;
182    int d, d1;
183    Variable x = f.mvar();
184
185    if ( (d=f.degree(x)) == s )
186        return CFFactor( f, 1 );
187    else while ( 1 ) {
188        b = randomPoly( d, x, gen );
189        f1 = gcd( b, f );
190        if ( (d1 = f1.degree(x)) > 0 && d1 < d ) {
191            CFFList firstFactor = CantorZassenhausFactorExt( f1, s, q, gen );
192            CFFList secondFactor = CantorZassenhausFactorExt( f/f1, s, q, gen );
193            return Union( firstFactor, secondFactor );
194        } else {
195            f1 = gcd( f, powerMod2( b, q, s, f ) - 1 );
196            if ( (d1 = f1.degree(x)) > 0 && d1 < d ) {
197                CFFList firstFactor = CantorZassenhausFactorExt( f1, s, q, gen );
198                CFFList secondFactor = CantorZassenhausFactorExt( f/f1, s, q, gen );
199                return Union( firstFactor, secondFactor );
200            }
201        }
202    }
203}
204
205CanonicalForm randomPoly( int d, const Variable & x, const CFRandom & g )
206{
207    CanonicalForm result = 0;
208    for ( int i = 0; i < d; i++ )
209        result += power( x, i ) * g.generate();
210    result += power( x, d );
211    return result;
212}
213
214CanonicalForm powerMod( const CanonicalForm & f, int m, const CanonicalForm & d )
215{
216    CanonicalForm prod = 1;
217    CanonicalForm b = f % d;
218
219    while ( m != 0 ) {
220        if ( m % 2 != 0 )
221            prod = (prod * b) % d;
222        m /= 2;
223        if ( m != 0 )
224            b = (b * b) % d;
225    }
226    return prod;
227}
228
229CanonicalForm powerMod( const CanonicalForm & f, int p, int s, const CanonicalForm & d )
230{
231    CanonicalForm prod = 1;
232    CanonicalForm b = f % d;
233    int odd;
234
235    mpz_t m;
236
237    mpz_init( m );
238    mpz_ui_pow_ui ( m, p, s );
239    while ( mpz_cmp_si( m, 0 ) != 0 )
240    {
241        odd = mpz_fdiv_q_ui( m, m, 2 );
242        if ( odd != 0 )
243            prod = (prod * b) % d;
244        if ( mpz_cmp_si( m, 0 ) != 0 )
245            b = (b*b) % d;
246    }
247    mpz_clear( m );
248    return prod;
249}
250
251CanonicalForm powerMod2( const CanonicalForm & f, int p, int s, const CanonicalForm & d )
252{
253    CanonicalForm prod = 1;
254    CanonicalForm b = f % d;
255    int odd;
256
257    mpz_t m;
258
259    mpz_init( m );
260    mpz_ui_pow_ui ( m, p, s );
261    mpz_sub_ui( m, m, 1 );
262    mpz_fdiv_q_ui( m, m, 2 );
263    while ( mpz_cmp_si( m, 0 ) != 0 )
264    {
265        odd = mpz_fdiv_q_ui( m, m, 2 );
266        if ( odd != 0 )
267            prod = (prod * b) % d;
268        if ( mpz_cmp_si( m, 0 ) != 0 )
269            b = (b*b) % d;
270    }
271    mpz_clear( m );
272    return prod;
273}
274
275CanonicalForm powerMod2( const CanonicalForm & f, mpz_t q, int s, const CanonicalForm & d )
276{
277    CanonicalForm prod = 1;
278    CanonicalForm b = f % d;
279    int odd;
280
281    mpz_t m;
282
283    mpz_init( m );
284    mpz_pow_ui( m, q, s );
285    mpz_sub_ui( m, m, 1 );
286    mpz_fdiv_q_ui( m, m, 2 );
287    while ( mpz_cmp_si( m, 0 ) != 0 )
288    {
289        odd = mpz_fdiv_q_ui( m, m, 2 );
290        if ( odd != 0 )
291            prod = (prod * b) % d;
292        if ( mpz_cmp_si( m, 0 ) != 0 )
293            b = (b*b) % d;
294    }
295    mpz_clear( m );
296    return prod;
297}
298#endif
299#endif
Note: See TracBrowser for help on using the repository browser.