source: git/factory/fac_cantzass.cc @ 72dd6e

spielwiese
Last change on this file since 72dd6e was 493c477, checked in by Jens Schmidt <schmidt@…>, 27 years ago
o header fixed git-svn-id: file:///usr/local/Singular/svn/trunk@404 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 7.2 KB
Line 
1/* emacs edit mode for this file is -*- C++ -*- */
2/* $Id: fac_cantzass.cc,v 1.2 1997-06-19 12:23:43 schmidt 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_globals.h"
12#include "cf_random.h"
13#include "cf_util.h"
14#include "fac_cantzass.h"
15#include "fac_sqrfree.h"
16#include "gmpext.h"
17
18int initializeGMP();
19
20static int initialized = initializeGMP();
21
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, MP_INT * 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, MP_INT * 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    MP_INT 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_mypow_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                    HH = CantorZassenhausFactorExt( j.getItem().factor(), j.getItem().exp(), &qq, AlgExtRandomF( alpha ) );
89                else
90                    HH = CantorZassenhausFactorExt( j.getItem().factor(), j.getItem().exp(), &qq, AlgExtRandomF( alpha, beta ) );
91            }
92            else  if ( galoisfield )
93                HH = CantorZassenhausFactorFFGF( j.getItem().factor(), j.getItem().exp(), q, GFRandom() );
94            else
95                HH = CantorZassenhausFactorFFGF( j.getItem().factor(), j.getItem().exp(), q, FFRandom() );
96            for ( k = HH; k.hasItem(); ++k ) {
97                fac = k.getItem().factor();
98                H.append( CFFactor( fac / LC( fac ), d ) );
99            }
100        }
101    }
102    if ( numext > 0 )
103        mpz_clear( &qq );
104    return H;
105}
106
107CFFList distinctDegreeFactorFFGF ( const CanonicalForm & f, int q )
108{
109    int i;
110    Variable x = f.mvar();
111    CanonicalForm g = f, h, r = x;
112    CFFList F;
113    i = 1;
114    while ( g.degree(x) > 0 && i <= g.degree(x) ) {
115        r = powerMod( r, q, g );
116        h = gcd( g, r - x );
117        if ( h.degree(x) > 0 ) {
118            F.append( CFFactor( h, i ) );
119            g /= h;
120        }
121        i++;
122    }
123    ASSERT( g.degree(x) == 0, "fatal fatal" );
124    return F;
125}
126
127CFFList distinctDegreeFactorExt ( const CanonicalForm & f, int p, int n )
128{
129    int i;
130    Variable x = f.mvar();
131    CanonicalForm g = f, h, r = x;
132    CFFList F;
133    i = 1;
134    while ( g.degree(x) > 0 && i <= g.degree(x) ) {
135        r = powerMod( r, p, n, g );
136        h = gcd( g, r - x );
137        if ( h.degree(x) > 0 ) {
138            F.append( CFFactor( h, i ) );
139            g /= h;
140        }
141        i++;
142    }
143    ASSERT( g.degree(x) == 0, "fatal fatal" );
144    return F;
145}
146
147CFFList CantorZassenhausFactorFFGF( const CanonicalForm & g, int s, int q, const CFRandom & gen )
148{
149    CanonicalForm f = g;
150    CanonicalForm b, f1;
151    int d, d1;
152    Variable x = f.mvar();
153
154    if ( (d=f.degree(x)) == s )
155        return CFFactor( f, 1 );
156    else while ( 1 ) {
157        b = randomPoly( d, x, gen );
158        f1 = gcd( b, f );
159        if ( (d1 = f1.degree(x)) > 0 && d1 < d )
160            return Union( CantorZassenhausFactorFFGF( f1, s, q, gen ), CantorZassenhausFactorFFGF( f/f1, s, q, gen ) );
161        else {
162            f1 = gcd( f, powerMod2( b, q, s, f ) - 1 );
163            if ( (d1 = f1.degree(x)) > 0 && d1 < d )
164                return Union( CantorZassenhausFactorFFGF( f1, s, q, gen ), CantorZassenhausFactorFFGF( f/f1, s, q, gen ) );
165        }
166    }
167}
168
169CFFList CantorZassenhausFactorExt( const CanonicalForm & g, int s, MP_INT * q, const CFRandom & gen )
170{
171    CanonicalForm f = g;
172    CanonicalForm b, f1;
173    int d, d1;
174    Variable x = f.mvar();
175
176    if ( (d=f.degree(x)) == s )
177        return CFFactor( f, 1 );
178    else while ( 1 ) {
179        b = randomPoly( d, x, gen );
180        f1 = gcd( b, f );
181        if ( (d1 = f1.degree(x)) > 0 && d1 < d )
182            return Union( CantorZassenhausFactorExt( f1, s, q, gen ), CantorZassenhausFactorExt( f/f1, s, q, gen ) );
183        else {
184            f1 = gcd( f, powerMod2( b, q, s, f ) - 1 );
185            if ( (d1 = f1.degree(x)) > 0 && d1 < d )
186                return Union( CantorZassenhausFactorExt( f1, s, q, gen ), CantorZassenhausFactorExt( f/f1, s, q, gen ) );
187        }
188    }
189}
190
191CanonicalForm randomPoly( int d, const Variable & x, const CFRandom & g )
192{
193    CanonicalForm result = 0;
194    for ( int i = 0; i < d; i++ )
195        result += power( x, i ) * g.generate();
196    result += power( x, d );
197    return result;
198}
199
200CanonicalForm powerMod( const CanonicalForm & f, int m, const CanonicalForm & d )
201{
202    CanonicalForm prod = 1;
203    CanonicalForm b = f % d;
204
205    while ( m != 0 ) {
206        if ( m % 2 != 0 )
207            prod = (prod * b) % d;
208        m /= 2;
209        if ( m != 0 )
210            b = (b * b) % d;
211    }
212    return prod;
213}
214
215CanonicalForm powerMod( const CanonicalForm & f, int p, int s, const CanonicalForm & d )
216{
217    CanonicalForm prod = 1;
218    CanonicalForm b = f % d;
219    int odd;
220
221    MP_INT m;
222
223    mpz_init( &m );
224    mpz_mypow_ui( &m, p, s );
225    while ( mpz_cmp_si( &m, 0 ) != 0 ) {
226        odd = mpz_mdivmod_ui( &m, 0, &m, 2 );
227        if ( odd != 0 )
228            prod = (prod * b) % d;
229        if ( mpz_cmp_si( &m, 0 ) != 0 )
230            b = (b*b) % d;
231    }
232    mpz_clear( &m );
233    return prod;
234}
235
236CanonicalForm powerMod2( const CanonicalForm & f, int p, int s, const CanonicalForm & d )
237{
238    CanonicalForm prod = 1;
239    CanonicalForm b = f % d;
240    int odd;
241
242    MP_INT m;
243
244    mpz_init( &m );
245    mpz_mypow_ui( &m, p, s );
246    mpz_sub_ui( &m, &m, 1 );
247    mpz_div_ui( &m, &m, 2 );
248    while ( mpz_cmp_si( &m, 0 ) != 0 ) {
249        odd = mpz_mdivmod_ui( &m, 0, &m, 2 );
250        if ( odd != 0 )
251            prod = (prod * b) % d;
252        if ( mpz_cmp_si( &m, 0 ) != 0 )
253            b = (b*b) % d;
254    }
255    mpz_clear( &m );
256    return prod;
257}
258
259CanonicalForm powerMod2( const CanonicalForm & f, MP_INT * q, int s, const CanonicalForm & d )
260{
261    CanonicalForm prod = 1;
262    CanonicalForm b = f % d;
263    int odd;
264
265    MP_INT m;
266
267    mpz_init( &m );
268    mpz_mypow( &m, q, s );
269    mpz_sub_ui( &m, &m, 1 );
270    mpz_div_ui( &m, &m, 2 );
271    while ( mpz_cmp_si( &m, 0 ) != 0 ) {
272        odd = mpz_mdivmod_ui( &m, 0, &m, 2 );
273        if ( odd != 0 )
274            prod = (prod * b) % d;
275        if ( mpz_cmp_si( &m, 0 ) != 0 )
276            b = (b*b) % d;
277    }
278    mpz_clear( &m );
279    return prod;
280}
Note: See TracBrowser for help on using the repository browser.