source: git/factory/fac_cantzass.cc @ 16f511

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