source: git/factory/fac_cantzass.cc @ 5e4636

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