source: git/factory/fac_cantzass.cc @ c770dc

spielwiese
Last change on this file since c770dc was d67fcad, checked in by Martin Lee <martinlee84@…>, 13 years ago
deleted initializeGMP
  • Property mode set to 100644
File size: 8.4 KB
Line 
1/* emacs edit mode for this file is -*- C++ -*- */
2/* $Id$ */
3
4#include "config.h"
5
6#include "cf_assert.h"
7
8#include "cf_defs.h"
9#include "cf_random.h"
10#include "cf_util.h"
11#include "fac_cantzass.h"
12#include "fac_sqrfree.h"
13#include "gmpext.h"
14
15#include "cf_gmp.h"
16
17static CanonicalForm randomPoly( int n, const Variable & x, const CFRandom & gen );
18
19static CFFList CantorZassenhausFactorFFGF( const CanonicalForm & f, int d, int q, const CFRandom & );
20
21static CFFList CantorZassenhausFactorExt( const CanonicalForm & g, int s, MP_INT * q, const CFRandom & gen );
22
23static CFFList distinctDegreeFactorFFGF ( const CanonicalForm & f, int q );
24
25static CFFList distinctDegreeFactorExt ( const CanonicalForm & f, int p, int n );
26
27// calculates f^m % d
28
29static CanonicalForm powerMod( const CanonicalForm & f, int m, const CanonicalForm & d );
30
31// calculates f^(p^s) % d
32
33static CanonicalForm powerMod( const CanonicalForm & f, int p, int s, const CanonicalForm & d );
34
35// calculates f^((p^s-1)/2) % d
36
37static CanonicalForm powerMod2( const CanonicalForm & f, int p, int s, const CanonicalForm & d );
38
39static CanonicalForm powerMod2( const CanonicalForm & f, MP_INT * q, int s, const CanonicalForm & d );
40
41CFFList FpFactorizeUnivariateCZ( const CanonicalForm& f, bool issqrfree, int numext, const Variable alpha, const Variable beta )
42{
43    CFFList F, G, H, HH;
44    CanonicalForm fac;
45    ListIterator<CFFactor> i, j, k;
46    int d, q, n = 0;
47    bool galoisfield = getGFDegree() > 1;
48    MP_INT qq;
49
50    if ( galoisfield )
51        q = ipower( getCharacteristic(), getGFDegree() );
52    else
53        q = getCharacteristic();
54    if ( numext > 0 ) {
55        if ( numext == 1 )
56            n = getMipo( alpha ).degree();
57        else
58            n = getMipo( alpha ).degree() * getMipo( beta ).degree();
59        mpz_init( &qq );
60        mpz_ui_pow_ui ( &qq, q, n );
61    }
62    if ( LC( f ).isOne() )
63        if ( issqrfree )
64            F.append( CFFactor( f, 1 ) );
65        else
66            F = sqrFreeFp( f );
67    else {
68        if ( issqrfree )
69            F.append( CFFactor( f / LC( f ), 1 ) );
70        else
71            F = sqrFreeFp( f / LC( f ) );
72        H.append( LC( f ) );
73    }
74    for ( i = F; i.hasItem(); ++i ) {
75        d = i.getItem().exp();
76        if ( numext > 0 )
77            G = distinctDegreeFactorExt( i.getItem().factor(), q, n );
78        else
79            G = distinctDegreeFactorFFGF( i.getItem().factor(), q );
80        for ( j = G; j.hasItem(); ++j ) {
81            if ( numext > 0 ) {
82             if ( numext == 1 ) {
83                   AlgExtRandomF tmpalpha( alpha );
84                    HH = CantorZassenhausFactorExt( j.getItem().factor(), j.getItem().exp(), &qq, tmpalpha );
85             }
86             else {
87                   AlgExtRandomF tmpalphabeta( alpha, beta );
88                    HH = CantorZassenhausFactorExt( j.getItem().factor(), j.getItem().exp(), &qq, tmpalphabeta );
89             }
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            CFFList firstFactor = CantorZassenhausFactorFFGF( f1, s, q, gen );
160            CFFList secondFactor = CantorZassenhausFactorFFGF( f/f1, s, q, gen );
161            return Union( firstFactor, secondFactor );
162        } else {
163            f1 = gcd( f, powerMod2( b, q, s, f ) - 1 );
164            if ( (d1 = f1.degree(x)) > 0 && d1 < d ) {
165                CFFList firstFactor = CantorZassenhausFactorFFGF( f1, s, q, gen );
166                CFFList secondFactor = CantorZassenhausFactorFFGF( f/f1, s, q, gen );
167                return Union( firstFactor, secondFactor );
168            }
169        }
170    }
171}
172
173CFFList CantorZassenhausFactorExt( const CanonicalForm & g, int s, MP_INT * q, const CFRandom & gen )
174{
175    CanonicalForm f = g;
176    CanonicalForm b, f1;
177    int d, d1;
178    Variable x = f.mvar();
179
180    if ( (d=f.degree(x)) == s )
181        return CFFactor( f, 1 );
182    else while ( 1 ) {
183        b = randomPoly( d, x, gen );
184        f1 = gcd( b, f );
185        if ( (d1 = f1.degree(x)) > 0 && d1 < d ) {
186            CFFList firstFactor = CantorZassenhausFactorExt( f1, s, q, gen );
187            CFFList secondFactor = CantorZassenhausFactorExt( f/f1, s, q, gen );
188            return Union( firstFactor, secondFactor );
189        } else {
190            f1 = gcd( f, powerMod2( b, q, s, f ) - 1 );
191            if ( (d1 = f1.degree(x)) > 0 && d1 < d ) {
192                CFFList firstFactor = CantorZassenhausFactorExt( f1, s, q, gen );
193                CFFList secondFactor = CantorZassenhausFactorExt( f/f1, s, q, gen );
194                return Union( firstFactor, secondFactor );
195            }
196        }
197    }
198}
199
200CanonicalForm randomPoly( int d, const Variable & x, const CFRandom & g )
201{
202    CanonicalForm result = 0;
203    for ( int i = 0; i < d; i++ )
204        result += power( x, i ) * g.generate();
205    result += power( x, d );
206    return result;
207}
208
209CanonicalForm powerMod( const CanonicalForm & f, int m, const CanonicalForm & d )
210{
211    CanonicalForm prod = 1;
212    CanonicalForm b = f % d;
213
214    while ( m != 0 ) {
215        if ( m % 2 != 0 )
216            prod = (prod * b) % d;
217        m /= 2;
218        if ( m != 0 )
219            b = (b * b) % d;
220    }
221    return prod;
222}
223
224CanonicalForm powerMod( const CanonicalForm & f, int p, int s, const CanonicalForm & d )
225{
226    CanonicalForm prod = 1;
227    CanonicalForm b = f % d;
228    int odd;
229
230    MP_INT m;
231
232    mpz_init( &m );
233    mpz_ui_pow_ui ( &m, p, s );
234    while ( mpz_cmp_si( &m, 0 ) != 0 )
235    {
236        odd = mpz_fdiv_q_ui( &m, &m, 2 );
237        if ( odd != 0 )
238            prod = (prod * b) % d;
239        if ( mpz_cmp_si( &m, 0 ) != 0 )
240            b = (b*b) % d;
241    }
242    mpz_clear( &m );
243    return prod;
244}
245
246CanonicalForm powerMod2( const CanonicalForm & f, int p, int s, const CanonicalForm & d )
247{
248    CanonicalForm prod = 1;
249    CanonicalForm b = f % d;
250    int odd;
251
252    MP_INT m;
253
254    mpz_init( &m );
255    mpz_ui_pow_ui ( &m, p, s );
256    mpz_sub_ui( &m, &m, 1 );
257    mpz_fdiv_q_ui( &m, &m, 2 );
258    while ( mpz_cmp_si( &m, 0 ) != 0 )
259    {
260        odd = mpz_fdiv_q_ui( &m, &m, 2 );
261        if ( odd != 0 )
262            prod = (prod * b) % d;
263        if ( mpz_cmp_si( &m, 0 ) != 0 )
264            b = (b*b) % d;
265    }
266    mpz_clear( &m );
267    return prod;
268}
269
270CanonicalForm powerMod2( const CanonicalForm & f, MP_INT * q, int s, const CanonicalForm & d )
271{
272    CanonicalForm prod = 1;
273    CanonicalForm b = f % d;
274    int odd;
275
276    MP_INT m;
277
278    mpz_init( &m );
279    mpz_pow_ui( &m, q, s );
280    mpz_sub_ui( &m, &m, 1 );
281    mpz_fdiv_q_ui( &m, &m, 2 );
282    while ( mpz_cmp_si( &m, 0 ) != 0 )
283    {
284        odd = mpz_fdiv_q_ui( &m, &m, 2 );
285        if ( odd != 0 )
286            prod = (prod * b) % d;
287        if ( mpz_cmp_si( &m, 0 ) != 0 )
288            b = (b*b) % d;
289    }
290    mpz_clear( &m );
291    return prod;
292}
Note: See TracBrowser for help on using the repository browser.