source: git/factory/fac_cantzass.cc @ 1b82a2

spielwiese
Last change on this file since 1b82a2 was 0509dde, checked in by Hans Schönemann <hannes@…>, 19 years ago
*Rex Dieter(rdieter@math.unl.edu): gcc 3.4 patch git-svn-id: file:///usr/local/Singular/svn/trunk@7558 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 8.6 KB
Line 
1/* emacs edit mode for this file is -*- C++ -*- */
2/* $Id: fac_cantzass.cc,v 1.7 2004-10-11 10:49:20 Singular Exp $ */
3
4#include <config.h>
5
6#include "cf_gmp.h"
7
8#include "assert.h"
9
10#include "cf_defs.h"
11#include "cf_random.h"
12#include "cf_util.h"
13#include "fac_cantzass.h"
14#include "fac_sqrfree.h"
15#include "gmpext.h"
16
17int initializeGMP();
18
19static int initialized = initializeGMP();
20
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, MP_INT * 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, MP_INT * 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    MP_INT 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_mypow_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#ifdef HAVE_NTL
108    extern  int NTLcmpCF( const CFFactor & f, const CFFactor & g );
109    if(isOn(SW_USE_NTL_SORT)) H.sort(NTLcmpCF);
110#endif   
111    return H;
112}
113
114CFFList distinctDegreeFactorFFGF ( const CanonicalForm & f, int q )
115{
116    int i;
117    Variable x = f.mvar();
118    CanonicalForm g = f, h, r = x;
119    CFFList F;
120    i = 1;
121    while ( g.degree(x) > 0 && i <= g.degree(x) ) {
122        r = powerMod( r, q, g );
123        h = gcd( g, r - x );
124        if ( h.degree(x) > 0 ) {
125            F.append( CFFactor( h, i ) );
126            g /= h;
127        }
128        i++;
129    }
130    ASSERT( g.degree(x) == 0, "fatal fatal" );
131    return F;
132}
133
134CFFList distinctDegreeFactorExt ( const CanonicalForm & f, int p, int n )
135{
136    int i;
137    Variable x = f.mvar();
138    CanonicalForm g = f, h, r = x;
139    CFFList F;
140    i = 1;
141    while ( g.degree(x) > 0 && i <= g.degree(x) ) {
142        r = powerMod( r, p, n, g );
143        h = gcd( g, r - x );
144        if ( h.degree(x) > 0 ) {
145            F.append( CFFactor( h, i ) );
146            g /= h;
147        }
148        i++;
149    }
150    ASSERT( g.degree(x) == 0, "fatal fatal" );
151    return F;
152}
153
154CFFList CantorZassenhausFactorFFGF( const CanonicalForm & g, int s, int q, const CFRandom & gen )
155{
156    CanonicalForm f = g;
157    CanonicalForm b, f1;
158    int d, d1;
159    Variable x = f.mvar();
160
161    if ( (d=f.degree(x)) == s )
162        return CFFactor( f, 1 );
163    else while ( 1 ) {
164        b = randomPoly( d, x, gen );
165        f1 = gcd( b, f );
166        if ( (d1 = f1.degree(x)) > 0 && d1 < d ) {
167            CFFList firstFactor = CantorZassenhausFactorFFGF( f1, s, q, gen );
168            CFFList secondFactor = CantorZassenhausFactorFFGF( f/f1, s, q, gen );
169            return Union( firstFactor, secondFactor );
170        } else {
171            f1 = gcd( f, powerMod2( b, q, s, f ) - 1 );
172            if ( (d1 = f1.degree(x)) > 0 && d1 < d ) {
173                CFFList firstFactor = CantorZassenhausFactorFFGF( f1, s, q, gen );
174                CFFList secondFactor = CantorZassenhausFactorFFGF( f/f1, s, q, gen );
175                return Union( firstFactor, secondFactor );
176            }
177        }
178    }
179}
180
181CFFList CantorZassenhausFactorExt( const CanonicalForm & g, int s, MP_INT * q, const CFRandom & gen )
182{
183    CanonicalForm f = g;
184    CanonicalForm b, f1;
185    int d, d1;
186    Variable x = f.mvar();
187
188    if ( (d=f.degree(x)) == s )
189        return CFFactor( f, 1 );
190    else while ( 1 ) {
191        b = randomPoly( d, x, gen );
192        f1 = gcd( b, f );
193        if ( (d1 = f1.degree(x)) > 0 && d1 < d ) {
194            CFFList firstFactor = CantorZassenhausFactorExt( f1, s, q, gen );
195            CFFList secondFactor = CantorZassenhausFactorExt( f/f1, s, q, gen );
196            return Union( firstFactor, secondFactor );
197        } else {
198            f1 = gcd( f, powerMod2( b, q, s, f ) - 1 );
199            if ( (d1 = f1.degree(x)) > 0 && d1 < d ) {
200                CFFList firstFactor = CantorZassenhausFactorExt( f1, s, q, gen );
201                CFFList secondFactor = CantorZassenhausFactorExt( f/f1, s, q, gen );
202                return Union( firstFactor, secondFactor );
203            }
204        }
205    }
206}
207
208CanonicalForm randomPoly( int d, const Variable & x, const CFRandom & g )
209{
210    CanonicalForm result = 0;
211    for ( int i = 0; i < d; i++ )
212        result += power( x, i ) * g.generate();
213    result += power( x, d );
214    return result;
215}
216
217CanonicalForm powerMod( const CanonicalForm & f, int m, const CanonicalForm & d )
218{
219    CanonicalForm prod = 1;
220    CanonicalForm b = f % d;
221
222    while ( m != 0 ) {
223        if ( m % 2 != 0 )
224            prod = (prod * b) % d;
225        m /= 2;
226        if ( m != 0 )
227            b = (b * b) % d;
228    }
229    return prod;
230}
231
232CanonicalForm powerMod( const CanonicalForm & f, int p, int s, const CanonicalForm & d )
233{
234    CanonicalForm prod = 1;
235    CanonicalForm b = f % d;
236    int odd;
237
238    MP_INT m;
239
240    mpz_init( &m );
241    mpz_mypow_ui( &m, p, s );
242    while ( mpz_cmp_si( &m, 0 ) != 0 ) {
243        odd = mpz_mdivmod_ui( &m, 0, &m, 2 );
244        if ( odd != 0 )
245            prod = (prod * b) % d;
246        if ( mpz_cmp_si( &m, 0 ) != 0 )
247            b = (b*b) % d;
248    }
249    mpz_clear( &m );
250    return prod;
251}
252
253CanonicalForm powerMod2( const CanonicalForm & f, int p, int s, const CanonicalForm & d )
254{
255    CanonicalForm prod = 1;
256    CanonicalForm b = f % d;
257    int odd;
258
259    MP_INT m;
260
261    mpz_init( &m );
262    mpz_mypow_ui( &m, p, s );
263    mpz_sub_ui( &m, &m, 1 );
264    mpz_div_ui( &m, &m, 2 );
265    while ( mpz_cmp_si( &m, 0 ) != 0 ) {
266        odd = mpz_mdivmod_ui( &m, 0, &m, 2 );
267        if ( odd != 0 )
268            prod = (prod * b) % d;
269        if ( mpz_cmp_si( &m, 0 ) != 0 )
270            b = (b*b) % d;
271    }
272    mpz_clear( &m );
273    return prod;
274}
275
276CanonicalForm powerMod2( const CanonicalForm & f, MP_INT * q, int s, const CanonicalForm & d )
277{
278    CanonicalForm prod = 1;
279    CanonicalForm b = f % d;
280    int odd;
281
282    MP_INT m;
283
284    mpz_init( &m );
285    mpz_mypow( &m, q, s );
286    mpz_sub_ui( &m, &m, 1 );
287    mpz_div_ui( &m, &m, 2 );
288    while ( mpz_cmp_si( &m, 0 ) != 0 ) {
289        odd = mpz_mdivmod_ui( &m, 0, &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}
Note: See TracBrowser for help on using the repository browser.