source: git/factory/fac_cantzass.cc @ 31a2be7

spielwiese
Last change on this file since 31a2be7 was 9c9e2a4, checked in by Jens Schmidt <schmidt@…>, 26 years ago
^M fix. Was: Thu 27.11.1997 22:30:00 Ruediger Stobbe <rstobbe@de.oracle.com> Factory Win NT Port, see ChangeLog for details git-svn-id: file:///usr/local/Singular/svn/trunk@951 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.4 1997-12-08 18:24:28 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_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                    HH = CantorZassenhausFactorExt( j.getItem().factor(), j.getItem().exp(), &qq, AlgExtRandomF( alpha ) );
88                else
89                    HH = CantorZassenhausFactorExt( j.getItem().factor(), j.getItem().exp(), &qq, AlgExtRandomF( alpha, beta ) );
90            }
91            else  if ( galoisfield )
92                HH = CantorZassenhausFactorFFGF( j.getItem().factor(), j.getItem().exp(), q, GFRandom() );
93            else
94                HH = CantorZassenhausFactorFFGF( j.getItem().factor(), j.getItem().exp(), q, FFRandom() );
95            for ( k = HH; k.hasItem(); ++k ) {
96                fac = k.getItem().factor();
97                H.append( CFFactor( fac / LC( fac ), d ) );
98            }
99        }
100    }
101    if ( numext > 0 )
102        mpz_clear( &qq );
103    return H;
104}
105
106CFFList distinctDegreeFactorFFGF ( const CanonicalForm & f, int q )
107{
108    int i;
109    Variable x = f.mvar();
110    CanonicalForm g = f, h, r = x;
111    CFFList F;
112    i = 1;
113    while ( g.degree(x) > 0 && i <= g.degree(x) ) {
114        r = powerMod( r, q, g );
115        h = gcd( g, r - x );
116        if ( h.degree(x) > 0 ) {
117            F.append( CFFactor( h, i ) );
118            g /= h;
119        }
120        i++;
121    }
122    ASSERT( g.degree(x) == 0, "fatal fatal" );
123    return F;
124}
125
126CFFList distinctDegreeFactorExt ( const CanonicalForm & f, int p, int n )
127{
128    int i;
129    Variable x = f.mvar();
130    CanonicalForm g = f, h, r = x;
131    CFFList F;
132    i = 1;
133    while ( g.degree(x) > 0 && i <= g.degree(x) ) {
134        r = powerMod( r, p, n, g );
135        h = gcd( g, r - x );
136        if ( h.degree(x) > 0 ) {
137            F.append( CFFactor( h, i ) );
138            g /= h;
139        }
140        i++;
141    }
142    ASSERT( g.degree(x) == 0, "fatal fatal" );
143    return F;
144}
145
146CFFList CantorZassenhausFactorFFGF( const CanonicalForm & g, int s, int q, const CFRandom & gen )
147{
148    CanonicalForm f = g;
149    CanonicalForm b, f1;
150    int d, d1;
151    Variable x = f.mvar();
152
153    if ( (d=f.degree(x)) == s )
154        return CFFactor( f, 1 );
155    else while ( 1 ) {
156        b = randomPoly( d, x, gen );
157        f1 = gcd( b, f );
158        if ( (d1 = f1.degree(x)) > 0 && d1 < d )
159            return Union( CantorZassenhausFactorFFGF( f1, s, q, gen ), CantorZassenhausFactorFFGF( f/f1, s, q, gen ) );
160        else {
161            f1 = gcd( f, powerMod2( b, q, s, f ) - 1 );
162            if ( (d1 = f1.degree(x)) > 0 && d1 < d )
163                return Union( CantorZassenhausFactorFFGF( f1, s, q, gen ), CantorZassenhausFactorFFGF( f/f1, s, q, gen ) );
164        }
165    }
166}
167
168CFFList CantorZassenhausFactorExt( const CanonicalForm & g, int s, MP_INT * q, const CFRandom & gen )
169{
170    CanonicalForm f = g;
171    CanonicalForm b, f1;
172    int d, d1;
173    Variable x = f.mvar();
174
175    if ( (d=f.degree(x)) == s )
176        return CFFactor( f, 1 );
177    else while ( 1 ) {
178        b = randomPoly( d, x, gen );
179        f1 = gcd( b, f );
180        if ( (d1 = f1.degree(x)) > 0 && d1 < d )
181            return Union( CantorZassenhausFactorExt( f1, s, q, gen ), CantorZassenhausFactorExt( f/f1, s, q, gen ) );
182        else {
183            f1 = gcd( f, powerMod2( b, q, s, f ) - 1 );
184            if ( (d1 = f1.degree(x)) > 0 && d1 < d )
185                return Union( CantorZassenhausFactorExt( f1, s, q, gen ), CantorZassenhausFactorExt( f/f1, s, q, gen ) );
186        }
187    }
188}
189
190CanonicalForm randomPoly( int d, const Variable & x, const CFRandom & g )
191{
192    CanonicalForm result = 0;
193    for ( int i = 0; i < d; i++ )
194        result += power( x, i ) * g.generate();
195    result += power( x, d );
196    return result;
197}
198
199CanonicalForm powerMod( const CanonicalForm & f, int m, const CanonicalForm & d )
200{
201    CanonicalForm prod = 1;
202    CanonicalForm b = f % d;
203
204    while ( m != 0 ) {
205        if ( m % 2 != 0 )
206            prod = (prod * b) % d;
207        m /= 2;
208        if ( m != 0 )
209            b = (b * b) % d;
210    }
211    return prod;
212}
213
214CanonicalForm powerMod( const CanonicalForm & f, int p, int s, const CanonicalForm & d )
215{
216    CanonicalForm prod = 1;
217    CanonicalForm b = f % d;
218    int odd;
219
220    MP_INT m;
221
222    mpz_init( &m );
223    mpz_mypow_ui( &m, p, s );
224    while ( mpz_cmp_si( &m, 0 ) != 0 ) {
225        odd = mpz_mdivmod_ui( &m, 0, &m, 2 );
226        if ( odd != 0 )
227            prod = (prod * b) % d;
228        if ( mpz_cmp_si( &m, 0 ) != 0 )
229            b = (b*b) % d;
230    }
231    mpz_clear( &m );
232    return prod;
233}
234
235CanonicalForm powerMod2( const CanonicalForm & f, int p, int s, const CanonicalForm & d )
236{
237    CanonicalForm prod = 1;
238    CanonicalForm b = f % d;
239    int odd;
240
241    MP_INT m;
242
243    mpz_init( &m );
244    mpz_mypow_ui( &m, p, s );
245    mpz_sub_ui( &m, &m, 1 );
246    mpz_div_ui( &m, &m, 2 );
247    while ( mpz_cmp_si( &m, 0 ) != 0 ) {
248        odd = mpz_mdivmod_ui( &m, 0, &m, 2 );
249        if ( odd != 0 )
250            prod = (prod * b) % d;
251        if ( mpz_cmp_si( &m, 0 ) != 0 )
252            b = (b*b) % d;
253    }
254    mpz_clear( &m );
255    return prod;
256}
257
258CanonicalForm powerMod2( const CanonicalForm & f, MP_INT * q, int s, const CanonicalForm & d )
259{
260    CanonicalForm prod = 1;
261    CanonicalForm b = f % d;
262    int odd;
263
264    MP_INT m;
265
266    mpz_init( &m );
267    mpz_mypow( &m, q, s );
268    mpz_sub_ui( &m, &m, 1 );
269    mpz_div_ui( &m, &m, 2 );
270    while ( mpz_cmp_si( &m, 0 ) != 0 ) {
271        odd = mpz_mdivmod_ui( &m, 0, &m, 2 );
272        if ( odd != 0 )
273            prod = (prod * b) % d;
274        if ( mpz_cmp_si( &m, 0 ) != 0 )
275            b = (b*b) % d;
276    }
277    mpz_clear( &m );
278    return prod;
279}
Note: See TracBrowser for help on using the repository browser.