My Project  UNKNOWN_GIT_VERSION
Functions
cfNTLzzpEXGCD.h File Reference
#include "NTLconvert.h"

Go to the source code of this file.

Functions

void tryNTLGCD (zz_pEX &x, const zz_pEX &a, const zz_pEX &b, bool &fail)
 compute the GCD x of a and b, fail is set to true if a zero divisor is encountered More...
 
void tryNTLXGCD (zz_pEX &d, zz_pEX &s, zz_pEX &t, const zz_pEX &a, const zz_pEX &b, bool &fail)
 compute the extended GCD d=s*a+t*b, fail is set to true if a zero divisor is encountered More...
 

Detailed Description

This file defines functions for univariate GCD and extended GCD over Z/p[t]/(f)[x] for reducible f

Note
the following code is slightly modified code out of lzz_pEX.h from Victor Shoup's NTL. Below is NTL's copyright notice.

ABSTRACT: Langemyr, McCallum "The Computation of Polynomial Greatest Common Divisors over an algebraic number fields"

Author
Martin Lee
              COPYRIGHT NOTICE
                for NTL 5.5
      (modified for Singular 2-0-6 - 3-1)

NTL – A Library for Doing Number Theory Copyright (C) 1996-2009 Victor Shoup

The most recent version of NTL is available at http://www.shoup.net

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

This entire copyright notice should be placed in an appropriately conspicuous place accompanying all distributions of software that make use of NTL.

The above terms apply to all of the software modules distributed with NTL, i.e., all source files in either the ntl-xxx.tar.gz or WinNTL-xxx.zip distributions. In general, the individual files do not contain copyright notices.

Note that the quad_float package is derived from the doubledouble package, originally developed by Keith Briggs, and also licensed unger the GNU GPL. The files quad_float.c and quad_float.h contain more detailed copyright notices.

Note that the traditional long integer package used by NTL, lip.c, is derived from—and represents an extensive modification of— a package originally developed and copyrighted by Arjen Lenstra, who has agreed to renounce any copyright claims on the particular version of the long integer package appearing in NTL, so that the this package now is covered by the GNU GPL as well.

Note that the alternative long integer package used by NTL is GMP, which is written by Torbjorn Granlund tege@.nosp@m.swox.nosp@m..com. GMP is licensed under the terms of the GNU Lesser General Public License.

Note that NTL makes use of the RSA Data Security, Inc. MD5 Message Digest Algorithm.

Note that prior to version 4.0, NTL was distributed under the following terms: NTL is freely available for research and educational purposes. I don't want to attach any legalistic licensing restrictions on users of NTL. However, NTL should not be linked in a commercial program (although using data in a commercial product produced by a program that used NTL is fine).

The hope is that the GNU GPL is actually less restrictive than these older terms; however, in any circumstances such that GNU GPL is more restrictive, then the following rule is in force: versions prior to 4.0 may continue to be used under the old terms, but users of versions 4.0 or later should adhere to the terms of the GNU GPL.

Definition in file cfNTLzzpEXGCD.h.

Function Documentation

◆ tryNTLGCD()

void tryNTLGCD ( zz_pEX &  x,
const zz_pEX &  a,
const zz_pEX &  b,
bool &  fail 
)

compute the GCD x of a and b, fail is set to true if a zero divisor is encountered

Parameters
[in,out]xGCD of a and b
[in]as.a.
[in]bs.a.
[in,out]fails.a.

Definition at line 242 of file cfNTLzzpEXGCD.cc.

