Changeset 583cb9 in git

Timestamp:

Feb 16, 2012, 4:08:44 PM (11 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'a800fe4b3e9d37a38c5a10cc0ae9dfa0c15a4ee6')

Children:

a090c889f1e12a81de12b9d046e6b570d92ff592

Parents:

eb481bfd5b0d2091758933b4dc457ec82ff37ce7

git-author:

Martin Lee <martinlee84@web.de>2012-02-16 16:08:44+01:00

git-committer:

Martin Lee <martinlee84@web.de>2012-04-04 14:42:25+02:00

Message:

chg: added diophantine equation solver using p-adic lifting

File:

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

factory/facHensel.cc

@@ -359 +359 @@
 }
 
-CFList diophantine (const CanonicalForm& F, const CFList& factors)
+CFList
+diophantine (const CanonicalForm& F, const CFList& factors);
+
+CFList
+diophantineHensel (const CanonicalForm & F, const CFList& factors,
+                   const modpk& b)
+{
+  int p= b.getp();
+  setCharacteristic (p);
+  CFList recResult= diophantine (mapinto (F), mapinto (factors));
+  setCharacteristic (0);
+  recResult= mapinto (recResult);
+  CanonicalForm e= 1;
+  CFList L;
+  CFArray bufFactors= CFArray (factors.length());
+  int k= 0;
+  for (CFListIterator i= factors; i.hasItem(); i++, k++)
+  {
+    if (k == 0)
+      bufFactors[k]= i.getItem() (0);
+    else
+      bufFactors [k]= i.getItem();
+  }
+  CanonicalForm tmp, quot;
+  for (k= 0; k < factors.length(); k++) //TODO compute b's faster
+  {
+    tmp= 1;
+    for (int l= 0; l < factors.length(); l++)
+    {
+      if (l == k)
+        continue;
+      else
+      {
+        tmp= mulNTL (tmp, bufFactors[l]);
+      }
+    }
+    L.append (tmp);
+  }
+
+  setCharacteristic (p);
+  for (k= 0; k < factors.length(); k++)
+    bufFactors [k]= bufFactors[k].mapinto();
+  setCharacteristic(0);
+
+  CFListIterator j= L;
+  for (CFListIterator i= recResult; i.hasItem(); i++, j++)
+    e= b (e - mulNTL (i.getItem(),j.getItem(), b));
+
+  if (e.isZero())
+    return recResult;
+  CanonicalForm coeffE;
+  CFList s;
+  CFList result= recResult;
+  CanonicalForm g;
+  CanonicalForm modulus= p;
+  int d= b.getk();
+  for (int i= 1; i < d; i++)
+  {
+    coeffE= div (e, modulus);
+    setCharacteristic (p);
+    coeffE= coeffE.mapinto();
+    setCharacteristic (0);
+    if (!coeffE.isZero())
+    {
+      CFListIterator k= result;
+      CFListIterator l= L;
+      int ii= 0;
+      j= recResult;
+      for (; j.hasItem(); j++, k++, l++, ii++)
+      {
+        setCharacteristic (p);
+        g= coeffE*j.getItem();
+        g= mod (g, bufFactors[ii]);
+        setCharacteristic (0);
+        k.getItem() += g.mapinto()*modulus;
+        e -= mulNTL (g.mapinto()*modulus, l.getItem(), b);
+        e= b(e);
+        DEBOUTLN (cerr, "mod (e, power (y, i + 1))= " <<
+                  mod (e, power (y, i + 1)));
+      }
+    }
+    modulus *= p;
+    if (e.isZero())
+      break;
+  }
+
+  return result;
+}
+
+CFList
+diophantine (const CanonicalForm& F, const CFList& factors, const modpk& b)
 {
   if (getCharacteristic() == 0)
   {
+    if (b.getp() != 0)
+      return diophantineHensel (F, factors, b);
     Variable v;
     bool hasAlgVar= hasFirstAlgVar (F, v);
@@ -399 +491 @@
   }
   return result;
+}
+
+CFList
+diophantine (const CanonicalForm& F, const CFList& factors)
+{
+  modpk b= modpk();
+  return diophantine (F, factors, b);
 }