Changeset 564dd8 in git for factory/fac_util.cc

Timestamp:

Jul 29, 2020, 10:00:14 AM (4 years ago)

Author:

Hans Schoenemann <hannes@…>

Branches:

(u'spielwiese', '2a584933abf2a2d3082034c7586d38bb6de1a30a')

Children:

f792337caec744ea4c10bf8d9214d7ae5e8acdcc

Parents:

8f5493aaf9a2f74965b580f83ebef852516cb86b

git-author:

Hans Schoenemann <hannes@mathematik.uni-kl.de>2020-07-29 10:00:14+02:00

git-committer:

Hans Schoenemann <hannes@mathematik.uni-kl.de>2020-07-29 10:42:27+02:00

Message:

factorize in Z[x,..] w/o NTL

File:

• factory/fac_util.cc (modified) (2 diffs)

factory/fac_util.cc

@@ -11 +11 @@
 #include "cf_iter.h"
 #include "fac_util.h"
+#include "cfUnivarGcd.h"
 
 STATIC_INST_VAR CanonicalForm PK, PKHALF;
@@ -111 +112 @@
 }
 
+CanonicalForm
+remainder( const CanonicalForm & f, const CanonicalForm & g, const modpk & pk )
+{
+    ASSERT( (f.inCoeffDomain() || f.isUnivariate()) && (g.inCoeffDomain() || g.isUnivariate()) && (f.inCoeffDomain() || g.inCoeffDomain() || f.mvar() == g.mvar()), "can not build remainder" );
+    if ( f.inCoeffDomain() )
+        if ( g.inCoeffDomain() )
+            return pk( f % g );
+        else
+            return pk( f );
+    else {
+        Variable x = f.mvar();
+        CanonicalForm result = f;
+        int degg = g.degree();
+        CanonicalForm invlcg = pk.inverse( g.lc() );
+        CanonicalForm gg = pk( g*invlcg );
+        if((gg.lc().isOne()))
+        {
+          while ( result.degree() >= degg )
+          {
+            result -= pk(lc( result ) * gg) * power( x, result.degree() - degg );
+            result=pk(result);
+          }
+        }
+        else
+        // no inverse found
+        {
+          CanonicalForm ic=icontent(g);
+          if (!ic.isOne())
+          {
+            gg=g/ic;
+            return remainder(f,gg,pk);
+          }
+          while ( result.degree() >= degg )
+          {
+            if (gg.lc().isZero()) return result;
+            CanonicalForm lcgf = result.lc() / gg.lc();
+            if (lcgf.inZ())
+              gg = pk( g*lcgf );
+            else
+            {
+              //printf("!\n\n");
+              return result;
+            }
+            result -=  gg * power( x, result.degree() - degg );
+            result=pk(result);
+          }
+        }
+        return result;
+    }
+}
+
+CanonicalForm
+prod ( const CFArray & a, int f, int l )
+{
+    if ( f < a.min() ) f = a.min();
+    if ( l > a.max() ) l = a.max();
+    CanonicalForm p = 1;
+    for ( int i = f; i <= l; i++ )
+        p *= a[i];
+    return p;
+}
+
+CanonicalForm
+prod ( const CFArray & a )
+{
+    return prod( a, a.min(), a.max() );
+}   
+
+void
+extgcd ( const CanonicalForm & a, const CanonicalForm & b, CanonicalForm & S, CanonicalForm & T, const modpk & pk )
+{
+    int p = pk.getp(), k = pk.getk(), j;
+    CanonicalForm amodp, bmodp, smodp, tmodp, s, t, sigma, tau, e;
+    CanonicalForm modulus = p, sigmat, taut, q;
+
+    setCharacteristic( p );
+    {
+        amodp = mapinto( a ); bmodp = mapinto( b );
+        (void)extgcd( amodp, bmodp, smodp, tmodp );
+    }
+    setCharacteristic( 0 );
+    s = mapinto( smodp ); t = mapinto( tmodp );
+
+    for ( j = 1; j < k; j++ ) {
+        e = ( 1 - s * a - t * b ) / modulus;
+        setCharacteristic( p );
+        {
+            e = mapinto( e );
+            sigmat = smodp * e;
+            taut = tmodp * e;
+            divrem( sigmat, bmodp, q, sigma );
+            tau = taut + q * amodp;
+        }
+        setCharacteristic( 0 );
+        s += mapinto( sigma ) * modulus;
+        t += mapinto( tau ) * modulus;
+        modulus *= p;
+    }
+    S = s; T = t;
+}