243 {
244  zz_pE t;
245 
246  if (IsZero(b))
247  x = a;
248  else if (IsZero(a))
249  x = b;
250  else {
251  long n = max(deg(a),deg(b)) + 1;
252  zz_pEX u(INIT_SIZE, n), v(INIT_SIZE, n);
253 
254  vec_zz_pX tmp;
255  SetSize(tmp, n, 2*zz_pE::degree());
256 
257  u = a;
258  v = b;
259  do {
260  tryPlainRem(u, u, v, tmp, fail);
261  if (fail)
262  return;
263  swap(u, v);
264  } while (!IsZero(v));
265 
266  x = u;
267  }
268 
269  if (IsZero(x)) return;
270  if (IsOne(LeadCoeff(x))) return;
271 
272  /* make gcd monic */
273 
274 
275  fail= InvModStatus (t, LeadCoeff(x));
276  if (fail)
277  return;
278  mul(x, x, t);
279 }

◆ tryNTLXGCD()

void tryNTLXGCD ( zz_pEX &  d,
zz_pEX &  s,
zz_pEX &  t,
const zz_pEX &  a,
const zz_pEX &  b,
bool &  fail 
)

compute the extended GCD d=s*a+t*b, fail is set to true if a zero divisor is encountered

Parameters
[in,out]dGCD of a and b
[in,out]ss. a.
[in,out]ts. a.
[in]as. a.
[in]bs. a.
[in,out]fails. a.

Definition at line 281 of file cfNTLzzpEXGCD.cc.

283 {
284  zz_pE z;
285 
286 
287  if (IsZero(b)) {
288  set(s);
289  clear(t);
290  d = a;
291  }
292  else if (IsZero(a)) {
293  clear(s);
294  set(t);
295  d = b;
296  }
297  else {
298  long e = max(deg(a), deg(b)) + 1;
299 
300  zz_pEX temp(INIT_SIZE, e), u(INIT_SIZE, e), v(INIT_SIZE, e),
301  u0(INIT_SIZE, e), v0(INIT_SIZE, e),
302  u1(INIT_SIZE, e), v1(INIT_SIZE, e),
303  u2(INIT_SIZE, e), v2(INIT_SIZE, e), q(INIT_SIZE, e);
304 
305 
306  set(u1); clear(v1);
307  clear(u2); set(v2);
308  u = a; v = b;
309 
310  do {
311  fail= InvModStatus (z, LeadCoeff(v));
312  if (fail)
313  return;
314  DivRem(q, u, u, v);
315  swap(u, v);
316  u0 = u2;
317  v0 = v2;
318  mul(temp, q, u2);
319  sub(u2, u1, temp);
320  mul(temp, q, v2);
321  sub(v2, v1, temp);
322  u1 = u0;
323  v1 = v0;
324  } while (!IsZero(v));
325 
326  d = u;
327  s = u1;
328  t = v1;
329  }
330 
331  if (IsZero(d)) return;
332  if (IsOne(LeadCoeff(d))) return;
333 
334  /* make gcd monic */
335 
336  fail= InvModStatus (z, LeadCoeff(d));
337  if (fail)
338  return;
339  mul(d, d, z);
340  mul(s, s, z);
341  mul(t, t, z);
342 }
InvModStatus
long InvModStatus(zz_pE &x, const zz_pE &a)
Definition: cfNTLzzpEXGCD.cc:95
x
Variable x
Definition: cfModGcd.cc:4023
IsOne
static BOOLEAN IsOne(number a, const coeffs r)
Definition: flintcf_Q.cc:330
b
CanonicalForm b
Definition: cfModGcd.cc:4044
max
static int max(int a, int b)
Definition: fast_mult.cc:264
tryPlainRem
void tryPlainRem(zz_pEX &r, const zz_pEX &a, const zz_pEX &b, vec_zz_pX &x, bool &fail)
Definition: cfNTLzzpEXGCD.cc:109
IsZero
static BOOLEAN IsZero(number a, const coeffs r)
Definition: flintcf_Q.cc:326
SetSize
static void SetSize(vec_zz_pX &x, long n, long m)
Definition: cfNTLzzpEXGCD.cc:101
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
swap
#define swap(_i, _j)
s
const CanonicalForm int s
Definition: facAbsFact.cc:55
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309