source: git/factory/fac_cantzass.cc @ 96113d

spielwiese
Last change on this file since 96113d was 0009d2, checked in by Hans Schoenemann <hannes@…>, 4 years ago
fix: handle trival case (deg<=1)
  • 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)
21static CanonicalForm randomPoly( int n, const Variable & x, const CFRandom & gen );
22
23static CFFList CantorZassenhausFactorFFGF( const CanonicalForm & f, int d, int q, const CFRandom & );
24
25static CFFList CantorZassenhausFactorExt( const CanonicalForm & g, int s, mpz_t q, const CFRandom & gen );
26
27static CFFList distinctDegreeFactorFFGF ( const CanonicalForm & f, int q );
28
29static CFFList distinctDegreeFactorExt ( const CanonicalForm & f, int p, int n );
30
31// calculates f^m % d
32
33static CanonicalForm powerMod( const CanonicalForm & f, int m, const CanonicalForm & d );
34
35// calculates f^(p^s) % d
36
37static CanonicalForm powerMod( const CanonicalForm & f, int p, int s, const CanonicalForm & d );
38
39// calculates f^((p^s-1)/2) % d
40
41static CanonicalForm powerMod2( const CanonicalForm & f, int p, int s, const CanonicalForm & d );
42
43static CanonicalForm powerMod2( const CanonicalForm & f, mpz_t q, int s, const CanonicalForm & d );
44
45CFFList FpFactorizeUnivariateCZ( const CanonicalForm& f, bool issqrfree, int numext, const Variable alpha, const Variable beta )
46{
47    CFFList F, G, H, HH;
48    CanonicalForm fac;
49    ListIterator<CFFactor> i, j, k;
50    int d, q, n = 0;
51    bool galoisfield = getGFDegree() > 1;
52    mpz_t qq;
53
54    if ( galoisfield )
55        q = ipower( getCharacteristic(), getGFDegree() );
56    else
57        q = getCharacteristic();
58    if ( numext > 0 ) {
59        if ( numext == 1 )
60            n = getMipo( alpha ).degree();
61        else
62            n = getMipo( alpha ).degree() * getMipo( beta ).degree();
63        mpz_init( qq );
64        mpz_ui_pow_ui ( qq, q, n );
65    }
66    if ( LC( f ).isOne() )
67        if ( issqrfree )
68            F.append( CFFactor( f, 1 ) );
69        else
70            F = sqrFreeFp( f );
71    else {
72        if ( issqrfree )
73            F.append( CFFactor( f / LC( f ), 1 ) );
74        else
75            F = sqrFreeFp( f / LC( f ) );
76        H.append( LC( f ) );
77    }
78    for ( i = F; i.hasItem(); ++i ) {
79        d = i.getItem().exp();
80        if ( numext > 0 )
81            G = distinctDegreeFactorExt( i.getItem().factor(), q, n );
82        else
83            G = distinctDegreeFactorFFGF( i.getItem().factor(), q );
84        for ( j = G; j.hasItem(); ++j ) {
85            if ( numext > 0 ) {
86             if ( numext == 1 ) {
87                   AlgExtRandomF tmpalpha( alpha );
88                    HH = CantorZassenhausFactorExt( j.getItem().factor(), j.getItem().exp(), qq, tmpalpha );
89             }
90             else {
91                   AlgExtRandomF tmpalphabeta( alpha, beta );
92                    HH = CantorZassenhausFactorExt( j.getItem().factor(), j.getItem().exp(), qq, tmpalphabeta );
93             }
94            }
95            else  if ( galoisfield )
96                HH = CantorZassenhausFactorFFGF( j.getItem().factor(), j.getItem().exp(), q, GFRandom() );
97            else
98                HH = CantorZassenhausFactorFFGF( j.getItem().factor(), j.getItem().exp(), q, FFRandom() );
99            for ( k = HH; k.hasItem(); ++k ) {
100                fac = k.getItem().factor();
101                H.append( CFFactor( fac / LC( fac ), d ) );
102            }
103        }
104    }
105    if ( numext > 0 )
106        mpz_clear( qq );
107    return H;
108}
109
110CFFList distinctDegreeFactorFFGF ( const CanonicalForm & f, int q )
111{
112    int i;
113    Variable x = f.mvar();
114    CanonicalForm g = f, h, r = x;
115    CFFList F;
116    i = 1;
117    while ( g.degree(x) > 0 && i <= g.degree(x) ) {
118        r = powerMod( r, q, g );
119        h = gcd( g, r - x );
120        if ( h.degree(x) > 0 ) {
121            F.append( CFFactor( h, i ) );
122            g /= h;
123        }
124        i++;
125    }
126    ASSERT( g.degree(x) == 0, "fatal fatal" );
127    return F;
128}
129
130CFFList distinctDegreeFactorExt ( const CanonicalForm & f, int p, int n )
131{
132    Variable x = f.mvar();
133    if (f.degree(x) <= 1) return CFFList(CFFactor(f,1));
134    int i;
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
Note: See TracBrowser for help on using the repository browser.