1 | /* emacs edit mode for this file is -*- C++ -*- */ |
---|
2 | /* $Id: sm_sparsemod.cc,v 1.2 1997-07-22 09:16:10 schmidt Exp $ */ |
---|
3 | |
---|
4 | //{{{ docu |
---|
5 | // |
---|
6 | // sm_sparsemod.cc - zippel's sparse modular gcd. |
---|
7 | // |
---|
8 | // Contributed by Marion Bruder <bruder@math.uni-sb.de>. |
---|
9 | // |
---|
10 | // Used by: cf_gcf.cc |
---|
11 | // |
---|
12 | //}}} |
---|
13 | |
---|
14 | #include <config.h> |
---|
15 | |
---|
16 | #include "assert.h" |
---|
17 | #include "debug.h" |
---|
18 | |
---|
19 | #include "canonicalform.h" |
---|
20 | #include "cf_map.h" |
---|
21 | #include "cf_reval.h" |
---|
22 | #include "cf_irred.h" |
---|
23 | #include "cf_iter.h" |
---|
24 | #include "cf_primes.h" |
---|
25 | #include "cf_random.h" |
---|
26 | #include "fac_util.h" |
---|
27 | #include "sm_util.h" |
---|
28 | #include "sm_sparsemod.h" |
---|
29 | #ifdef macintosh |
---|
30 | #include <::templates:ftmpl_array.h> |
---|
31 | #include <::templates:ftmpl_functions.h> |
---|
32 | #else |
---|
33 | #include "templates/ftmpl_array.h" |
---|
34 | #include "templates/ftmpl_functions.h" |
---|
35 | #endif |
---|
36 | |
---|
37 | static CanonicalForm |
---|
38 | smodgcd( const CanonicalForm & u, const CanonicalForm & v, const CanonicalForm & lcggt, const REvaluation & alpha, CFRandom & gen, int CHAR, const Variable & extension ) |
---|
39 | { |
---|
40 | DEBOUTLN( cerr, " ALPHA = " << alpha ); |
---|
41 | |
---|
42 | DEBOUTLN( cerr, " u = " << u ); |
---|
43 | DEBOUTLN( cerr, " v = " << v ); |
---|
44 | |
---|
45 | // diverse Fallunterscheidungen // |
---|
46 | |
---|
47 | if ( u.isZero() ) |
---|
48 | return v; |
---|
49 | else if ( v.isZero() ) |
---|
50 | return u; |
---|
51 | else if ( u.inBaseDomain() ) |
---|
52 | if ( v.inBaseDomain() ) |
---|
53 | return gcd( u, v ); |
---|
54 | else |
---|
55 | return gcd( u, icontent( u ) ); |
---|
56 | else if ( v.inBaseDomain() ) |
---|
57 | return gcd( icontent( u ), v); |
---|
58 | else if ( u.isUnivariate() ) |
---|
59 | if ( v.isUnivariate() ) |
---|
60 | return gcd( u, v ); |
---|
61 | else |
---|
62 | return gcd( v, u ); |
---|
63 | |
---|
64 | |
---|
65 | |
---|
66 | |
---|
67 | // u und v Polynome in levU - Variablen x1, ..., xlevU |
---|
68 | // mit den gleichen Variablen, welches in sparsemod gesichert wurde |
---|
69 | |
---|
70 | int levU = level( u ); |
---|
71 | |
---|
72 | |
---|
73 | CFArray G( 1, levU ); |
---|
74 | Variable x( 1 ); |
---|
75 | CanonicalForm alphau = alpha( u, 2, levU ); |
---|
76 | CanonicalForm alphav = alpha( v, 2, levU ); |
---|
77 | |
---|
78 | G[1] = gcd( alphau, alphav ); // univariater gcd berechnen in x1 |
---|
79 | |
---|
80 | DEBOUTLN( cerr, " G[1] ohne lc = " << G[1] ); |
---|
81 | // Leitkoeffizienten auf univariaten gcd aufsetzen // |
---|
82 | |
---|
83 | if( alpha(lcggt) != 0 && degree(G[1]) != 0 ) |
---|
84 | { |
---|
85 | //G[1] =( alpha( lcggt ))*( ( 1/lc( G[1] ) ) * G[1] ); |
---|
86 | G[1] =( alpha( lcggt ))*( ( 1/Leitkoeffizient( G[1] ) ) * G[1] ); |
---|
87 | |
---|
88 | } |
---|
89 | |
---|
90 | |
---|
91 | |
---|
92 | if ( degree( G[1]) < 0 ) |
---|
93 | { |
---|
94 | |
---|
95 | return 1 ; |
---|
96 | } |
---|
97 | |
---|
98 | |
---|
99 | if ( degree( G[1] ) == 0 ) |
---|
100 | { |
---|
101 | // zwei Auswertungen um sicherzugehen, dass gcd Eins ist! |
---|
102 | |
---|
103 | return 1; |
---|
104 | } |
---|
105 | |
---|
106 | |
---|
107 | CFIterator J = G[ 1 ]; |
---|
108 | CFArray g( 1, degree( G[ 1 ]) + 1 ); |
---|
109 | int * emma = new int[ degree( G[1] ) + 2 ]; |
---|
110 | int s, m, i = 1; |
---|
111 | |
---|
112 | // g[i] enthaelt die momentan berechneten Monome bzgl x^emma[i] // |
---|
113 | |
---|
114 | while ( J.hasTerms() ) |
---|
115 | { |
---|
116 | g[ i ] = J.coeff() ; |
---|
117 | emma[ i ] = J.exp(); |
---|
118 | J++; |
---|
119 | i++; |
---|
120 | } |
---|
121 | |
---|
122 | |
---|
123 | m = i-1; /// Anzahl der Terme bzgl x1 |
---|
124 | int * n = new int[ m+1 ]; |
---|
125 | CFArray U( 2, levU ), V( 2, levU ); |
---|
126 | |
---|
127 | int N, d ; |
---|
128 | int k, j, zip ; |
---|
129 | |
---|
130 | // fuer jede Variabel interpolieren, um g[s] zu erhalten // |
---|
131 | |
---|
132 | DEBOUTLN( cerr, " unigcd mit alpha mit lc = " << G[1] ); |
---|
133 | |
---|
134 | for( s = 2 ;s <= levU ; s++ ) |
---|
135 | { |
---|
136 | U[ s ] = alpha( u, s+1, levU ); // s Variablen stehen lassen, fuer |
---|
137 | V[ s ] = alpha( v, s+1, levU ); // den Rest alpha einsetzen |
---|
138 | |
---|
139 | d = tmin( degree( U[ s ], s ), degree( V[ s ], s )); |
---|
140 | |
---|
141 | DEBOUTLN( cerr, " U["<< s << "] = " << U[s] ); |
---|
142 | DEBOUTLN( cerr, " V["<< s << "] = " << V[s] ); |
---|
143 | DEBOUTLN( cerr, " d = " << d ); |
---|
144 | |
---|
145 | |
---|
146 | |
---|
147 | for ( i = 1; i <= m ; i++ ) |
---|
148 | { |
---|
149 | // Anzahl der Monome berechnen pro gi liefert das Skeletonpolynom // |
---|
150 | |
---|
151 | n[ i ] = countmonome( g[ i ] ); |
---|
152 | //cout << "n["<<i<<"] = "<< n[i] << endl; |
---|
153 | } |
---|
154 | |
---|
155 | |
---|
156 | |
---|
157 | for ( i = 1; i <= m ; i++ ) |
---|
158 | { |
---|
159 | if ( i ==1 ) |
---|
160 | N = n[i]; |
---|
161 | else |
---|
162 | { |
---|
163 | if ( n[i]> N ) |
---|
164 | N = n[i]; |
---|
165 | } |
---|
166 | } |
---|
167 | |
---|
168 | |
---|
169 | // int tau[d+1][m+1][N+1]; /// keine Integers !!! |
---|
170 | typedef CanonicalForm** CF_ptr_ptr; |
---|
171 | typedef CanonicalForm* CF_ptr; |
---|
172 | |
---|
173 | CanonicalForm ***tau = new CF_ptr_ptr[m+1]; |
---|
174 | for ( i = 1; i <= m; i++ ) { |
---|
175 | tau[i] = new CF_ptr[d+1]; |
---|
176 | for ( j = 1; j <= d; j++ ) |
---|
177 | tau[i][j] = new CanonicalForm[N+1]; |
---|
178 | } |
---|
179 | |
---|
180 | CFArray beta( 1, d ); |
---|
181 | |
---|
182 | for ( i = 1; i <= d ; i++ ) |
---|
183 | { |
---|
184 | beta[ i ] = gen.generate(); // verschiedene Elemente aus Zp |
---|
185 | // cout << " beta["<<i << "] = " << beta[i]; |
---|
186 | } |
---|
187 | |
---|
188 | |
---|
189 | |
---|
190 | |
---|
191 | |
---|
192 | Array<REvaluation> xi( 1, N ); |
---|
193 | REvaluation a( 2, s-1, gen ); |
---|
194 | |
---|
195 | for ( i = 1 ; i <= N ; i++ ) |
---|
196 | { |
---|
197 | a.nextpoint(); |
---|
198 | xi[ i ] = a;//REvaluation( 2, s-1, gen ); |
---|
199 | // cout << " xi["<<i<<"] = "<< xi[i]; |
---|
200 | } |
---|
201 | |
---|
202 | |
---|
203 | //CFArray T(1, d*N ); |
---|
204 | |
---|
205 | if ( d == 0 ) |
---|
206 | { |
---|
207 | ASSERT( 0, "alpha bad point! try some other gcd algorithm" ); |
---|
208 | return gcd(u, v); |
---|
209 | } |
---|
210 | |
---|
211 | CFMatrix T( d, N ) ; // diese Moeglichkeit laeuft!!! |
---|
212 | //help = Koeff( T( j, k ), emma[ i ] ); |
---|
213 | //tau[i][j][k] = help; //.intval(); |
---|
214 | |
---|
215 | |
---|
216 | |
---|
217 | for ( j = 1 ; j <= d ; j++ ) // jedesmal andere REvaluation?? |
---|
218 | for ( k = 1 ; k <= N ; k++ ) |
---|
219 | { |
---|
220 | CanonicalForm zwischenu, zwischenv, help, nfa ; |
---|
221 | |
---|
222 | zwischenu = U[ s ]( beta[ j ], s ); |
---|
223 | zwischenv = V[ s ]( beta[ j ], s ); |
---|
224 | |
---|
225 | T( j, k) = gcd ( xi[k]( zwischenu, 2, s-1 ), xi[k]( zwischenv, 2, s-1 )); |
---|
226 | |
---|
227 | |
---|
228 | nfa = lcggt( beta[j], s ); |
---|
229 | nfa = alpha( nfa, s+1, levU ); |
---|
230 | |
---|
231 | //T(j, k ) = (xi[k]( nfa, 2, s-1 ))*((1/lc(T( j, k ))) * T( j, k )); |
---|
232 | T(j, k ) = (xi[k]( nfa, 2, s-1 ))*((1/Leitkoeffizient(T( j, k ))) * T( j, k )); |
---|
233 | |
---|
234 | //cout <<"T("<<j<<", "<< k <<") = " << T(j, k) << endl; |
---|
235 | |
---|
236 | |
---|
237 | for ( i = 1 ; i <= m ; i++ ) |
---|
238 | { |
---|
239 | // diese Moeglichkeit laeuft!!! |
---|
240 | //help = Koeff( T( j, k ), emma[ i ] ); |
---|
241 | //tau[i][j][k] = help; //.intval(); |
---|
242 | if ( T( j, k).inBaseDomain() ) |
---|
243 | { |
---|
244 | if ( emma[i] == 0 ) |
---|
245 | tau[i][j][k] = T( j, k ); |
---|
246 | else |
---|
247 | tau[i][j][k] = 0 ; |
---|
248 | } |
---|
249 | else |
---|
250 | { |
---|
251 | tau[i][j][k] = T(j, k)[emma[i]]; |
---|
252 | } |
---|
253 | } |
---|
254 | } |
---|
255 | |
---|
256 | |
---|
257 | CFMatrix h( m, d ); |
---|
258 | |
---|
259 | |
---|
260 | for ( i = 1; i <= m ; i++ ) |
---|
261 | { |
---|
262 | for ( j = 1 ; j <= d ; j++ ) |
---|
263 | { |
---|
264 | zip = n[i] +1; |
---|
265 | CanonicalForm * zwischen = new CanonicalForm[ zip ];//n[i]+1 ]; |
---|
266 | |
---|
267 | for ( k = 1 ; k <= n[i] ; k++ ) |
---|
268 | { |
---|
269 | zwischen[ k ] = tau[i][j][k]; |
---|
270 | } |
---|
271 | |
---|
272 | //cout <<" werte fuer sinterpol : " << endl; |
---|
273 | //cout <<" g["<<i<<"] = " << g[i] << " xi = " << xi << endl; |
---|
274 | //cout << " zwischen = " << zwischen << " ni = " << n[i]<<endl; |
---|
275 | h[ i ][ j ] = sinterpol( g[i], xi, zwischen, n[i] ); |
---|
276 | DEBOUTLN( cerr, " Ergebnis von sinterpol h["<<i<<"]["<<j<< "] = " << h[i][j] ); |
---|
277 | delete [] zwischen; |
---|
278 | } |
---|
279 | } |
---|
280 | for ( i = 1 ; i <= m ; i++ ) |
---|
281 | { |
---|
282 | CFArray zwitscher( 1, d ); |
---|
283 | for ( j = 1 ; j <= d ; j++ ) |
---|
284 | { |
---|
285 | zwitscher[ j ] = h[ i ][ j ]; |
---|
286 | } |
---|
287 | |
---|
288 | DEBOUTLN( cerr, "Werte fuer dinterpol : " ); |
---|
289 | DEBOUTLN( cerr, " d = " << d << " g["<<i<<"] = "<< g[i] ); |
---|
290 | DEBOUTLN( cerr, " zwitscher = " << zwitscher ); |
---|
291 | DEBOUTLN( cerr, " alpha["<<s<< "] = "<< alpha[s] << " beta = "<<beta << " n["<<i<<"] = " << n[i] ); |
---|
292 | |
---|
293 | g[ i ] = dinterpol( d, g[i], zwitscher, alpha, s, beta, n[ i ], CHAR ); |
---|
294 | DEBOUTLN( cerr, " Ergebnis von dinterpol g["<<i<<"] = " << g[i] ); |
---|
295 | |
---|
296 | } |
---|
297 | |
---|
298 | |
---|
299 | for ( i = 1 ; i <= m ; i++ ) |
---|
300 | { |
---|
301 | G[ s ] += g[ i ] * ( power( x, emma[i] ) ); |
---|
302 | } |
---|
303 | DEBOUTLN( cerr, "G["<<s<<"] = " << G[s] ); |
---|
304 | for ( i = 1; i <= m; i++ ) { |
---|
305 | for ( j = 1; j <= d; j++ ) |
---|
306 | delete [] tau[i][j]; |
---|
307 | delete [] tau[i]; |
---|
308 | } |
---|
309 | delete [] tau; |
---|
310 | } |
---|
311 | delete [] emma; |
---|
312 | |
---|
313 | return G[ levU ]; |
---|
314 | } |
---|
315 | |
---|
316 | // In sparsemod testen, ob G[levU] | u und G[levU] | v /// |
---|
317 | static CanonicalForm |
---|
318 | internalSparsemod( const CanonicalForm & F, const CanonicalForm & G ) |
---|
319 | { |
---|
320 | // On(SW_USE_EZGCD ); |
---|
321 | On( SW_SYMMETRIC_FF ); |
---|
322 | //cout << " in sparse " << endl; |
---|
323 | if( F.inCoeffDomain() && G.inCoeffDomain() ) |
---|
324 | { |
---|
325 | return gcd( F, G ); |
---|
326 | } |
---|
327 | |
---|
328 | CanonicalForm f, g, ff, gg, ggt, res, fmodp, gmodp ; |
---|
329 | int i, count = 10; |
---|
330 | |
---|
331 | // COMPRESS /////////////////// |
---|
332 | |
---|
333 | |
---|
334 | CFArray A(1, 2); |
---|
335 | A[1] = F; |
---|
336 | A[2] = G; |
---|
337 | CFMap M, N; |
---|
338 | compress(A, M, N); |
---|
339 | f = M(A[1]); |
---|
340 | g = M(A[2]); |
---|
341 | |
---|
342 | |
---|
343 | // POLYNOME PRIMITIV BZGL DER ERSTEN VARIABLE ///// |
---|
344 | |
---|
345 | |
---|
346 | |
---|
347 | CanonicalForm primif, primig, lcf, lcg, lcggt, lcggtmodp, result ; |
---|
348 | ff = content( f, Variable(1) );//contentsparse( f, 1 ); |
---|
349 | gg = content( g, Variable(1) );//contentsparse( g, 1 ); |
---|
350 | |
---|
351 | |
---|
352 | |
---|
353 | primif = f/ff; |
---|
354 | primig = g/gg; |
---|
355 | ggt = gcd( ff, gg ); |
---|
356 | |
---|
357 | if( primif.inCoeffDomain() && primig.inCoeffDomain() ) |
---|
358 | { |
---|
359 | return N( gcd( primif, primig ) ) * N( ggt ); |
---|
360 | } |
---|
361 | |
---|
362 | |
---|
363 | |
---|
364 | |
---|
365 | // Variablen, die in beiden Polynomen auftreten ///// |
---|
366 | |
---|
367 | int levis, m, levelprimif, levelprimig; |
---|
368 | int ABFRAGE = 1 ; |
---|
369 | |
---|
370 | levelprimif = level( primif ); |
---|
371 | levelprimig = level( primig ); |
---|
372 | |
---|
373 | if ( levelprimif > levelprimig ) |
---|
374 | levis = levelprimif; |
---|
375 | else |
---|
376 | levis = levelprimig; |
---|
377 | |
---|
378 | if ( levis < 0 ) |
---|
379 | return N( gcd( primif, primig ) ); |
---|
380 | |
---|
381 | int varf[ levis ], varg[ levis ], schnitt[ levis ]; |
---|
382 | |
---|
383 | while ( ABFRAGE == 1 ) |
---|
384 | { |
---|
385 | levelprimif = level(primif); |
---|
386 | levelprimig = level(primig); |
---|
387 | |
---|
388 | if ( levelprimif > levelprimig ) |
---|
389 | levis = levelprimif; |
---|
390 | else |
---|
391 | levis = levelprimig; |
---|
392 | |
---|
393 | if ( levis < 0 ) |
---|
394 | return N( gcd(primif, primig )); |
---|
395 | |
---|
396 | |
---|
397 | for( i = 1; i <= levis ; i++ ) |
---|
398 | { |
---|
399 | if ( degree( primif, i ) != 0 ) |
---|
400 | varf[i] = 1; |
---|
401 | else |
---|
402 | varf[i] = 0; |
---|
403 | if ( degree( primig, i ) != 0 ) |
---|
404 | varg[i] = 1; |
---|
405 | else |
---|
406 | varg[i] = 0; |
---|
407 | if ( varg[i] == 1 && varf[i] == 1 ) |
---|
408 | schnitt[i] = 1; |
---|
409 | else |
---|
410 | schnitt[i] = 0; |
---|
411 | } |
---|
412 | |
---|
413 | levelprimif = level(primif); |
---|
414 | levelprimig = level(primig); |
---|
415 | |
---|
416 | for ( m = 1; m <= levis ; m++) |
---|
417 | { |
---|
418 | if ( schnitt[m] == 0 ) |
---|
419 | if ( varf[m] == 1) |
---|
420 | { |
---|
421 | primif = content( primif, m ); //contentsparse( primif, m ); |
---|
422 | } |
---|
423 | else |
---|
424 | { |
---|
425 | primig = content( primig, m ); //contentsparse( primig, m ); |
---|
426 | } |
---|
427 | } |
---|
428 | |
---|
429 | if ( level( primif ) == level( primig ) ) |
---|
430 | ABFRAGE = 0 ; |
---|
431 | |
---|
432 | } |
---|
433 | |
---|
434 | |
---|
435 | |
---|
436 | |
---|
437 | |
---|
438 | // Nochmal compress fuer den Fall, dass eine Variable rausfliegt // |
---|
439 | |
---|
440 | |
---|
441 | CFArray C(1, 2); |
---|
442 | C[1] = primif; |
---|
443 | C[2] = primig; |
---|
444 | CFMap MM, NN ; |
---|
445 | compress(C, MM, NN); |
---|
446 | primif = MM(C[1]); |
---|
447 | primig = MM(C[2]); |
---|
448 | |
---|
449 | if ( level( primif) != level( primig ) ) |
---|
450 | ASSERT( 0, "this should n e v e r happen !!!!" ); |
---|
451 | |
---|
452 | //cout << " primif = " << primif << endl; |
---|
453 | //cout << " primig = " << primig << endl; |
---|
454 | |
---|
455 | if( primif.inCoeffDomain() && primig.inCoeffDomain() ) |
---|
456 | { |
---|
457 | return N( NN( gcd( primif, primig ) ) ) * N( ggt ); |
---|
458 | } |
---|
459 | |
---|
460 | // erst hier Leitkoeffizienten updaten ///////// |
---|
461 | |
---|
462 | //if( primif.inCoeffDomain() || primif.isUnivariate |
---|
463 | |
---|
464 | lcf = LC(primif, 1 ); |
---|
465 | lcg = LC(primig, 1 ); |
---|
466 | lcggt = gcd ( lcf, lcg ); |
---|
467 | |
---|
468 | |
---|
469 | |
---|
470 | // BOUND BESTIMMEN fuer Charakteristik Null ///////// |
---|
471 | |
---|
472 | int CHAR = getCharacteristic(), deg ; |
---|
473 | if ( CHAR < 10 ) |
---|
474 | deg = 3; // Default Erweiterung bei kleiner Primzahl; |
---|
475 | else |
---|
476 | deg = 1; |
---|
477 | CanonicalForm B, L, Bound, lcF = Leitkoeffizient( primif); //lc( primif ) ; |
---|
478 | B = 2 * maxCoeff( primif ) * maxCoeff( g ) ; |
---|
479 | L = lcF ; |
---|
480 | Bound = abs( 2 * B * L + 1 ); |
---|
481 | int length = 1; |
---|
482 | |
---|
483 | CFArray p( 1, 10 ) ; |
---|
484 | |
---|
485 | if( CHAR == 0 ) |
---|
486 | { |
---|
487 | p[ 1 ] = cf_getBigPrime( count ); |
---|
488 | CanonicalForm q = p[ 1 ]; |
---|
489 | |
---|
490 | while ( q < Bound ) |
---|
491 | { |
---|
492 | count++; |
---|
493 | length++; |
---|
494 | p[ length ] = cf_getBigPrime( count ); |
---|
495 | q *= p[ length ]; //G[levU] = ( 1/lc(G[levU] ))* G[levU];// sinnig? |
---|
496 | //cout << " lcggt = " << lcggt << endl; |
---|
497 | //bool ja; |
---|
498 | //ja = divides( lcggt, lc( G[levU] ) ); |
---|
499 | //cout << " ja = " << ja << endl; |
---|
500 | //cout << " vor Verlassen " << endl; |
---|
501 | } |
---|
502 | } |
---|
503 | else |
---|
504 | { |
---|
505 | //int q = CHAR; |
---|
506 | //setCharacteristic( 0 ); |
---|
507 | //CanonicalForm Bound2 = mapinto( Bound ) ; |
---|
508 | //cout << " Bound2 " << Bound2 << endl; |
---|
509 | //cout << " CHAR = " << q << endl; |
---|
510 | |
---|
511 | // erstmal ohne Erweiterung !!! |
---|
512 | //deg = 3; // Default Erweiterung |
---|
513 | //q *= ( q * q ) ;cout << "q = " << q << endl; |
---|
514 | |
---|
515 | //Bestimme Grad der Koerpererweiterung voellig unnuetz!!! |
---|
516 | //while ( q < abs( Bound2 ) ) |
---|
517 | // { |
---|
518 | // q *= CHAR;cout << " q = " << q << endl; |
---|
519 | //deg++;cout << " degchar = " << deg << endl; |
---|
520 | //cout << " in Graderhoehung? " << endl; |
---|
521 | |
---|
522 | //} |
---|
523 | //setCharacteristic( CHAR ); |
---|
524 | //cerr << " JUHU " << endl; |
---|
525 | } |
---|
526 | |
---|
527 | |
---|
528 | |
---|
529 | |
---|
530 | // ENDE BOUNDBESTIMMUNG ///////////////// |
---|
531 | |
---|
532 | |
---|
533 | FFRandom gen ; |
---|
534 | levelprimif = level( primif ); |
---|
535 | REvaluation am( 2, levelprimif, FFRandom ( )); |
---|
536 | int k, help ; |
---|
537 | CFArray resultat( 1, length );//cout << " nach Resultat " << endl; |
---|
538 | CanonicalForm zwischen; |
---|
539 | Variable alpha1( levelprimif + 1 ); |
---|
540 | ABFRAGE = 0; |
---|
541 | |
---|
542 | |
---|
543 | for ( i = 1 ; i <= 10; i++ ) // 10 Versuche mit sparsemod |
---|
544 | { |
---|
545 | if ( CHAR == 0 ) |
---|
546 | { |
---|
547 | for( k = 1; k <= length ; k++) |
---|
548 | { |
---|
549 | help = p[ k ].intval(); |
---|
550 | setCharacteristic( help ); |
---|
551 | FFRandom mache; |
---|
552 | am = REvaluation( 2, levelprimif, mache ); |
---|
553 | am.nextpoint(); |
---|
554 | fmodp = mapinto( primif ); |
---|
555 | gmodp = mapinto( primig ); |
---|
556 | lcggtmodp = mapinto ( lcggt ); |
---|
557 | |
---|
558 | zwischen = smodgcd( fmodp, gmodp, lcggtmodp, am, mache, CHAR, Variable( 1 )); |
---|
559 | // Variable ( 1 ) Interface fuer endliche Koerper |
---|
560 | |
---|
561 | // Char auf 0 wegen Chinese Remainder //////// |
---|
562 | |
---|
563 | setCharacteristic( 0 ); |
---|
564 | |
---|
565 | |
---|
566 | resultat[ k ] = mapinto( zwischen ); |
---|
567 | |
---|
568 | } |
---|
569 | |
---|
570 | |
---|
571 | //////////////////////////////////////////////////////////// |
---|
572 | // result[k] mod p[k] via Chinese Remainder zu Resultat ////// |
---|
573 | // ueber Z hochziehen ////// |
---|
574 | //////////////////////////////////////////////////////////// |
---|
575 | |
---|
576 | if( length != 1 ) |
---|
577 | ChinesePoly( length, resultat, p, result ); |
---|
578 | else |
---|
579 | result = resultat[1]; |
---|
580 | |
---|
581 | CanonicalForm contentresult = content( result, 1 ); |
---|
582 | |
---|
583 | if ( contentresult != 0 ) |
---|
584 | res = result/contentresult; |
---|
585 | else |
---|
586 | res = result; |
---|
587 | |
---|
588 | if ( divides( res, primif ) && divides( res, primig ) ) |
---|
589 | return N(NN(res))*N(ggt) ; /// compress rueckgaengig machen! |
---|
590 | else |
---|
591 | { |
---|
592 | |
---|
593 | // Start all over again /// |
---|
594 | |
---|
595 | count++; |
---|
596 | for ( k = 1; k <= length ; k++) |
---|
597 | { |
---|
598 | p[k] = cf_getBigPrime( count ); |
---|
599 | count++; |
---|
600 | } |
---|
601 | |
---|
602 | } |
---|
603 | } |
---|
604 | else |
---|
605 | { |
---|
606 | // Fall Char != 0 /// |
---|
607 | // in algebraische Erweiterung vom Grad deg gehen // |
---|
608 | //cout << " IN CHAR != 0 " << endl; |
---|
609 | //cout << " degree = " << deg << endl; |
---|
610 | CanonicalForm minimalpoly; |
---|
611 | //cout << " vor mini " << endl; |
---|
612 | minimalpoly = find_irreducible( deg, gen, alpha1 ); |
---|
613 | //cout << " nach mini " << endl; |
---|
614 | Variable alpha2 = rootOf( minimalpoly, 'a' ) ; |
---|
615 | AlgExtRandomF hallo( alpha2 ); |
---|
616 | //cout << " vor am " << endl; |
---|
617 | REvaluation am ( 2, levelprimif, hallo ); |
---|
618 | //cout << " nach ma " << endl; |
---|
619 | am.nextpoint(); |
---|
620 | //cout << "vor smodgcd " << endl; |
---|
621 | result = smodgcd( primif, primig, lcggt, am, hallo, CHAR, alpha2 ); |
---|
622 | if ( result == 1 && ABFRAGE == 0) |
---|
623 | { |
---|
624 | // zwei Auswertungen fuer gcd Eins |
---|
625 | am.nextpoint(); |
---|
626 | ABFRAGE = 1; |
---|
627 | } |
---|
628 | //CanonicalForm contentresult = contentsparse( result, 1 ); |
---|
629 | //zuerst mal auf Nummer sicher gehen ... |
---|
630 | else |
---|
631 | { |
---|
632 | CanonicalForm contentresult = content( result, 1 ); |
---|
633 | //cout << "RESULT = " << result << endl; |
---|
634 | if ( contentresult != 0 ) |
---|
635 | res = result/contentresult; |
---|
636 | else |
---|
637 | { |
---|
638 | res = result; |
---|
639 | } |
---|
640 | |
---|
641 | |
---|
642 | if ( ( divides( res, primif )) && ( divides ( res, primig ) )) |
---|
643 | { |
---|
644 | // make monic //// |
---|
645 | res = (1/lc(res)) * res; |
---|
646 | // eventuell auch hier Leitkoeffizient anstatt lc ? |
---|
647 | |
---|
648 | return N( NN( res ) ) * N( ggt ) ; |
---|
649 | } |
---|
650 | else |
---|
651 | { |
---|
652 | // Grad der Erweiterung sukzessive um eins erhoehen |
---|
653 | deg++; |
---|
654 | //cout << " deg = " << deg << endl; |
---|
655 | am.nextpoint(); |
---|
656 | // nextpoint() unnoetig? |
---|
657 | } |
---|
658 | } |
---|
659 | } |
---|
660 | } |
---|
661 | |
---|
662 | |
---|
663 | //Fuer den Fall der unwahrscheinlichen Faelle, dass die Versuche |
---|
664 | //nicht ausreichen : |
---|
665 | |
---|
666 | ASSERT( 0, "sparsemod failed! try some other gcd algorithm" ); |
---|
667 | if( CHAR == 0 ) |
---|
668 | setCharacteristic( 0 ); |
---|
669 | |
---|
670 | return 0; |
---|
671 | |
---|
672 | } |
---|
673 | |
---|
674 | CanonicalForm |
---|
675 | sparsemod( const CanonicalForm & F, const CanonicalForm & G ) |
---|
676 | { |
---|
677 | Off( SW_USE_SPARSEMOD ); |
---|
678 | CanonicalForm result = internalSparsemod( F, G ); |
---|
679 | On( SW_USE_SPARSEMOD ); |
---|
680 | return result; |
---|
681 | } |
---|