My Project
Loading...
Searching...
No Matches
Functions
cfNTLzzpEXGCD.cc File Reference
#include "config.h"
#include "cfNTLzzpEXGCD.h"
#include "NTLconvert.h"

Go to the source code of this file.

Functions

long InvModStatus (zz_pE &x, const zz_pE &a)
 
static void SetSize (vec_zz_pX &x, long n, long m)
 
void tryPlainRem (zz_pEX &r, const zz_pEX &a, const zz_pEX &b, vec_zz_pX &x, bool &fail)
 
void tryPlainDivRem (zz_pEX &q, zz_pEX &r, const zz_pEX &a, const zz_pEX &b, bool &fail)
 
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

Author
Martin Lee

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.c from Victor Shoup's NTL. Below is NTL's copyright notice.
Copyright:
(c) by The SINGULAR Team, see LICENSE file
            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.cc.

Function Documentation

◆ InvModStatus()

long InvModStatus ( zz_pE &  x,
const zz_pE &  a 
)

Definition at line 95 of file cfNTLzzpEXGCD.cc.

96{
97 return InvModStatus(x._zz_pE__rep, a._zz_pE__rep, zz_pE::modulus());
98}
x
Variable x
Definition: cfModGcd.cc:4082
InvModStatus
long InvModStatus(zz_pE &x, const zz_pE &a)
Definition: cfNTLzzpEXGCD.cc:95

◆ SetSize()

static void SetSize ( vec_zz_pX &  x,
long  n,
long  m 
)
static

Definition at line 101 of file cfNTLzzpEXGCD.cc.

102{
103 x.SetLength(n);
104 long i;
105 for (i = 0; i < n; i++)
106 x[i].rep.SetMaxLength(m);
107}
m
int m
Definition: cfEzgcd.cc:128
i
int i
Definition: cfEzgcd.cc:132

◆ 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}
swap
#define swap(_i, _j)
b
CanonicalForm b
Definition: cfModGcd.cc:4103
SetSize
static void SetSize(vec_zz_pX &x, long n, long m)
Definition: cfNTLzzpEXGCD.cc:101
tryPlainRem
void tryPlainRem(zz_pEX &r, const zz_pEX &a, const zz_pEX &b, vec_zz_pX &x, bool &fail)
Definition: cfNTLzzpEXGCD.cc:109
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
max
static int max(int a, int b)
Definition: fast_mult.cc:264
IsOne
static BOOLEAN IsOne(number a, const coeffs)
Definition: flintcf_Q.cc:332
IsZero
static BOOLEAN IsZero(number a, const coeffs)
Definition: flintcf_Q.cc:328

◆ 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}
s
const CanonicalForm int s
Definition: facAbsFact.cc:51

◆ tryPlainDivRem()

void tryPlainDivRem ( zz_pEX &  q,
zz_pEX &  r,
const zz_pEX &  a,
const zz_pEX &  b,
bool &  fail 
)

Definition at line 167 of file cfNTLzzpEXGCD.cc.

169{
170 long da, db, dq, i, j, LCIsOne;
171 const zz_pE *bp;
172 zz_pE *qp;
173 zz_pX *xp;
174
175
176 zz_pE LCInv, t;
177 zz_pX s;
178
179 da = deg(a);
180 db = deg(b);
181
182 if (db < 0) Error("zz_pEX: division by zero");
183
184 if (da < db) {
185 r = a;
186 clear(q);
187 return;
188 }
189
190 zz_pEX lb;
191
192 if (&q == &b) {
193 lb = b;
194 bp = lb.rep.elts();
195 }
196 else
197 bp = b.rep.elts();
198
199 if (IsOne(bp[db]))
200 LCIsOne = 1;
201 else {
202 LCIsOne = 0;
203 fail= InvModStatus (LCInv, bp[db]);
204 //inv(LCInv, bp[db]);
205 if (fail)
206 return;
207 }
208
209 vec_zz_pX x;
210
211 SetSize(x, da+1, 2*zz_pE::degree());
212
213 for (i = 0; i <= da; i++)
214 x[i] = rep(a.rep[i]);
215
216 xp = x.elts();
217
218 dq = da - db;
219 q.rep.SetLength(dq+1);
220 qp = q.rep.elts();
221
222 for (i = dq; i >= 0; i--) {
223 conv(t, xp[i+db]);
224 if (!LCIsOne)
225 mul(t, t, LCInv);
226 qp[i] = t;
227 NTL::negate(t, t);
228
229 for (j = db-1; j >= 0; j--) {
230 mul(s, rep(t), rep(bp[j]));
231 add(xp[i+j], xp[i+j], s);
232 }
233 }
234
235 r.rep.SetLength(db);
236 for (i = 0; i < db; i++)
237 conv(r.rep[i], xp[i]);
238 r.normalize();
239}
conv
CFList conv(const CFFList &L)
convert a CFFList to a CFList by dropping the multiplicity
Definition: facBivar.cc:126
j
int j
Definition: facHensel.cc:110
add
STATIC_VAR unsigned add[]
Definition: misc_ip.cc:107

◆ tryPlainRem()

void tryPlainRem ( zz_pEX &  r,
const zz_pEX &  a,
const zz_pEX &  b,
vec_zz_pX &  x,
bool &  fail 
)

Definition at line 109 of file cfNTLzzpEXGCD.cc.

111{
112 long da, db, dq, i, j, LCIsOne;
113 const zz_pE *bp;
114 zz_pX *xp;
115
116
117 zz_pE LCInv, t;
118 zz_pX s;
119
120 da = deg(a);
121 db = deg(b);
122
123 if (db < 0) Error("zz_pEX: division by zero");
124
125 if (da < db) {
126 r = a;
127 return;
128 }
129
130 bp = b.rep.elts();
131
132 if (IsOne(bp[db]))
133 LCIsOne = 1;
134 else {
135 LCIsOne = 0;
136 fail= InvModStatus (LCInv, bp[db]);
137 //inv(LCInv, bp[db]);
138 if (fail)
139 return;
140 }
141
142 for (i = 0; i <= da; i++)
143 x[i] = rep(a.rep[i]);
144
145 xp = x.elts();
146
147 dq = da - db;
148
149 for (i = dq; i >= 0; i--) {
150 conv(t, xp[i+db]);
151 if (!LCIsOne)
152 mul(t, t, LCInv);
153 NTL::negate(t, t);
154
155 for (j = db-1; j >= 0; j--) {
156 mul(s, rep(t), rep(bp[j]));
157 add(xp[i+j], xp[i+j], s);
158 }
159 }
160
161 r.rep.SetLength(db);
162 for (i = 0; i < db; i++)
163 conv(r.rep[i], xp[i]);
164 r.normalize();
165}
Generated on Mon Feb 27 2023 10:53:50 for My Project by   doxygen 1.9.5 for Singular