source: git/factory/fac_cantzass.cc @ 2dd068

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