Context Navigation

source: sage/libs/ntl/ntl.pyx @ 3154:84be7673cef8

Visit:

Revision 3154:84be7673cef8, 93.6 KB checked in by William Stein <wstein@…>, 6 years ago (diff)
merge in Robert's changes needed for new SageX code.

Line
1	"""
2	NTL wrapper
3
4	AUTHORS:
5	- William Stein
6	- Martin Albrecht <malb@informatik.uni-bremen.de>
7	- David Harvey (2007-02): speed up getting data in/out of NTL
8	"""
9
10	#*****************************************************************************
11	# Copyright (C) 2005 William Stein <wstein@gmail.com>
12	#
13	# Distributed under the terms of the GNU General Public License (GPL)
14	#
15	# This code is distributed in the hope that it will be useful,
16	# but WITHOUT ANY WARRANTY; without even the implied warranty of
17	# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18	# General Public License for more details.
19	#
20	# The full text of the GPL is available at:
21	#
22	# http://www.gnu.org/licenses/
23	#*****************************************************************************
24
25	include "../../ext/interrupt.pxi"
26	include "../../ext/stdsage.pxi"
27	include 'misc.pxi'
28	include 'decl.pxi'
29
30	from sage.rings.integer import Integer
31	from sage.rings.integer cimport Integer
32	#cimport sage.rings.integer
33
34
35	##############################################################################
36	# ZZ: Arbitrary precision integers
37	##############################################################################
38
39	cdef class ntl_ZZ:
40	r"""
41	The \class{ZZ} class is used to represent signed, arbitrary length integers.
42
43	Routines are provided for all of the basic arithmetic operations, as
44	well as for some more advanced operations such as primality testing.
45	Space is automatically managed by the constructors and destructors.
46
47	This module also provides routines for generating small primes, and
48	fast routines for performing modular arithmetic on single-precision
49	numbers.
50	"""
51	# See ntl.pxd for definition of data members
52
53	def __dealloc__(self):
54	del_ZZ(self.x)
55
56	def __repr__(self):
57	_sig_on
58	return string(ZZ_to_str(self.x))
59
60	def __reduce__(self):
61	raise NotImplementedError
62
63	def __mul__(ntl_ZZ self, other):
64	cdef ntl_ZZ y
65	if not isinstance(other, ntl_ZZ):
66	other = ntl_ZZ(other)
67	y = other
68	_sig_on
69	return make_ZZ(ZZ_mul(self.x, y.x))
70
71	def __sub__(ntl_ZZ self, other):
72	cdef ntl_ZZ y
73	if not isinstance(other, ntl_ZZ):
74	other = ntl_ZZ(other)
75	y = other
76	_sig_on
77	return make_ZZ(ZZ_sub(self.x, y.x))
78
79	def __add__(ntl_ZZ self, other):
80	cdef ntl_ZZ y
81	if not isinstance(other, ntl_ZZ):
82	other = ntl_ZZ(other)
83	y = other
84	_sig_on
85	return make_ZZ(ZZ_add(self.x, y.x))
86
87	def __neg__(ntl_ZZ self):
88	_sig_on
89	return make_ZZ(ZZ_neg(self.x))
90
91	def __pow__(ntl_ZZ self, long e, ignored):
92	_sig_on
93	return make_ZZ(ZZ_pow(self.x, e))
94
95	cdef set(self, void *y): # only used internally for initialization; assumes self.x not set yet!
96	self.x = <ZZ*> y
97
98	cdef int get_as_int(ntl_ZZ self):
99	r"""
100	Returns value as C int.
101	Return value is only valid if the result fits into an int.
102
103	AUTHOR: David Harvey (2006-08-05)
104	"""
105	return ZZ_to_int(self.x)
106
107	def get_as_int_doctest(self):
108	r"""
109	This method exists solely for automated testing of get_as_int().
110
111	sage: x = ntl.ZZ(42)
112	sage: i = x.get_as_int_doctest()
113	sage: print i
114	42
115	sage: print type(i)
116	<type 'int'>
117	"""
118	return self.get_as_int()
119
120	cdef void set_from_int(ntl_ZZ self, int value):
121	r"""
122	Sets the value from a C int.
123
124	AUTHOR: David Harvey (2006-08-05)
125	"""
126	ZZ_set_from_int(self.x, value)
127
128	def set_from_int_doctest(self, value):
129	r"""
130	This method exists solely for automated testing of set_from_int().
131
132	sage: x = ntl.ZZ()
133	sage: x.set_from_int_doctest(42)
134	sage: x
135	42
136	"""
137	self.set_from_int(int(value))
138
139	# todo: add wrapper for int_to_ZZ in wrap.cc?
140
141
142	cdef public make_ZZ(ZZ* x):
143	cdef ntl_ZZ y
144	_sig_off
145	y = ntl_ZZ()
146	y.x = x
147	return y
148
149	def make_new_ZZ(x='0'):
150	s = str(x)
151	cdef ntl_ZZ n
152	n = ntl_ZZ()
153	_sig_on
154	n.x = str_to_ZZ(s)
155	_sig_off
156	return n
157
158	# Random-number generation
159	def ntl_setSeed(x=None):
160	"""
161	Seed the NTL random number generator.
162
163	EXAMPLE:
164	sage: ntl.ntl_setSeed(10)
165	sage: ntl.ZZ_random(1000)
166	776
167	"""
168	cdef ntl_ZZ seed
169	if x is None:
170	from random import randint
171	seed = make_new_ZZ(str(randint(0,int(2)**64)))
172	else:
173	seed = make_new_ZZ(str(x))
174	_sig_on
175	setSeed(seed.x)
176	_sig_off
177
178	ntl_setSeed()
179
180	def randomBnd(q):
181	r"""
182	Returns cryptographically-secure random number in the range [0,n)
183
184	EXAMPLES:
185	sage: [ntl.ZZ_random(99999) for i in range(5)]
186	[53357, 19674, 69528, 87029, 28752]
187
188	AUTHOR:
189	-- Didier Deshommes <dfdeshom@gmail.com>
190	"""
191	cdef ntl_ZZ w
192
193	if not isinstance(q, ntl_ZZ):
194	q = make_new_ZZ(str(q))
195	w = q
196	_sig_on
197	return make_ZZ(ZZ_randomBnd(w.x))
198
199	def randomBits(long n):
200	r"""
201	Return a pseudo-random number between 0 and $2^n-1$
202
203	EXAMPLES:
204	sage: [ntl.ZZ_random_bits(20) for i in range(3)]
205	[1025619, 177635, 766262]
206
207	AUTHOR:
208	-- Didier Deshommes <dfdeshom@gmail.com>
209	"""
210	_sig_on
211	return make_ZZ(ZZ_randomBits(n))
212
213
214	##############################################################################
215	#
216	# ZZX: polynomials over the integers
217	#
218	##############################################################################
219
220
221	cdef class ntl_ZZX:
222	r"""
223	The class \class{ZZX} implements polynomials in $\Z[X]$, i.e.,
224	univariate polynomials with integer coefficients.
225
226	Polynomial multiplication is very fast, and is implemented using
227	one of 4 different algorithms:
228	\begin{enumerate}
229	\item\hspace{1em} Classical
230	\item\hspace{1em} Karatsuba
231	\item\hspace{1em} Schoenhage and Strassen --- performs an FFT by working
232	modulo a "Fermat number" of appropriate size...
233	good for polynomials with huge coefficients
234	and moderate degree
235	\item\hspace{1em} CRT/FFT --- performs an FFT by working modulo several
236	small primes. This is good for polynomials with moderate
237	coefficients and huge degree.
238	\end{enumerate}
239
240	The choice of algorithm is somewhat heuristic, and may not always be
241	perfect.
242
243	Many thanks to Juergen Gerhard {\tt
244	<jngerhar@plato.uni-paderborn.de>} for pointing out the deficiency
245	in the NTL-1.0 ZZX arithmetic, and for contributing the
246	Schoenhage/Strassen code.
247
248	Extensive use is made of modular algorithms to enhance performance
249	(e.g., the GCD algorithm and many others).
250	"""
251
252	# See ntl_ZZX.pxd for definition of data members
253	def __init__(self):
254	"""
255	EXAMPLES:
256	sage: f = ntl.ZZX([1,2,5,-9])
257	sage: f
258	[1 2 5 -9]
259	sage: g = ntl.ZZX([0,0,0]); g
260	[]
261	sage: g[10]=5
262	sage: g
263	[0 0 0 0 0 0 0 0 0 0 5]
264	sage: g[10]
265	5
266	"""
267	return
268
269	def __reduce__(self):
270	raise NotImplementedError
271
272	def __dealloc__(self):
273	if self.x:
274	ZZX_dealloc(self.x)
275
276	def __repr__(self):
277	return str(ZZX_repr(self.x))
278
279	def copy(self):
280	return make_ZZX(ZZX_copy(self.x))
281
282	def __copy__(self):
283	return make_ZZX(ZZX_copy(self.x))
284
285	def __setitem__(self, long i, a):
286	if i < 0:
287	raise IndexError, "index (i=%s) must be >= 0"%i
288	a = str(int(a))
289	ZZX_setitem(self.x, i, a)
290
291	cdef void setitem_from_int(ntl_ZZX self, long i, int value):
292	r"""
293	Sets ith coefficient to value.
294
295	AUTHOR: David Harvey (2006-08-05)
296	"""
297	ZZX_setitem_from_int(self.x, i, value)
298
299	def setitem_from_int_doctest(self, i, value):
300	r"""
301	This method exists solely for automated testing of setitem_from_int().
302
303	sage: x = ntl.ZZX([2, 3, 4])
304	sage: x.setitem_from_int_doctest(5, 42)
305	sage: x
306	[2 3 4 0 0 42]
307	"""
308	self.setitem_from_int(int(i), int(value))
309
310	def __getitem__(self, unsigned int i):
311	r"""
312	Retrieves coefficient #i as a SAGE Integer.
313
314	sage: x = ntl.ZZX([129381729371289371237128318293718237, 2, -3, 0, 4])
315	sage: x[0]
316	129381729371289371237128318293718237
317	sage: type(x[0])
318	<type 'sage.rings.integer.Integer'>
319	sage: x[1]
320	2
321	sage: x[2]
322	-3
323	sage: x[3]
324	0
325	sage: x[4]
326	4
327	sage: x[5]
328	0
329	"""
330	cdef Integer output
331	output = Integer()
332	ZZX_getitem_as_mpz(&output.value, self.x, i)
333	return output
334
335	cdef int getitem_as_int(ntl_ZZX self, long i):
336	r"""
337	Returns ith coefficient as C int.
338	Return value is only valid if the result fits into an int.
339
340	AUTHOR: David Harvey (2006-08-05)
341	"""
342	return ZZX_getitem_as_int(self.x, i)
343
344	def getitem_as_int_doctest(self, i):
345	r"""
346	This method exists solely for automated testing of getitem_as_int().
347
348	sage: x = ntl.ZZX([2, 3, 5, -7, 11])
349	sage: i = x.getitem_as_int_doctest(3)
350	sage: print i
351	-7
352	sage: print type(i)
353	<type 'int'>
354	sage: print x.getitem_as_int_doctest(15)
355	0
356	"""
357	return self.getitem_as_int(i)
358
359	def __add__(ntl_ZZX self, ntl_ZZX other):
360	"""
361	EXAMPLES:
362	sage: ntl.ZZX(range(5)) + ntl.ZZX(range(6))
363	[0 2 4 6 8 5]
364	"""
365	return make_ZZX(ZZX_add(self.x, other.x))
366
367	def __sub__(ntl_ZZX self, ntl_ZZX other):
368	"""
369	EXAMPLES:
370	sage: ntl.ZZX(range(5)) - ntl.ZZX(range(6))
371	[0 0 0 0 0 -5]
372	"""
373	return make_ZZX(ZZX_sub(self.x, other.x))
374
375	def __mul__(ntl_ZZX self, ntl_ZZX other):
376	"""
377	EXAMPLES:
378	sage: ntl.ZZX(range(5)) * ntl.ZZX(range(6))
379	[0 0 1 4 10 20 30 34 31 20]
380	"""
381	_sig_on
382	return make_ZZX(ZZX_mul(self.x, other.x))
383
384	def __div__(ntl_ZZX self, ntl_ZZX other):
385	"""
386	Compute quotient self / other, if the quotient is a polynomial.
387	Otherwise an Exception is raised.
388
389	EXAMPLES:
390	sage: f = ntl.ZZX([1,2,3]) * ntl.ZZX([4,5])**2
391	sage: g = ntl.ZZX([4,5])
392	sage: f/g
393	[4 13 22 15]
394	sage: ntl.ZZX([1,2,3]) * ntl.ZZX([4,5])
395	[4 13 22 15]
396
397	sage: f = ntl.ZZX(range(10)); g = ntl.ZZX([-1,0,1])
398	sage: f/g
399	Traceback (most recent call last):
400	...
401	ArithmeticError: self (=[0 1 2 3 4 5 6 7 8 9]) is not divisible by other (=[-1 0 1])
402	"""
403	_sig_on
404	cdef int divisible
405	cdef ZZX* q
406	q = ZZX_div(self.x, other.x, &divisible)
407	if not divisible:
408	raise ArithmeticError, "self (=%s) is not divisible by other (=%s)"%(self, other)
409	return make_ZZX(q)
410
411	def __mod__(ntl_ZZX self, ntl_ZZX other):
412	"""
413	Given polynomials a, b in ZZ[X], there exist polynomials q, r
414	in QQ[X] such that a = b*q + r, deg(r) < deg(b). This
415	function returns q if q lies in ZZ[X], and otherwise raises an
416	Exception.
417
418	EXAMPLES:
419	sage: f = ntl.ZZX([2,4,6]); g = ntl.ZZX([2])
420	sage: f % g # 0
421	[]
422
423	sage: f = ntl.ZZX(range(10)); g = ntl.ZZX([-1,0,1])
424	sage: f % g
425	[20 25]
426	"""
427	_sig_on
428	return make_ZZX(ZZX_mod(self.x, other.x))
429
430	def quo_rem(self, ntl_ZZX other):
431	"""
432	Returns the unique integral q and r such that self = q*other +
433	r, if they exist. Otherwise raises an Exception.
434
435	EXAMPLES:
436	sage: f = ntl.ZZX(range(10)); g = ntl.ZZX([-1,0,1])
437	sage: q, r = f.quo_rem(g)
438	sage: q, r
439	([20 24 18 21 14 16 8 9], [20 25])
440	sage: q*g + r == f
441	True
442	"""
443	cdef ZZX r, q
444	_sig_on
445	ZZX_quo_rem(self.x, other.x, &r, &q)
446	return (make_ZZX(q), make_ZZX(r))
447
448	def square(self):
449	"""
450	Return f*f.
451
452	EXAMPLES:
453	sage: f = ntl.ZZX([-1,0,1])
454	sage: f*f
455	[1 0 -2 0 1]
456	"""
457	_sig_on
458	return make_ZZX(ZZX_square(self.x))
459
460	def __pow__(ntl_ZZX self, long n, ignored):
461	"""
462	Return the n-th nonnegative power of self.
463
464	EXAMPLES:
465	sage: g = ntl.ZZX([-1,0,1])
466	sage: g**10
467	[1 0 -10 0 45 0 -120 0 210 0 -252 0 210 0 -120 0 45 0 -10 0 1]
468	"""
469	if n < 0:
470	raise NotImplementedError
471	import sage.rings.arith
472	return sage.rings.arith.generic_power(self, n, make_new_ZZX([1]))
473
474	def __cmp__(ntl_ZZX self, ntl_ZZX other):
475	"""
476	Decide whether or not self and other are equal.
477
478	EXAMPLES:
479	sage: f = ntl.ZZX([1,2,3])
480	sage: g = ntl.ZZX([1,2,3,0])
481	sage: f == g
482	True
483	sage: g = ntl.ZZX([0,1,2,3])
484	sage: f == g
485	False
486	"""
487	if ZZX_equal(self.x, other.x):
488	return 0
489	return -1
490
491	def is_zero(self):
492	"""
493	Return True exactly if this polynomial is 0.
494
495	EXAMPLES:
496	sage: f = ntl.ZZX([0,0,0,0])
497	sage: f.is_zero()
498	True
499	sage: f = ntl.ZZX([0,0,1])
500	sage: f
501	[0 0 1]
502	sage: f.is_zero()
503	False
504	"""
505	return bool(ZZX_is_zero(self.x))
506
507	def is_one(self):
508	"""
509	Return True exactly if this polynomial is 1.
510
511	EXAMPLES:
512	sage: f = ntl.ZZX([1,1])
513	sage: f.is_one()
514	False
515	sage: f = ntl.ZZX([1])
516	sage: f.is_one()
517	True
518	"""
519	return bool(ZZX_is_one(self.x))
520
521	def is_monic(self):
522	"""
523	Return True exactly if this polynomial is monic.
524
525	EXAMPLES:
526	sage: f = ntl.ZZX([2,0,0,1])
527	sage: f.is_monic()
528	True
529	sage: g = f.reverse()
530	sage: g.is_monic()
531	False
532	sage: g
533	[1 0 0 2]
534	"""
535	return bool(ZZX_is_monic(self.x))
536
537	def __neg__(self):
538	"""
539	Return the negative of self.
540	EXAMPLES:
541	sage: f = ntl.ZZX([2,0,0,1])
542	sage: -f
543	[-2 0 0 -1]
544	"""
545	return make_ZZX(ZZX_neg(self.x))
546
547	def left_shift(self, long n):
548	"""
549	Return the polynomial obtained by shifting all coefficients of
550	this polynomial to the left n positions.
551
552	EXAMPLES:
553	sage: f = ntl.ZZX([2,0,0,1])
554	sage: f
555	[2 0 0 1]
556	sage: f.left_shift(2)
557	[0 0 2 0 0 1]
558	sage: f.left_shift(5)
559	[0 0 0 0 0 2 0 0 1]
560
561	A negative left shift is a right shift.
562	sage: f.left_shift(-2)
563	[0 1]
564	"""
565	return make_ZZX(ZZX_left_shift(self.x, n))
566
567	def right_shift(self, long n):
568	"""
569	Return the polynomial obtained by shifting all coefficients of
570	this polynomial to the right n positions.
571
572	EXAMPLES:
573	sage: f = ntl.ZZX([2,0,0,1])
574	sage: f
575	[2 0 0 1]
576	sage: f.right_shift(2)
577	[0 1]
578	sage: f.right_shift(5)
579	[]
580	sage: f.right_shift(-2)
581	[0 0 2 0 0 1]
582	"""
583	return make_ZZX(ZZX_right_shift(self.x, n))
584
585	def content(self):
586	"""
587	Return the content of f, which has sign the same as the
588	leading coefficient of f. Also, our convention is that the
589	content of 0 is 0.
590
591	EXAMPLES:
592	sage: f = ntl.ZZX([2,0,0,2])
593	sage: f.content()
594	2
595	sage: f = ntl.ZZX([2,0,0,-2])
596	sage: f.content()
597	-2
598	sage: f = ntl.ZZX([6,12,3,9])
599	sage: f.content()
600	3
601	sage: f = ntl.ZZX([])
602	sage: f.content()
603	0
604	"""
605	cdef char* t
606	t = ZZX_content(self.x)
607	return int(string(t))
608
609	def primitive_part(self):
610	"""
611	Return the primitive part of f. Our convention is that the leading
612	coefficient of the primitive part is nonnegegative, and the primitive
613	part of 0 is 0.
614
615	EXAMPLES:
616	sage: f = ntl.ZZX([6,12,3,9])
617	sage: f.primitive_part()
618	[2 4 1 3]
619	sage: f
620	[6 12 3 9]
621	sage: f = ntl.ZZX([6,12,3,-9])
622	sage: f
623	[6 12 3 -9]
624	sage: f.primitive_part()
625	[-2 -4 -1 3]
626	sage: f = ntl.ZZX()
627	sage: f.primitive_part()
628	[]
629	"""
630	return make_ZZX(ZZX_primitive_part(self.x))
631
632	def pseudo_quo_rem(self, ntl_ZZX other):
633	r"""
634	Performs pseudo-division: computes q and r with deg(r) <
635	deg(b), and \code{LeadCoeff(b)\^(deg(a)-deg(b)+1) a = b q + r}.
636	Only the classical algorithm is used.
637
638	EXAMPLES:
639	sage: f = ntl.ZZX([0,1])
640	sage: g = ntl.ZZX([1,2,3])
641	sage: g.pseudo_quo_rem(f)
642	([2 3], [1])
643	sage: f = ntl.ZZX([1,1])
644	sage: g.pseudo_quo_rem(f)
645	([-1 3], [2])
646	"""
647	cdef ZZX r, q
648	_sig_on
649	ZZX_pseudo_quo_rem(self.x, other.x, &r, &q)
650	return (make_ZZX(q), make_ZZX(r))
651
652	def gcd(self, ntl_ZZX other):
653	"""
654	Return the gcd d = gcd(a, b), where by convention the leading coefficient
655	of d is >= 0. We use a multi-modular algorithm.
656
657	EXAMPLES:
658	sage: f = ntl.ZZX([1,2,3]) * ntl.ZZX([4,5])**2
659	sage: g = ntl.ZZX([1,1,1])*3 ntl.ZZX([1,2,3])
660	sage: f.gcd(g)
661	[1 2 3]
662	sage: g.gcd(f)
663	[1 2 3]
664	"""
665	_sig_on
666	return make_ZZX(ZZX_gcd(self.x, other.x))
667
668	def lcm(self, ntl_ZZX other):
669	"""
670	Return the least common multiple of self and other.
671	"""
672	g = self.gcd(other)
673	return (self*other).quo_rem(g)[0]
674
675	def xgcd(self, ntl_ZZX other, proof=True):
676	"""
677	If self and other are coprime over the rationals, return r, s,
678	t such that r = sself + tother. Otherwise return 0. This
679	is \emph{not} the same as the \sage function on polynomials
680	over the integers, since here the return value r is always an
681	integer.
682
683	Here r is the resultant of a and b; if r != 0, then this
684	function computes s and t such that: as + bt = r; otherwise
685	s and t are both 0. If proof = False (not the default),
686	then resultant computation may use a randomized strategy that
687	errs with probability no more than $2^{-80}$.
688
689	EXAMPLES:
690	sage: f = ntl.ZZX([1,2,3]) * ntl.ZZX([4,5])**2
691	sage: g = ntl.ZZX([1,1,1])*3 ntl.ZZX([1,2,3])
692	sage: f.xgcd(g) # nothing since they are not coprime
693	(0, [], [])
694
695	In this example the input quadratic polynomials have a common root modulo 13.
696	sage: f = ntl.ZZX([5,0,1])
697	sage: g = ntl.ZZX([18,0,1])
698	sage: f.xgcd(g)
699	(169, [-13], [13])
700	"""
701	cdef ZZX s, t
702	cdef ZZ *r
703	_sig_on
704	ZZX_xgcd(self.x, other.x, &r, &s, &t, proof)
705	return (make_ZZ(r), make_ZZX(s), make_ZZX(t))
706
707	def degree(self):
708	"""
709	Return the degree of this polynomial. The degree of the 0
710	polynomial is -1.
711
712	EXAMPLES:
713	sage: f = ntl.ZZX([5,0,1])
714	sage: f.degree()
715	2
716	sage: f = ntl.ZZX(range(100))
717	sage: f.degree()
718	99
719	sage: f = ntl.ZZX()
720	sage: f.degree()
721	-1
722	sage: f = ntl.ZZX([1])
723	sage: f.degree()
724	0
725	"""
726	return ZZX_degree(self.x)
727
728	def leading_coefficient(self):
729	"""
730	Return the leading coefficient of this polynomial.
731
732	EXAMPLES:
733	sage: f = ntl.ZZX([3,6,9])
734	sage: f.leading_coefficient()
735	9
736	sage: f = ntl.ZZX()
737	sage: f.leading_coefficient()
738	0
739	"""
740	return make_ZZ(ZZX_leading_coefficient(self.x))
741
742	def constant_term(self):
743	"""
744	Return the constant coefficient of this polynomial.
745
746	EXAMPLES:
747	sage: f = ntl.ZZX([3,6,9])
748	sage: f.constant_term()
749	3
750	sage: f = ntl.ZZX()
751	sage: f.constant_term()
752	0
753	"""
754	cdef char* t
755	t = ZZX_constant_term(self.x)
756	return int(string(t))
757
758	def set_x(self):
759	"""
760	Set this polynomial to the monomial "x".
761
762	EXAMPLES:
763	sage: f = ntl.ZZX()
764	sage: f.set_x()
765	sage: f
766	[0 1]
767	sage: g = ntl.ZZX([0,1])
768	sage: f == g
769	True
770
771	Though f and g are equal, they are not the same objects in memory:
772	sage: f is g
773	False
774
775	"""
776	ZZX_set_x(self.x)
777
778	def is_x(self):
779	"""
780	True if this is the polynomial "x".
781
782	EXAMPLES:
783	sage: f = ntl.ZZX()
784	sage: f.set_x()
785	sage: f.is_x()
786	True
787	sage: f = ntl.ZZX([0,1])
788	sage: f.is_x()
789	True
790	sage: f = ntl.ZZX([1])
791	sage: f.is_x()
792	False
793	"""
794	return bool(ZZX_is_x(self.x))
795
796	def derivative(self):
797	"""
798	Return the derivative of this polynomial.
799
800	EXAMPLES:
801	sage: f = ntl.ZZX([1,7,0,13])
802	sage: f.derivative()
803	[7 0 39]
804	"""
805	return make_ZZX(ZZX_derivative(self.x))
806
807	def reverse(self, hi=None):
808	"""
809	Return the polynomial obtained by reversing the coefficients
810	of this polynomial. If hi is set then this function behaves
811	as if this polynomial has degree hi.
812
813	EXAMPLES:
814	sage: f = ntl.ZZX([1,2,3,4,5])
815	sage: f.reverse()
816	[5 4 3 2 1]
817	sage: f.reverse(hi=10)
818	[0 0 0 0 0 0 5 4 3 2 1]
819	sage: f.reverse(hi=2)
820	[3 2 1]
821	sage: f.reverse(hi=-2)
822	[]
823	"""
824	if not (hi is None):
825	return make_ZZX(ZZX_reverse_hi(self.x, int(hi)))
826	else:
827	return make_ZZX(ZZX_reverse(self.x))
828
829	def truncate(self, long m):
830	"""
831	Return the truncation of this polynomial obtained by
832	removing all terms of degree >= m.
833
834	EXAMPLES:
835	sage: f = ntl.ZZX([1,2,3,4,5])
836	sage: f.truncate(3)
837	[1 2 3]
838	sage: f.truncate(8)
839	[1 2 3 4 5]
840	sage: f.truncate(1)
841	[1]
842	sage: f.truncate(0)
843	[]
844	sage: f.truncate(-1)
845	[]
846	sage: f.truncate(-5)
847	[]
848	"""
849	if m <= 0:
850	return make_new_ZZX()
851	return make_ZZX(ZZX_truncate(self.x, m))
852
853	def multiply_and_truncate(self, ntl_ZZX other, long m):
854	"""
855	Return self*other but with terms of degree >= m removed.
856
857	EXAMPLES:
858	sage: f = ntl.ZZX([1,2,3,4,5])
859	sage: g = ntl.ZZX([10])
860	sage: f.multiply_and_truncate(g, 2)
861	[10 20]
862	sage: g.multiply_and_truncate(f, 2)
863	[10 20]
864	"""
865	if m <= 0:
866	return make_new_ZZX()
867	return make_ZZX(ZZX_multiply_and_truncate(self.x, other.x, m))
868
869	def square_and_truncate(self, long m):
870	"""
871	Return self*self but with terms of degree >= m removed.
872
873	EXAMPLES:
874	sage: f = ntl.ZZX([1,2,3,4,5])
875	sage: f.square_and_truncate(4)
876	[1 4 10 20]
877	sage: (f*f).truncate(4)
878	[1 4 10 20]
879	"""
880	if m < 0:
881	return make_new_ZZX()
882	return make_ZZX(ZZX_square_and_truncate(self.x, m))
883
884	def invert_and_truncate(self, long m):
885	"""
886	Compute and return the inverse of self modulo $x^m$.
887	The constant term of self must be 1 or -1.
888
889	EXAMPLES:
890	sage: f = ntl.ZZX([1,2,3,4,5,6,7])
891	sage: f.invert_and_truncate(20)
892	[1 -2 1 0 0 0 0 8 -23 22 -7 0 0 0 64 -240 337 -210 49]
893	sage: g = f.invert_and_truncate(20)
894	sage: g * f
895	[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -512 1344 -1176 343]
896	"""
897	if m < 0:
898	raise ArithmeticError, "m (=%s) must be positive"%m
899	n = self.constant_term()
900	if n != 1 and n != -1:
901	raise ArithmeticError, \
902	"The constant term of self must be 1 or -1."
903	_sig_on
904	return make_ZZX(ZZX_invert_and_truncate(self.x, m))
905
906	def multiply_mod(self, ntl_ZZX other, ntl_ZZX modulus):
907	"""
908	Return self*other % modulus. The modulus must be monic with
909	deg(modulus) > 0, and self and other must have smaller degree.
910
911	EXAMPLES:
912	sage: modulus = ntl.ZZX([1,2,0,1]) # must be monic
913	sage: g = ntl.ZZX([-1,0,1])
914	sage: h = ntl.ZZX([3,7,13])
915	sage: h.multiply_mod(g, modulus)
916	[-10 -34 -36]
917	"""
918	_sig_on
919	return make_ZZX(ZZX_multiply_mod(self.x, other.x, modulus.x))
920
921	def trace_mod(self, ntl_ZZX modulus):
922	"""
923	Return the trace of this polynomial modulus the modulus.
924	The modulus must be monic, and of positive degree degree bigger
925	than the the degree of self.
926
927	EXAMPLES:
928	sage: f = ntl.ZZX([1,2,0,3])
929	sage: mod = ntl.ZZX([5,3,-1,1,1])
930	sage: f.trace_mod(mod)
931	-37
932	"""
933	_sig_on
934	return make_ZZ(ZZX_trace_mod(self.x, modulus.x))
935
936	def trace_list(self):
937	"""
938	Return the list of traces of the powers $x^i$ of the
939	monomial x modulo this polynomial for i = 0, ..., deg(f)-1.
940	This polynomial must be monic.
941
942	EXAMPLES:
943	sage: f = ntl.ZZX([1,2,0,3,0,1])
944	sage: f.trace_list()
945	[5, 0, -6, 0, 10]
946
947	The input polynomial must be monic or a ValueError is raised:
948	sage: f = ntl.ZZX([1,2,0,3,0,2])
949	sage: f.trace_list()
950	Traceback (most recent call last):
951	...
952	ValueError: polynomial must be monic.
953	"""
954	if not self.is_monic():
955	raise ValueError, "polynomial must be monic."
956	_sig_on
957	cdef char* t
958	t = ZZX_trace_list(self.x)
959	return eval(string(t).replace(' ', ','))
960
961	def resultant(self, ntl_ZZX other, proof=True):
962	"""
963	Return the resultant of self and other. If proof = False (the
964	default is proof=True), then this function may use a
965	randomized strategy that errors with probability no more than
966	$2^{-80}$.
967
968	EXAMPLES:
969	sage: f = ntl.ZZX([17,0,1,1])
970	sage: g = ntl.ZZX([34,-17,18,2])
971	sage: f.resultant(g)
972	1345873
973	sage: f.resultant(g, proof=False)
974	1345873
975	"""
976	# NOTES: Within a factor of 2 in speed compared to MAGMA.
977	_sig_on
978	return make_ZZ(ZZX_resultant(self.x, other.x, proof))
979
980	def norm_mod(self, ntl_ZZX modulus, proof=True):
981	"""
982	Return the norm of this polynomial modulo the modulus. The
983	modulus must be monic, and of positive degree strictly greater
984	than the degree of self. If proof=False (the default is
985	proof=True) then it may use a randomized strategy that errors
986	with probability no more than $2^{-80}$.
987
988
989	EXAMPLE:
990	sage: f = ntl.ZZX([1,2,0,3])
991	sage: mod = ntl.ZZX([-5,2,0,0,1])
992	sage: f.norm_mod(mod)
993	-8846
994
995	The norm is the constant term of the characteristic polynomial.
996	sage: f.charpoly_mod(mod)
997	[-8846 -594 -60 14 1]
998	"""
999	_sig_on
1000	return make_ZZ(ZZX_norm_mod(self.x, modulus.x, proof))
1001
1002	def discriminant(self, proof=True):
1003	r"""
1004	Return the discriminant of self, which is by definition
1005	$$
1006	(-1)^{m(m-1)/2} {\mbox{\tt resultant}}(a, a')/lc(a),
1007	$$
1008	where m = deg(a), and lc(a) is the leading coefficient of a.
1009	If proof is False (the default is True), then this function
1010	may use a randomized strategy that errors with probability no
1011	more than $2^{-80}$.
1012	EXAMPLES:
1013	sage: f = ntl.ZZX([1,2,0,3])
1014	sage: f.discriminant()
1015	-339
1016	sage: f.discriminant(proof=False)
1017	-339
1018	"""
1019	_sig_on
1020	return make_ZZ(ZZX_discriminant(self.x, proof))
1021
1022	#def __call__(self, ntl_ZZ a):
1023	# _sig_on
1024	# return make_ZZ(ZZX_polyeval(self.x, a.x))
1025
1026	def charpoly_mod(self, ntl_ZZX modulus, proof=True):
1027	"""
1028	Return the characteristic polynomial of this polynomial modulo
1029	the modulus. The modulus must be monic of degree bigger than
1030	self. If proof=False (the default is True), then this function
1031	may use a randomized strategy that errors with probability no
1032	more than $2^{-80}$.
1033
1034	EXAMPLES:
1035	sage: f = ntl.ZZX([1,2,0,3])
1036	sage: mod = ntl.ZZX([-5,2,0,0,1])
1037	sage: f.charpoly_mod(mod)
1038	[-8846 -594 -60 14 1]
1039
1040	"""
1041	_sig_on
1042	return make_ZZX(ZZX_charpoly_mod(self.x, modulus.x, proof))
1043
1044	def minpoly_mod_noproof(self, ntl_ZZX modulus):
1045	"""
1046	Return the minimal polynomial of this polynomial modulo the
1047	modulus. The modulus must be monic of degree bigger than
1048	self. In all cases, this function may use a randomized
1049	strategy that errors with probability no more than $2^{-80}$.
1050
1051	EXAMPLES:
1052	sage: f = ntl.ZZX([0,0,1])
1053	sage: g = f*f
1054	sage: f.charpoly_mod(g)
1055	[0 0 0 0 1]
1056
1057	However, since $f^2 = 0$ moduluo $g$, its minimal polynomial
1058	is of degree $2$.
1059	sage: f.minpoly_mod_noproof(g)
1060	[0 0 1]
1061	"""
1062	_sig_on
1063	return make_ZZX(ZZX_minpoly_mod(self.x, modulus.x))
1064
1065	def clear(self):
1066	"""
1067	Reset this polynomial to 0. Changes this polynomial in place.
1068
1069	EXAMPLES:
1070	sage: f = ntl.ZZX([1,2,3])
1071	sage: f
1072	[1 2 3]
1073	sage: f.clear()
1074	sage: f
1075	[]
1076	"""
1077	ZZX_clear(self.x)
1078
1079	def preallocate_space(self, long n):
1080	"""
1081	Pre-allocate spaces for n coefficients. The polynomial that f
1082	represents is unchanged. This is useful if you know you'll be
1083	setting coefficients up to n, so memory isn't re-allocated as
1084	the polynomial grows. (You might save a millisecond with this
1085	function.)
1086
1087	EXAMPLES:
1088	sage: f = ntl.ZZX([1,2,3])
1089	sage: f.preallocate_space(20)
1090	sage: f
1091	[1 2 3]
1092	sage: f[10]=5 # no new memory is allocated
1093	sage: f
1094	[1 2 3 0 0 0 0 0 0 0 5]
1095	"""
1096	_sig_on
1097	ZZX_preallocate_space(self.x, n)
1098	_sig_off
1099
1100
1101	cdef set(self, void* x): # only used internally for initialization; assumes self.x not set yet!
1102	self.x = <ZZX*>x
1103
1104	cdef make_ZZX(ZZX* x):
1105	cdef ntl_ZZX y
1106	_sig_off
1107	y = ntl_ZZX()
1108	y.x = x
1109	return y
1110
1111	def make_new_ZZX(v=[]):
1112	s = str(v).replace(',',' ')
1113	cdef ntl_ZZX z
1114	z = ntl_ZZX()
1115	_sig_on
1116	z.x = str_to_ZZX(s)
1117	_sig_off
1118	return z
1119
1120
1121	##############################################################################
1122	#
1123	# ZZ_p: integers modulo p
1124	#
1125	##############################################################################
1126	cdef class ntl_ZZ_p:
1127	r"""
1128	The \class{ZZ_p} class is used to represent integers modulo $p$.
1129	The modulus $p$ may be any positive integer, not necessarily prime.
1130
1131	Objects of the class \class{ZZ_p} are represented as a \code{ZZ} in the
1132	range $0, \ldots, p-1$.
1133
1134	An executing program maintains a "current modulus", which is set to p
1135	with ntl_ZZ_p.init(p). The current modulus should be initialized before
1136	any ZZ_p objects are created.
1137
1138	The modulus may be changed, and a mechanism is provided for saving and
1139	restoring a modulus (see classes ZZ_pBak and ZZ_pContext below).
1140
1141	TODO: This documentation is wrong
1142	"""
1143	# See ntl.pxd for definition of data members
1144
1145	def __reduce__(self):
1146	raise NotImplementedError
1147
1148	def __dealloc__(self):
1149	del_ZZ_p(self.x)
1150
1151	def __repr__(self):
1152	_sig_on
1153	return string(ZZ_p_to_str(self.x))
1154
1155	def __cmp__(ntl_ZZ_p self, ntl_ZZ_p other):
1156	cdef int t
1157	_sig_on
1158	t = ZZ_p_eq(self.x, other.x)
1159	_sig_off
1160	if t:
1161	return 0
1162	return 1
1163
1164	def __invert__(ntl_ZZ_p self):
1165	_sig_on
1166	return make_ZZ_p(ZZ_p_inv(self.x))
1167
1168
1169	def __mul__(ntl_ZZ_p self, other):
1170	cdef ntl_ZZ_p y
1171	if not isinstance(other, ntl_ZZ_p):
1172	other = ntl_ZZ_p(other)
1173	y = other
1174	_sig_on
1175	return make_ZZ_p(ZZ_p_mul(self.x, y.x))
1176
1177	def __sub__(ntl_ZZ_p self, other):
1178	cdef ntl_ZZ_p y
1179	if not isinstance(other, ntl_ZZ_p):
1180	other = ntl_ZZ_p(other)
1181	y = other
1182	_sig_on
1183	return make_ZZ_p(ZZ_p_sub(self.x, y.x))
1184
1185	def __add__(ntl_ZZ_p self, other):
1186	cdef ntl_ZZ_p y
1187	if not isinstance(other, ntl_ZZ_p):
1188	other = ntl_ZZ_p(other)
1189	y = other
1190	_sig_on
1191	return make_ZZ_p(ZZ_p_add(self.x, y.x))
1192
1193	def __neg__(ntl_ZZ_p self):
1194	_sig_on
1195	return make_ZZ_p(ZZ_p_neg(self.x))
1196
1197	def __pow__(ntl_ZZ_p self, long e, ignored):
1198	_sig_on
1199	return make_ZZ_p(ZZ_p_pow(self.x, e))
1200
1201	cdef set(self, void *y): # only used internally for initialization; assumes self.x not set yet!
1202	self.x = <ZZ_p*> y
1203
1204	cdef int get_as_int(ntl_ZZ_p self):
1205	r"""
1206	Returns value as C int.
1207	Return value is only valid if the result fits into an int.
1208
1209	AUTHOR: David Harvey (2006-08-05)
1210	"""
1211	return ZZ_p_to_int(self.x)
1212
1213	def get_as_int_doctest(self):
1214	r"""
1215	This method exists solely for automated testing of get_as_int().
1216
1217	sage: ntl.set_modulus(ntl.ZZ(20))
1218	sage: x = ntl.ZZ_p(42)
1219	sage: i = x.get_as_int_doctest()
1220	sage: print i
1221	2
1222	sage: print type(i)
1223	<type 'int'>
1224	"""
1225	return self.get_as_int()
1226
1227	cdef void set_from_int(ntl_ZZ_p self, int value):
1228	r"""
1229	Sets the value from a C int.
1230
1231	AUTHOR: David Harvey (2006-08-05)
1232	"""
1233	ZZ_p_set_from_int(self.x, value)
1234
1235	def set_from_int_doctest(self, value):
1236	r"""
1237	This method exists solely for automated testing of set_from_int().
1238
1239	sage: ntl.set_modulus(ntl.ZZ(20))
1240	sage: x = ntl.ZZ_p()
1241	sage: x.set_from_int_doctest(42)
1242	sage: x
1243	2
1244	"""
1245	self.set_from_int(int(value))
1246
1247	# todo: add wrapper for int_to_ZZ_p in wrap.cc?
1248
1249
1250	cdef public make_ZZ_p(ZZ_p* x):
1251	cdef ntl_ZZ_p y
1252	_sig_off
1253	y = ntl_ZZ_p()
1254	y.x = x
1255	return y
1256
1257	def make_new_ZZ_p(x='0'):
1258	s = str(x)
1259	cdef ntl_ZZ_p n
1260	n = ntl_ZZ_p()
1261	_sig_on
1262	n.x = str_to_ZZ_p(s)
1263	_sig_off
1264	return n
1265
1266	def set_ZZ_p_modulus(ntl_ZZ p):
1267	ntl_ZZ_set_modulus(<ZZ*>p.x)
1268
1269
1270	def ntl_ZZ_p_random():
1271	"""
1272	Return a random number modulo p.
1273	"""
1274	_sig_on
1275	return make_ZZ_p(ZZ_p_random())
1276
1277	##############################################################################
1278	#
1279	# ZZ_pX -- polynomials over the integers modulo p
1280	#
1281	##############################################################################
1282
1283	cdef class ntl_ZZ_pX:
1284	r"""
1285	The class \class{ZZ_pX} implements polynomial arithmetic modulo $p$.
1286
1287	Polynomial arithmetic is implemented using the FFT, combined with
1288	the Chinese Remainder Theorem. A more detailed description of the
1289	techniques used here can be found in [Shoup, J. Symbolic
1290	Comp. 20:363-397, 1995].
1291
1292	Small degree polynomials are multiplied either with classical
1293	or Karatsuba algorithms.
1294	"""
1295	# See ntl_ZZ_pX.pxd for definition of data members
1296	def __init__(self):
1297	"""
1298	EXAMPLES:
1299	sage: ntl.set_modulus(ntl.ZZ(20))
1300	sage: f = ntl.ZZ_pX([1,2,5,-9])
1301	sage: f
1302	[1 2 5 11]
1303	sage: g = ntl.ZZ_pX([0,0,0]); g
1304	[]
1305	sage: g[10]=5
1306	sage: g
1307	[0 0 0 0 0 0 0 0 0 0 5]
1308	sage: g[10]
1309	5
1310	"""
1311	return
1312
1313	def __reduce__(self):
1314	raise NotImplementedError
1315
1316	def __dealloc__(self):
1317	if self.x:
1318	ZZ_pX_dealloc(self.x)
1319
1320
1321	def __repr__(self):
1322	return str(ZZ_pX_repr(self.x))
1323
1324	def __copy__(self):
1325	return make_ZZ_pX(ZZ_pX_copy(self.x))
1326
1327	def copy(self):
1328	return make_ZZ_pX(ZZ_pX_copy(self.x))
1329
1330	cdef set(self, void* x): # only used internally for initialization; assumes self.x not set yet!
1331	self.x = <ZZ_pX*>x
1332
1333	def __setitem__(self, long i, a):
1334	if i < 0:
1335	raise IndexError, "index (i=%s) must be >= 0"%i
1336	a = str(int(a))
1337	ZZ_pX_setitem(self.x, i, a)
1338
1339	cdef void setitem_from_int(ntl_ZZ_pX self, long i, int value):
1340	r"""
1341	Sets ith coefficient to value.
1342
1343	AUTHOR: David Harvey (2006-08-05)
1344	"""
1345	ZZ_pX_setitem_from_int(self.x, i, value)
1346
1347	def setitem_from_int_doctest(self, i, value):
1348	r"""
1349	This method exists solely for automated testing of setitem_from_int().
1350
1351	sage: ntl.set_modulus(ntl.ZZ(20))
1352	sage: x = ntl.ZZ_pX([2, 3, 4])
1353	sage: x.setitem_from_int_doctest(5, 42)
1354	sage: x
1355	[2 3 4 0 0 2]
1356	"""
1357	self.setitem_from_int(int(i), int(value))
1358
1359	def __getitem__(self, unsigned int i):
1360	cdef char* t
1361	t = ZZ_pX_getitem(self.x,i)
1362	return int(string(t))
1363
1364	cdef int getitem_as_int(ntl_ZZ_pX self, long i):
1365	r"""
1366	Returns ith coefficient as C int.
1367	Return value is only valid if the result fits into an int.
1368
1369	AUTHOR: David Harvey (2006-08-05)
1370	"""
1371	return ZZ_pX_getitem_as_int(self.x, i)
1372
1373	def getitem_as_int_doctest(self, i):
1374	r"""
1375	This method exists solely for automated testing of getitem_as_int().
1376
1377	sage: ntl.set_modulus(ntl.ZZ(20))
1378	sage: x = ntl.ZZ_pX([2, 3, 5, -7, 11])
1379	sage: i = x.getitem_as_int_doctest(3)
1380	sage: print i
1381	13
1382	sage: print type(i)
1383	<type 'int'>
1384	sage: print x.getitem_as_int_doctest(15)
1385	0
1386	"""
1387	return self.getitem_as_int(i)
1388
1389	def list(self):
1390	"""
1391	Return list of entries as a list of Python int's.
1392	"""
1393	return eval(str(self).replace(' ',','))
1394
1395	def __add__(ntl_ZZ_pX self, ntl_ZZ_pX other):
1396	"""
1397	EXAMPLES:
1398	sage: ntl.set_modulus(ntl.ZZ(20))
1399	sage: ntl.ZZ_pX(range(5)) + ntl.ZZ_pX(range(6))
1400	[0 2 4 6 8 5]
1401	"""
1402	return make_ZZ_pX(ZZ_pX_add(self.x, other.x))
1403
1404	def __sub__(ntl_ZZ_pX self, ntl_ZZ_pX other):
1405	"""
1406	EXAMPLES:
1407	sage: ntl.set_modulus(ntl.ZZ(20))
1408	sage: ntl.ZZ_pX(range(5)) - ntl.ZZ_pX(range(6))
1409	[0 0 0 0 0 15]
1410	"""
1411	return make_ZZ_pX(ZZ_pX_sub(self.x, other.x))
1412
1413	def __mul__(ntl_ZZ_pX self, ntl_ZZ_pX other):
1414	"""
1415	EXAMPLES:
1416	sage: ntl.set_modulus(ntl.ZZ(20))
1417	sage: ntl.ZZ_pX(range(5)) * ntl.ZZ_pX(range(6))
1418	[0 0 1 4 10 0 10 14 11]
1419	"""
1420	_sig_on
1421	return make_ZZ_pX(ZZ_pX_mul(self.x, other.x))
1422
1423	def __div__(ntl_ZZ_pX self, ntl_ZZ_pX other):
1424	"""
1425	Compute quotient self / other, if the quotient is a polynomial.
1426	Otherwise an Exception is raised.
1427
1428	EXAMPLES:
1429	sage: ntl.set_modulus(ntl.ZZ(17))
1430	sage: f = ntl.ZZ_pX([1,2,3]) * ntl.ZZ_pX([4,5])**2
1431	sage: g = ntl.ZZ_pX([4,5])
1432	sage: f/g
1433	[4 13 5 15]
1434	sage: ntl.ZZ_pX([1,2,3]) * ntl.ZZ_pX([4,5])
1435	[4 13 5 15]
1436
1437	sage: f = ntl.ZZ_pX(range(10)); g = ntl.ZZ_pX([-1,0,1])
1438	sage: f/g
1439	Traceback (most recent call last):
1440	...
1441	ArithmeticError: self (=[0 1 2 3 4 5 6 7 8 9]) is not divisible by other (=[16 0 1])
1442	"""
1443	_sig_on
1444	cdef int divisible
1445	cdef ZZ_pX* q
1446	q = ZZ_pX_div(self.x, other.x, &divisible)
1447	if not divisible:
1448	raise ArithmeticError, "self (=%s) is not divisible by other (=%s)"%(self, other)
1449	return make_ZZ_pX(q)
1450
1451	def __mod__(ntl_ZZ_pX self, ntl_ZZ_pX other):
1452	"""
1453	Given polynomials a, b in ZZ[X], there exist polynomials q, r
1454	in QQ[X] such that a = b*q + r, deg(r) < deg(b). This
1455	function returns q if q lies in ZZ[X], and otherwise raises an
1456	Exception.
1457
1458	EXAMPLES:
1459	sage: ntl.set_modulus(ntl.ZZ(17))
1460	sage: f = ntl.ZZ_pX([2,4,6]); g = ntl.ZZ_pX([2])
1461	sage: f % g # 0
1462	[]
1463
1464	sage: f = ntl.ZZ_pX(range(10)); g = ntl.ZZ_pX([-1,0,1])
1465	sage: f % g
1466	[3 8]
1467	"""
1468	_sig_on
1469	return make_ZZ_pX(ZZ_pX_mod(self.x, other.x))
1470
1471	def quo_rem(self, ntl_ZZ_pX other):
1472	"""
1473	Returns the unique integral q and r such that self = q*other +
1474	r, if they exist. Otherwise raises an Exception.
1475
1476	EXAMPLES:
1477	sage: ntl.set_modulus(ntl.ZZ(17))
1478	sage: f = ntl.ZZ_pX(range(10)); g = ntl.ZZ_pX([-1,0,1])
1479	sage: q, r = f.quo_rem(g)
1480	sage: q, r
1481	([3 7 1 4 14 16 8 9], [3 8])
1482	sage: q*g + r == f
1483	True
1484	"""
1485	cdef ZZ_pX r, q
1486	_sig_on
1487	ZZ_pX_quo_rem(self.x, other.x, &r, &q)
1488	return (make_ZZ_pX(q), make_ZZ_pX(r))
1489
1490	def square(self):
1491	"""
1492	Return f*f.
1493
1494	EXAMPLES:
1495	sage: ntl.set_modulus(ntl.ZZ(17))
1496	sage: f = ntl.ZZ_pX([-1,0,1])
1497	sage: f*f
1498	[1 0 15 0 1]
1499	"""
1500	_sig_on
1501	return make_ZZ_pX(ZZ_pX_square(self.x))
1502
1503	def __pow__(ntl_ZZ_pX self, long n, ignored):
1504	"""
1505	Return the n-th nonnegative power of self.
1506
1507	EXAMPLES:
1508	sage: ntl.set_modulus(ntl.ZZ(20))
1509	sage: g = ntl.ZZ_pX([-1,0,1])
1510	sage: g**10
1511	[1 0 10 0 5 0 0 0 10 0 8 0 10 0 0 0 5 0 10 0 1]
1512	"""
1513	if n < 0:
1514	raise NotImplementedError
1515	import sage.rings.arith
1516	return sage.rings.arith.generic_power(self, n, make_new_ZZ_pX([1]))
1517
1518	def __cmp__(ntl_ZZ_pX self, ntl_ZZ_pX other):
1519	"""
1520	Decide whether or not self and other are equal.
1521
1522	EXAMPLES:
1523	sage: ntl.set_modulus(ntl.ZZ(20))
1524	sage: f = ntl.ZZ_pX([1,2,3])
1525	sage: g = ntl.ZZ_pX([1,2,3,0])
1526	sage: f == g
1527	True
1528	sage: g = ntl.ZZ_pX([0,1,2,3])
1529	sage: f == g
1530	False
1531	"""
1532	if ZZ_pX_equal(self.x, other.x):
1533	return 0
1534	return -1
1535
1536	def is_zero(self):
1537	"""
1538	Return True exactly if this polynomial is 0.
1539
1540	EXAMPLES:
1541	sage: ntl.set_modulus(ntl.ZZ(20))
1542	sage: f = ntl.ZZ_pX([0,0,0,20])
1543	sage: f.is_zero()
1544	True
1545	sage: f = ntl.ZZ_pX([0,0,1])
1546	sage: f
1547	[0 0 1]
1548	sage: f.is_zero()
1549	False
1550	"""
1551	return bool(ZZ_pX_is_zero(self.x))
1552
1553	def is_one(self):
1554	"""
1555	Return True exactly if this polynomial is 1.
1556
1557	EXAMPLES:
1558	sage: ntl.set_modulus(ntl.ZZ(20))
1559	sage: f = ntl.ZZ_pX([1,1])
1560	sage: f.is_one()
1561	False
1562	sage: f = ntl.ZZ_pX([1])
1563	sage: f.is_one()
1564	True
1565	"""
1566	return bool(ZZ_pX_is_one(self.x))
1567
1568	def is_monic(self):
1569	"""
1570	Return True exactly if this polynomial is monic.
1571
1572	EXAMPLES:
1573	sage: ntl.set_modulus(ntl.ZZ(20))
1574	sage: f = ntl.ZZ_pX([2,0,0,1])
1575	sage: f.is_monic()
1576	True
1577	sage: g = f.reverse()
1578	sage: g.is_monic()
1579	False
1580	sage: g
1581	[1 0 0 2]
1582	"""
1583	return bool(ZZ_pX_is_monic(self.x))
1584
1585	def __neg__(self):
1586	"""
1587	Return the negative of self.
1588	EXAMPLES:
1589	sage: ntl.set_modulus(ntl.ZZ(20))
1590	sage: f = ntl.ZZ_pX([2,0,0,1])
1591	sage: -f
1592	[18 0 0 19]
1593	"""
1594	return make_ZZ_pX(ZZ_pX_neg(self.x))
1595
1596	def left_shift(self, long n):
1597	"""
1598	Return the polynomial obtained by shifting all coefficients of
1599	this polynomial to the left n positions.
1600
1601	EXAMPLES:
1602	sage: ntl.set_modulus(ntl.ZZ(20))
1603	sage: f = ntl.ZZ_pX([2,0,0,1])
1604	sage: f
1605	[2 0 0 1]
1606	sage: f.left_shift(2)
1607	[0 0 2 0 0 1]
1608	sage: f.left_shift(5)
1609	[0 0 0 0 0 2 0 0 1]
1610
1611	A negative left shift is a right shift.
1612	sage: f.left_shift(-2)
1613	[0 1]
1614	"""
1615	return make_ZZ_pX(ZZ_pX_left_shift(self.x, n))
1616
1617	def right_shift(self, long n):
1618	"""
1619	Return the polynomial obtained by shifting all coefficients of
1620	this polynomial to the right n positions.
1621
1622	EXAMPLES:
1623	sage: ntl.set_modulus(ntl.ZZ(20))
1624	sage: f = ntl.ZZ_pX([2,0,0,1])
1625	sage: f
1626	[2 0 0 1]
1627	sage: f.right_shift(2)
1628	[0 1]
1629	sage: f.right_shift(5)
1630	[]
1631	sage: f.right_shift(-2)
1632	[0 0 2 0 0 1]
1633	"""
1634	return make_ZZ_pX(ZZ_pX_right_shift(self.x, n))
1635
1636	def gcd(self, ntl_ZZ_pX other):
1637	"""
1638	Return the gcd d = gcd(a, b), where by convention the leading coefficient
1639	of d is >= 0. We uses a multi-modular algorithm.
1640
1641	EXAMPLES:
1642	sage: ntl.set_modulus(ntl.ZZ(17))
1643	sage: f = ntl.ZZ_pX([1,2,3]) * ntl.ZZ_pX([4,5])**2
1644	sage: g = ntl.ZZ_pX([1,1,1])*3 ntl.ZZ_pX([1,2,3])
1645	sage: f.gcd(g)
1646	[6 12 1]
1647	sage: g.gcd(f)
1648	[6 12 1]
1649	"""
1650	_sig_on
1651	return make_ZZ_pX(ZZ_pX_gcd(self.x, other.x))
1652
1653	def xgcd(self, ntl_ZZ_pX other, plain=True):
1654	"""
1655	Returns r,s,t such that r = sself + tother.
1656
1657	Here r is the resultant of a and b; if r != 0, then this
1658	function computes s and t such that: as + bt = r; otherwise
1659	s and t are both 0.
1660
1661	EXAMPLES:
1662	sage: ntl.set_modulus(ntl.ZZ(17))
1663	sage: f = ntl.ZZ_pX([1,2,3]) * ntl.ZZ_pX([4,5])**2
1664	sage: g = ntl.ZZ_pX([1,1,1])*3 ntl.ZZ_pX([1,2,3])
1665	sage: f.xgcd(g) # nothing since they are not coprime
1666	([6 12 1], [15 13 6 8 7 9], [4 13])
1667
1668	In this example the input quadratic polynomials have a common root modulo 13.
1669	sage: f = ntl.ZZ_pX([5,0,1])
1670	sage: g = ntl.ZZ_pX([18,0,1])
1671	sage: f.xgcd(g)
1672	([1], [13], [4])
1673	"""
1674	cdef ZZ_pX s, t, *r
1675	_sig_on
1676	if plain:
1677	ZZ_pX_plain_xgcd(&r, &s, &t, self.x, other.x)
1678	else:
1679	ZZ_pX_xgcd(&r, &s, &t, self.x, other.x)
1680	return (make_ZZ_pX(r), make_ZZ_pX(s), make_ZZ_pX(t))
1681
1682	def degree(self):
1683	"""
1684	Return the degree of this polynomial. The degree of the 0
1685	polynomial is -1.
1686
1687	EXAMPLES:
1688	sage: ntl.set_modulus(ntl.ZZ(20))
1689	sage: f = ntl.ZZ_pX([5,0,1])
1690	sage: f.degree()
1691	2
1692	sage: f = ntl.ZZ_pX(range(100))
1693	sage: f.degree()
1694	99
1695	sage: f = ntl.ZZ_pX()
1696	sage: f.degree()
1697	-1
1698	sage: f = ntl.ZZ_pX([1])
1699	sage: f.degree()
1700	0
1701	"""
1702	return ZZ_pX_degree(self.x)
1703
1704	def leading_coefficient(self):
1705	"""
1706	Return the leading coefficient of this polynomial.
1707
1708	EXAMPLES:
1709	sage: ntl.set_modulus(ntl.ZZ(20))
1710	sage: f = ntl.ZZ_pX([3,6,9])
1711	sage: f.leading_coefficient()
1712	9
1713	sage: f = ntl.ZZ_pX()
1714	sage: f.leading_coefficient()
1715	0
1716	"""
1717	return make_ZZ_p(ZZ_pX_leading_coefficient(self.x))
1718
1719	def constant_term(self):
1720	"""
1721	Return the constant coefficient of this polynomial.
1722
1723	EXAMPLES:
1724	sage: ntl.set_modulus(ntl.ZZ(20))
1725	sage: f = ntl.ZZ_pX([3,6,9])
1726	sage: f.constant_term()
1727	3
1728	sage: f = ntl.ZZ_pX()
1729	sage: f.constant_term()
1730	0
1731	"""
1732	cdef char* t
1733	t = ZZ_pX_constant_term(self.x)
1734	return int(string(t))
1735
1736	def set_x(self):
1737	"""
1738	Set this polynomial to the monomial "x".
1739
1740	EXAMPLES:
1741	sage: ntl.set_modulus(ntl.ZZ(20))
1742	sage: f = ntl.ZZ_pX()
1743	sage: f.set_x()
1744	sage: f
1745	[0 1]
1746	sage: g = ntl.ZZ_pX([0,1])
1747	sage: f == g
1748	True
1749
1750	Though f and g are equal, they are not the same objects in memory:
1751	sage: f is g
1752	False
1753
1754	"""
1755	ZZ_pX_set_x(self.x)
1756
1757	def is_x(self):
1758	"""
1759	True if this is the polynomial "x".
1760
1761	EXAMPLES:
1762	sage: ntl.set_modulus(ntl.ZZ(20))
1763	sage: f = ntl.ZZ_pX()
1764	sage: f.set_x()
1765	sage: f.is_x()
1766	True
1767	sage: f = ntl.ZZ_pX([0,1])
1768	sage: f.is_x()
1769	True
1770	sage: f = ntl.ZZ_pX([1])
1771	sage: f.is_x()
1772	False
1773	"""
1774	return bool(ZZ_pX_is_x(self.x))
1775
1776	def derivative(self):
1777	"""
1778	Return the derivative of this polynomial.
1779
1780	EXAMPLES:
1781	sage: ntl.set_modulus(ntl.ZZ(20))
1782	sage: f = ntl.ZZ_pX([1,7,0,13])
1783	sage: f.derivative()
1784	[7 0 19]
1785	"""
1786	return make_ZZ_pX(ZZ_pX_derivative(self.x))
1787
1788	def factor(self, verbose=False):
1789	cdef ZZ_pX** v
1790	cdef long* e
1791	cdef long i, n
1792	_sig_on
1793	ZZ_pX_factor(&v, &e, &n, self.x, verbose)
1794	_sig_off
1795	F = []
1796	for i from 0 <= i < n:
1797	F.append((make_ZZ_pX(v[i]), e[i]))
1798	free(v)
1799	free(e)
1800	return F
1801
1802	def linear_roots(self):
1803	"""
1804	Assumes that input is monic, and has deg(f) distinct roots.
1805	Returns the list of roots.
1806	"""
1807	cdef ZZ_p** v
1808	cdef long i, n
1809	_sig_on
1810	ZZ_pX_linear_roots(&v, &n, self.x)
1811	_sig_off
1812	F = []
1813	for i from 0 <= i < n:
1814	F.append(make_ZZ_p(v[i]))
1815	free(v)
1816	return F
1817
1818	def reverse(self, hi=None):
1819	"""
1820	Return the polynomial obtained by reversing the coefficients
1821	of this polynomial. If hi is set then this function behaves
1822	as if this polynomial has degree hi.
1823
1824	EXAMPLES:
1825	sage: ntl.set_modulus(ntl.ZZ(20))
1826	sage: f = ntl.ZZ_pX([1,2,3,4,5])
1827	sage: f.reverse()
1828	[5 4 3 2 1]
1829	sage: f.reverse(hi=10)
1830	[0 0 0 0 0 0 5 4 3 2 1]
1831	sage: f.reverse(hi=2)
1832	[3 2 1]
1833	sage: f.reverse(hi=-2)
1834	[]
1835	"""
1836	if not (hi is None):
1837	return make_ZZ_pX(ZZ_pX_reverse_hi(self.x, int(hi)))
1838	else:
1839	return make_ZZ_pX(ZZ_pX_reverse(self.x))
1840
1841	def truncate(self, long m):
1842	"""
1843	Return the truncation of this polynomial obtained by
1844	removing all terms of degree >= m.
1845
1846	EXAMPLES:
1847	sage: ntl.set_modulus(ntl.ZZ(20))
1848	sage: f = ntl.ZZ_pX([1,2,3,4,5])
1849	sage: f.truncate(3)
1850	[1 2 3]
1851	sage: f.truncate(8)
1852	[1 2 3 4 5]
1853	sage: f.truncate(1)
1854	[1]
1855	sage: f.truncate(0)
1856	[]
1857	sage: f.truncate(-1)
1858	[]
1859	sage: f.truncate(-5)
1860	[]
1861	"""
1862	if m <= 0:
1863	return make_new_ZZ_pX()
1864	return make_ZZ_pX(ZZ_pX_truncate(self.x, m))
1865
1866	def multiply_and_truncate(self, ntl_ZZ_pX other, long m):
1867	"""
1868	Return self*other but with terms of degree >= m removed.
1869
1870	EXAMPLES:
1871	sage: ntl.set_modulus(ntl.ZZ(20))
1872	sage: f = ntl.ZZ_pX([1,2,3,4,5])
1873	sage: g = ntl.ZZ_pX([10])
1874	sage: f.multiply_and_truncate(g, 2)
1875	[10]
1876	sage: g.multiply_and_truncate(f, 2)
1877	[10]
1878	"""
1879	if m <= 0:
1880	return make_new_ZZ_pX()
1881	return make_ZZ_pX(ZZ_pX_multiply_and_truncate(self.x, other.x, m))
1882
1883	def square_and_truncate(self, long m):
1884	"""
1885	Return self*self but with terms of degree >= m removed.
1886
1887	EXAMPLES:
1888	sage: ntl.set_modulus(ntl.ZZ(20))
1889	sage: f = ntl.ZZ_pX([1,2,3,4,5])
1890	sage: f.square_and_truncate(4)
1891	[1 4 10]
1892	sage: (f*f).truncate(4)
1893	[1 4 10]
1894	"""
1895	if m < 0:
1896	return make_new_ZZ_pX()
1897	return make_ZZ_pX(ZZ_pX_square_and_truncate(self.x, m))
1898
1899	def invert_and_truncate(self, long m):
1900	"""
1901	Compute and return the inverse of self modulo $x^m$.
1902	The constant term of self must be 1 or -1.
1903
1904	EXAMPLES:
1905	sage: ntl.set_modulus(ntl.ZZ(20))
1906	sage: f = ntl.ZZ_pX([1,2,3,4,5,6,7])
1907	sage: f.invert_and_truncate(20)
1908	[1 18 1 0 0 0 0 8 17 2 13 0 0 0 4 0 17 10 9]
1909	sage: g = f.invert_and_truncate(20)
1910	sage: g * f
1911	[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 4 4 3]
1912	"""
1913	if m < 0:
1914	raise ArithmeticError, "m (=%s) must be positive"%m
1915	n = self.constant_term()
1916	if n != 1 and n != -1:
1917	raise ArithmeticError, \
1918	"The constant term of self must be 1 or -1."
1919	_sig_on
1920	return make_ZZ_pX(ZZ_pX_invert_and_truncate(self.x, m))
1921
1922	def multiply_mod(self, ntl_ZZ_pX other, ntl_ZZ_pX modulus):
1923	"""
1924	Return self*other % modulus. The modulus must be monic with
1925	deg(modulus) > 0, and self and other must have smaller degree.
1926
1927	EXAMPLES:
1928	sage: ntl.set_modulus(ntl.ZZ(20))
1929	sage: modulus = ntl.ZZ_pX([1,2,0,1]) # must be monic
1930	sage: g = ntl.ZZ_pX([-1,0,1])
1931	sage: h = ntl.ZZ_pX([3,7,13])
1932	sage: h.multiply_mod(g, modulus)
1933	[10 6 4]
1934	"""
1935	_sig_on
1936	return make_ZZ_pX(ZZ_pX_multiply_mod(self.x, other.x, modulus.x))
1937
1938	def trace_mod(self, ntl_ZZ_pX modulus):
1939	"""
1940	Return the trace of this polynomial modulus the modulus.
1941	The modulus must be monic, and of positive degree degree bigger
1942	than the the degree of self.
1943
1944	EXAMPLES:
1945	sage: ntl.set_modulus(ntl.ZZ(20))
1946	sage: f = ntl.ZZ_pX([1,2,0,3])
1947	sage: mod = ntl.ZZ_pX([5,3,-1,1,1])
1948	sage: f.trace_mod(mod)
1949	3
1950	"""
1951	_sig_on
1952	return make_ZZ_p(ZZ_pX_trace_mod(self.x, modulus.x))
1953
1954	def trace_list(self):
1955	"""
1956	Return the list of traces of the powers $x^i$ of the
1957	monomial x modulo this polynomial for i = 0, ..., deg(f)-1.
1958	This polynomial must be monic.
1959
1960	EXAMPLES:
1961	sage: ntl.set_modulus(ntl.ZZ(20))
1962	sage: f = ntl.ZZ_pX([1,2,0,3,0,1])
1963	sage: f.trace_list()
1964	[5, 0, 14, 0, 10]
1965
1966	The input polynomial must be monic or a ValueError is raised:
1967	sage: ntl.set_modulus(ntl.ZZ(20))
1968	sage: f = ntl.ZZ_pX([1,2,0,3,0,2])
1969	sage: f.trace_list()
1970	Traceback (most recent call last):
1971	...
1972	ValueError: polynomial must be monic.
1973	"""
1974	if not self.is_monic():
1975	raise ValueError, "polynomial must be monic."
1976	_sig_on
1977	cdef char* t
1978	t = ZZ_pX_trace_list(self.x)
1979	return eval(string(t).replace(' ', ','))
1980
1981	def resultant(self, ntl_ZZ_pX other):
1982	"""
1983	Return the resultant of self and other.
1984
1985	EXAMPLES:
1986	sage: ntl.set_modulus(ntl.ZZ(17))
1987	sage: f = ntl.ZZ_pX([17,0,1,1])
1988	sage: g = ntl.ZZ_pX([34,-17,18,2])
1989	sage: f.resultant(g)
1990	0
1991	"""
1992	_sig_on
1993	return make_ZZ_p(ZZ_pX_resultant(self.x, other.x))
1994
1995	def norm_mod(self, ntl_ZZ_pX modulus):
1996	"""
1997	Return the norm of this polynomial modulo the modulus. The
1998	modulus must be monic, and of positive degree strictly greater
1999	than the degree of self.
2000
2001
2002	EXAMPLE:
2003	sage: ntl.set_modulus(ntl.ZZ(17))
2004	sage: f = ntl.ZZ_pX([1,2,0,3])
2005	sage: mod = ntl.ZZ_pX([-5,2,0,0,1])
2006	sage: f.norm_mod(mod)
2007	11
2008
2009	The norm is the constant term of the characteristic polynomial.
2010	sage: f.charpoly_mod(mod)
2011	[11 1 8 14 1]
2012	"""
2013	_sig_on
2014	return make_ZZ_p(ZZ_pX_norm_mod(self.x, modulus.x))
2015
2016	def discriminant(self):
2017	r"""
2018	Return the discriminant of a=self, which is by definition
2019	$$
2020	(-1)^{m(m-1)/2} {\mbox{\tt resultant}}(a, a')/lc(a),
2021	$$
2022	where m = deg(a), and lc(a) is the leading coefficient of a.
2023
2024	EXAMPLES:
2025	sage: ntl.set_modulus(ntl.ZZ(17))
2026	sage: f = ntl.ZZ_pX([1,2,0,3])
2027	sage: f.discriminant()
2028	1
2029	"""
2030	cdef long m
2031
2032	c = ~self.leading_coefficient()
2033	m = self.degree()
2034	if (m*(m-1)/2) % 2:
2035	c = -c
2036	return c*self.resultant(self.derivative())
2037
2038	def charpoly_mod(self, ntl_ZZ_pX modulus):
2039	"""
2040	Return the characteristic polynomial of this polynomial modulo
2041	the modulus. The modulus must be monic of degree bigger than
2042	self.
2043
2044	EXAMPLES:
2045	sage: ntl.set_modulus(ntl.ZZ(17))
2046	sage: f = ntl.ZZ_pX([1,2,0,3])
2047	sage: mod = ntl.ZZ_pX([-5,2,0,0,1])
2048	sage: f.charpoly_mod(mod)
2049	[11 1 8 14 1]
2050	"""
2051	_sig_on
2052	return make_ZZ_pX(ZZ_pX_charpoly_mod(self.x, modulus.x))
2053
2054	def minpoly_mod(self, ntl_ZZ_pX modulus):
2055	"""
2056	Return the minimal polynomial of this polynomial modulo the
2057	modulus. The modulus must be monic of degree bigger than
2058	self.
2059
2060	EXAMPLES:
2061	sage: ntl.set_modulus(ntl.ZZ(17))
2062	sage: f = ntl.ZZ_pX([0,0,1])
2063	sage: g = f*f
2064	sage: f.charpoly_mod(g)
2065	[0 0 0 0 1]
2066
2067	However, since $f^2 = 0$ moduluo $g$, its minimal polynomial
2068	is of degree $2$.
2069	sage: f.minpoly_mod(g)
2070	[0 0 1]
2071	"""
2072	_sig_on
2073	return make_ZZ_pX(ZZ_pX_minpoly_mod(self.x, modulus.x))
2074
2075	def clear(self):
2076	"""
2077	Reset this polynomial to 0. Changes this polynomial in place.
2078
2079	EXAMPLES:
2080	sage: ntl.set_modulus(ntl.ZZ(17))
2081	sage: f = ntl.ZZ_pX([1,2,3])
2082	sage: f
2083	[1 2 3]
2084	sage: f.clear()
2085	sage: f
2086	[]
2087	"""
2088	ZZ_pX_clear(self.x)
2089
2090	def preallocate_space(self, long n):
2091	"""
2092	Pre-allocate spaces for n coefficients. The polynomial that f
2093	represents is unchanged. This is useful if you know you'll be
2094	setting coefficients up to n, so memory isn't re-allocated as
2095	the polynomial grows. (You might save a millisecond with this
2096	function.)
2097
2098	EXAMPLES:
2099	sage: ntl.set_modulus(ntl.ZZ(17))
2100	sage: f = ntl.ZZ_pX([1,2,3])
2101	sage: f.preallocate_space(20)
2102	sage: f
2103	[1 2 3]
2104	sage: f[10]=5 # no new memory is allocated
2105	sage: f
2106	[1 2 3 0 0 0 0 0 0 0 5]
2107	"""
2108	_sig_on
2109	ZZ_pX_preallocate_space(self.x, n)
2110	_sig_off
2111
2112
2113	## TODO: NTL's ZZ_pX has minpolys of linear recurrence sequences!!!
2114
2115
2116	cdef make_ZZ_pX(ZZ_pX* x):
2117	cdef ntl_ZZ_pX y
2118	_sig_off
2119	y = ntl_ZZ_pX()
2120	y.x = x
2121	return y
2122
2123	def make_new_ZZ_pX(v=[]):
2124	s = str(v).replace(',',' ').replace('L','')
2125	cdef ntl_ZZ_pX z
2126	z = ntl_ZZ_pX()
2127	_sig_on
2128	z.x = str_to_ZZ_pX(s)
2129	_sig_off
2130	return z
2131
2132
2133	##############################################################################
2134	#
2135	# ntl_mat_ZZ: Matrices over the integers via NTL
2136	#
2137	##############################################################################
2138
2139	cdef class ntl_mat_ZZ:
2140	# see ntl.pxd for data members
2141	r"""
2142	The \class{mat_ZZ} class implements arithmetic with matrices over $\Z$.
2143	"""
2144	def __init__(self, nrows=0, ncols=0, v=None):
2145	if nrows == _INIT:
2146	return
2147	cdef unsigned long i, j
2148	cdef ntl_ZZ tmp
2149	if nrows == 0 and ncols == 0:
2150	return
2151	nrows = int(nrows)
2152	ncols = int(ncols)
2153	self.x = new_mat_ZZ(nrows, ncols)
2154	self.__nrows = nrows
2155	self.__ncols = ncols
2156	if v != None:
2157	for i from 0 <= i < nrows:
2158	for j from 0 <= j < ncols:
2159	tmp = make_new_ZZ(v[i*ncols+j])
2160	mat_ZZ_setitem(self.x, i, j, <ZZ*> tmp.x)
2161
2162
2163	def __reduce__(self):
2164	raise NotImplementedError
2165
2166	def __dealloc__(self):
2167	del_mat_ZZ(self.x)
2168
2169	def __repr__(self):
2170	_sig_on
2171	return string(mat_ZZ_to_str(self.x))
2172
2173	def __mul__(ntl_mat_ZZ self, other):
2174	cdef ntl_mat_ZZ y
2175	if not isinstance(other, ntl_mat_ZZ):
2176	other = ntl_mat_ZZ(other)
2177	y = other
2178	_sig_on
2179	return make_mat_ZZ(mat_ZZ_mul(self.x, y.x))
2180
2181	def __sub__(ntl_mat_ZZ self, other):
2182	cdef ntl_mat_ZZ y
2183	if not isinstance(other, ntl_mat_ZZ):
2184	other = ntl_mat_ZZ(other)
2185	y = other
2186	_sig_on
2187	return make_mat_ZZ(mat_ZZ_sub(self.x, y.x))
2188
2189	def __add__(ntl_mat_ZZ self, other):
2190	cdef ntl_mat_ZZ y
2191	if not isinstance(other, ntl_mat_ZZ):
2192	other = ntl_mat_ZZ(other)
2193	y = other
2194	_sig_on
2195	return make_mat_ZZ(mat_ZZ_add(self.x, y.x))
2196
2197	def __pow__(ntl_mat_ZZ self, long e, ignored):
2198	_sig_on
2199	return make_mat_ZZ(mat_ZZ_pow(self.x, e))
2200
2201	def nrows(self):
2202	return self.__nrows
2203
2204	def ncols(self):
2205	return self.__ncols
2206
2207	def __setitem__(self, ij, x):
2208	cdef ntl_ZZ y
2209	cdef int i, j
2210	if not isinstance(x, ntl_ZZ):
2211	y = make_new_ZZ(x)
2212	else:
2213	y = x
2214	if not isinstance(ij, tuple) or len(ij) != 2:
2215	raise TypeError, 'ij must be a 2-tuple'
2216	i, j = int(ij[0]),int(ij[1])
2217	if i < 0 or i >= self.__nrows or j < 0 or j >= self.__ncols:
2218	raise IndexError, "array index out of range"
2219	_sig_on
2220	mat_ZZ_setitem(self.x, i, j, <ZZ*> y.x)
2221	_sig_off
2222
2223	def __getitem__(self, ij):
2224	cdef int i, j
2225	if not isinstance(ij, tuple) or len(ij) != 2:
2226	raise TypeError, 'ij must be a 2-tuple'
2227	i, j = ij
2228	if i < 0 or i >= self.__nrows or j < 0 or j >= self.__ncols:
2229	raise IndexError, "array index out of range"
2230	return make_ZZ(mat_ZZ_getitem(self.x, i+1, j+1))
2231
2232	def determinant(self, deterministic=True):
2233	_sig_on
2234	return make_ZZ(mat_ZZ_determinant(self.x, deterministic))
2235
2236	def HNF(self, D=None):
2237	r"""
2238	The input matrix A=self is an n x m matrix of rank m (so n >=
2239	m), and D is a multiple of the determinant of the lattice L
2240	spanned by the rows of A. The output W is the Hermite Normal
2241	Form of A; that is, W is the unique m x m matrix whose rows
2242	span L, such that
2243
2244	- W is lower triangular,
2245	- the diagonal entries are positive,
2246	- any entry below the diagonal is a non-negative number
2247	strictly less than the diagonal entry in its column.
2248
2249	This is implemented using the algorithm of [P. Domich,
2250	R. Kannan and L. Trotter, Math. Oper. Research 12:50-59,
2251	1987].
2252
2253	TIMINGS:
2254	NTL isn't very good compared to MAGMA, unfortunately:
2255
2256	sage.: import ntl
2257	sage.: a=MatrixSpace(Q,200).random_element() # -2 to 2
2258	sage.: A=ntl.mat_ZZ(200,200)
2259	sage.: for i in xrange(a.nrows()):
2260	....: for j in xrange(a.ncols()):
2261	....: A[i,j] = a[i,j]
2262	....:
2263	sage.: time d=A.determinant()
2264	Time.: 3.89 seconds
2265	sage.: time B=A.HNF(d)
2266	Time.: 27.59 seconds
2267
2268	In comparison, MAGMA does this much more quickly:
2269	\begin{verbatim}
2270	> A := MatrixAlgebra(Z,200)![Random(-2,2) : i in [1..200^2]];
2271	> time d := Determinant(A);
2272	Time: 0.710
2273	> time H := HermiteForm(A);
2274	Time: 3.080
2275	\end{verbatim}
2276
2277	Also, PARI is also faster than NTL if one uses the flag 1 to
2278	the mathnf routine. The above takes 16 seconds in PARI.
2279	"""
2280	cdef ntl_ZZ _D
2281	if D == None:
2282	_D = self.determinant()
2283	else:
2284	_D = ntl_ZZ(D)
2285	_sig_on
2286	return make_mat_ZZ(mat_ZZ_HNF(self.x, <ZZ*>_D.x))
2287
2288	def charpoly(self):
2289	return make_ZZX(mat_ZZ_charpoly(self.x));
2290
2291	def LLL(self, a=3, b=4, return_U=False, verbose=False):
2292	r"""
2293	Performs LLL reduction of self (puts self in an LLL form).
2294
2295	self is an m x n matrix, viewed as m rows of n-vectors. m may
2296	be less than, equal to, or greater than n, and the rows need
2297	not be linearly independent. self is transformed into an
2298	LLL-reduced basis, and the return value is the rank r of self
2299	so as det2 (see below). The first m-r rows of self are zero.
2300
2301	More specifically, elementary row transformations are
2302	performed on self so that the non-zero rows of new-self form
2303	an LLL-reduced basis for the lattice spanned by the rows of
2304	old-self. The default reduction parameter is $\delta=3/4$,
2305	which means that the squared length of the first non-zero
2306	basis vector is no more than $2^{r-1}$ times that of the
2307	shortest vector in the lattice.
2308
2309	det2 is calculated as the \emph{square} of the determinant of
2310	the lattice---note that sqrt(det2) is in general an integer
2311	only when r = n.
2312
2313	If return_U is True, a value U is returned which is the
2314	transformation matrix, so that U is a unimodular m x m matrix
2315	with U * old-self = new-self. Note that the first m-r rows of
2316	U form a basis (as a lattice) for the kernel of old-B.
2317
2318	The parameters a and b allow an arbitrary reduction parameter
2319	$\delta=a/b$, where $1/4 < a/b \leq 1$, where a and b are positive
2320	integers. For a basis reduced with parameter delta, the
2321	squared length of the first non-zero basis vector is no more
2322	than $1/(delta-1/4)^{r-1}$ times that of the shortest vector in
2323	the lattice.
2324
2325	The algorithm employed here is essentially the one in Cohen's
2326	book: [H. Cohen, A Course in Computational Algebraic Number
2327	Theory, Springer, 1993]
2328
2329	INPUT:
2330	a -- parameter a as described above (default: 3)
2331	b -- parameter b as described above (default: 4)
2332	return_U -- return U as described above
2333	verbose -- if True NTL will produce some verbatim messages on
2334	what's going on internally (default: False)
2335
2336	OUTPUT:
2337	(rank,det2,[U]) where rank,det2, and U are as described
2338	above and U is an optional return value if return_U is
2339	True.
2340
2341	EXAMPLE:
2342	sage: M=ntl.mat_ZZ(3,3,[1,2,3,4,5,6,7,8,9])
2343	sage: M.LLL()
2344	(2, 54)
2345	sage: M
2346	[[0 0 0]
2347	[2 1 0]
2348	[-1 1 3]
2349	]
2350	sage: M=ntl.mat_ZZ(4,4,[-6,9,-15,-18,4,-6,10,12,10,-16,18,35,-24,36,-46,-82]); M
2351	[[-6 9 -15 -18]
2352	[4 -6 10 12]
2353	[10 -16 18 35]
2354	[-24 36 -46 -82]
2355	]
2356	sage: M.LLL()
2357	(3, 19140)
2358	sage: M
2359	[[0 0 0 0]
2360	[0 -2 0 0]
2361	[-2 1 -5 -6]
2362	[0 -1 -7 5]
2363	]
2364
2365	WARNING: This method modifies self. So after applying this method your matrix
2366	will be a vector of vectors.
2367	"""
2368	cdef ZZ *det2
2369	cdef mat_ZZ *U
2370	if return_U:
2371	_sig_on
2372	U = new_mat_ZZ(self.nrows(),self.ncols())
2373	rank = int(mat_ZZ_LLL_U(&det2, self.x, U, int(a), int(b), int(verbose)))
2374	_sig_off
2375	return rank, make_ZZ(det2), make_mat_ZZ(U)
2376	else:
2377	_sig_on
2378	rank = int(mat_ZZ_LLL(&det2,self.x,int(a),int(b),int(verbose)))
2379	_sig_off
2380	return rank,make_ZZ(det2)
2381
2382	cdef make_mat_ZZ(mat_ZZ* x):
2383	cdef ntl_mat_ZZ y
2384	_sig_off
2385	y = ntl_mat_ZZ(_INIT)
2386	y.x = x
2387	y.__nrows = mat_ZZ_nrows(y.x);
2388	y.__ncols = mat_ZZ_ncols(y.x);
2389	return y
2390
2391
2392	##############################################################################
2393	#
2394	# ntl_GF2X: Polynomials over GF(2) via NTL
2395	#
2396	# AUTHORS:
2397	# - Martin Albrecht <malb@informatik.uni-bremen.de>
2398	# 2006-01: initial version (based on code by William Stein)
2399	#
2400	##############################################################################
2401
2402	__have_GF2X_hex_repr = False # hex representation of GF2X
2403
2404
2405	cdef class ntl_GF2X:
2406	"""
2407	Polynomials over GF(2) via NTL
2408	"""
2409	# See ntl.pxd for definition of data members
2410
2411	def __reduce__(self):
2412	raise NotImplementedError
2413
2414	def __dealloc__(self):
2415	del_GF2X(self.gf2x_x)
2416
2417	def __repr__(self):
2418	_sig_on
2419	return string(GF2X_to_str(self.gf2x_x))
2420
2421
2422	def __mul__(ntl_GF2X self, other):
2423	cdef ntl_GF2X y
2424	if not isinstance(other, ntl_GF2X):
2425	other = ntl_GF2X(other)
2426	y = other
2427	_sig_on
2428	return make_GF2X(GF2X_mul(self.gf2x_x, y.gf2x_x))
2429
2430	def __sub__(ntl_GF2X self, other):
2431	cdef ntl_GF2X y
2432	if not isinstance(other, ntl_GF2X):
2433	other = ntl_GF2X(other)
2434	y = other
2435	_sig_on
2436	return make_GF2X(GF2X_sub(self.gf2x_x, y.gf2x_x))
2437
2438	def __add__(ntl_GF2X self, other):
2439	cdef ntl_GF2X y
2440	if not isinstance(other, ntl_GF2X):
2441	other = ntl_GF2X(other)
2442	y = other
2443	_sig_on
2444	return make_GF2X(GF2X_add(self.gf2x_x, y.gf2x_x))
2445
2446	def __neg__(ntl_GF2X self):
2447	_sig_on
2448	return make_GF2X(GF2X_neg(self.gf2x_x))
2449
2450	def __pow__(ntl_GF2X self, long e, ignored):
2451	_sig_on
2452	return make_GF2X(GF2X_pow(self.gf2x_x, e))
2453
2454
2455	def __cmp__(ntl_GF2X self, ntl_GF2X other):
2456	cdef int t
2457	_sig_on
2458	t = GF2X_eq(self.gf2x_x, other.gf2x_x)
2459	_sig_off
2460	if t:
2461	return 0
2462	return 1
2463
2464	def degree(ntl_GF2X self):
2465	"""
2466	Returns the degree of this polynomial
2467	"""
2468	return GF2X_deg(self.gf2x_x)
2469
2470	def list(ntl_GF2X self):
2471	"""
2472	Represents this element as a list of binary digits.
2473
2474	EXAMPLES:
2475	sage: e=ntl.GF2X([0,1,1])
2476	sage: e.list()
2477	[0, 1, 1]
2478	sage: e=ntl.GF2X('0xff')
2479	sage: e.list()
2480	[1, 1, 1, 1, 1, 1, 1, 1]
2481
2482	OUTPUT:
2483	a list of digits representing the coefficients in this element's
2484	polynomial representation
2485	"""
2486	#yields e.g. "[1 1 0 0 1 1 0 1]"
2487	_sig_on
2488	s = string(GF2X_to_bin(self.gf2x_x))
2489
2490	#yields e.g. [1,1,0,0,1,1,0,1]
2491	return map(int,list(s[1:][:len(s)-2].replace(" ","")))
2492
2493
2494	def bin(ntl_GF2X self):
2495	"""
2496	Returns binary representation of this element. It is
2497	the same as setting \code{ntl.hex_output(False)} and
2498	representing this element afterwards. However it should be
2499	faster and preserves the HexOutput state as opposed to
2500	the above code.
2501
2502	EXAMPLES:
2503	sage: e=ntl.GF2X([1,1,0,1,1,1,0,0,1])
2504	sage: e.bin()
2505	'[1 1 0 1 1 1 0 0 1]'
2506
2507	OUTPUT:
2508	string representing this element in binary digits
2509
2510	"""
2511	_sig_on
2512	return string(GF2X_to_bin(self.gf2x_x))
2513
2514	def hex(ntl_GF2X self):
2515	"""
2516	Returns hexadecimal representation of this element. It is
2517	the same as setting \code{ntl.hex_output(True)} and
2518	representing this element afterwards. However it should be
2519	faster and preserves the HexOutput state as opposed to
2520	the above code.
2521
2522	EXAMPLES:
2523	sage: e=ntl.GF2X([1,1,0,1,1,1,0,0,1])
2524	sage: e.hex()
2525	'0xb31'
2526
2527	OUTPUT:
2528	string representing this element in hexadecimal
2529
2530	"""
2531	_sig_on
2532	return string(GF2X_to_hex(self.gf2x_x))
2533
2534	def _sage_(ntl_GF2X self,R=None,cache=None):
2535	"""
2536	Returns a SAGE polynomial over GF(2) equivalent to
2537	this element. If a ring R is provided it is used
2538	to construct the polynomial in, otherwise
2539	an appropriate ring is generated.
2540
2541	INPUT:
2542	self -- GF2X element
2543	R -- PolynomialRing over GF(2)
2544	cache -- optional NTL to SAGE cache (dict)
2545
2546	OUTPUT:
2547	polynomial in R
2548	"""
2549	if R==None:
2550	from sage.rings.polynomial_ring import PolynomialRing
2551	from sage.rings.finite_field import FiniteField
2552	R = PolynomialRing(FiniteField(2), 'x')
2553
2554	if cache != None:
2555	try:
2556	return cache[self.hex()]
2557	except KeyError:
2558	cache[self.hex()] = R(self.list())
2559	return cache[self.hex()]
2560
2561	return R(self.list())
2562
2563	cdef set(self, void *y): # only used internally for initialization; assumes self.gf2x_x not set yet!
2564	self.gf2x_x = <GF2X*> y
2565
2566	cdef public make_GF2X(GF2X* x):
2567	cdef ntl_GF2X y
2568	_sig_off
2569	y = ntl_GF2X()
2570	y.gf2x_x = x
2571	return y
2572
2573	def make_new_GF2X(x=[]):
2574	"""
2575	Constructs a new polynomial over GF(2).
2576
2577	A value may be passed to this constructor. If you pass a string
2578	to the constructor please note that byte sequences and the hexadecimal
2579	notation are little endian. So e.g. '[0 1]' == '0x2' == x.
2580
2581	Input types are ntl.ZZ_px, strings, lists of digits, FiniteFieldElements
2582	from extension fields over GF(2), Polynomials over GF(2), Integers, and finite
2583	extension fields over GF(2) (uses modulus).
2584
2585	INPUT:
2586	x -- value to be assigned to this element. See examples.
2587
2588	OUTPUT:
2589	a new ntl.GF2X element
2590
2591	EXAMPLES:
2592	sage: ntl.GF2X(ntl.ZZ_pX([1,1,3]))
2593	[1 1 1]
2594	sage: ntl.GF2X('0x1c')
2595	[1 0 0 0 0 0 1 1]
2596	sage: ntl.GF2X('[1 0 1 0]')
2597	[1 0 1]
2598	sage: ntl.GF2X([1,0,1,0])
2599	[1 0 1]
2600	sage: ntl.GF2X(GF(28,'a').gen()20)
2601	[0 0 1 0 1 1 0 1]
2602	sage: ntl.GF2X(GF(2**8,'a'))
2603	[1 0 1 1 1 0 0 0 1]
2604	sage: ntl.GF2X(2)
2605	[0 1]
2606	"""
2607	from sage.rings.finite_field_element import FiniteField_ext_pariElement
2608	from sage.rings.finite_field import FiniteField_ext_pari
2609	from sage.rings.finite_field_givaro import FiniteField_givaro,FiniteField_givaroElement
2610	from sage.rings.polynomial_element_generic import Polynomial_dense_mod_p
2611	from sage.rings.integer import Integer
2612
2613	if isinstance(x, Integer):
2614	#binary repr, reversed, and "["..."]" added
2615	x="["+x.binary()[::-1].replace(""," ")+"]"
2616	elif type(x) == int:
2617	#hex repr, "0x" stripped, reversed (!)
2618	x="0x"+hex(x)[2:][::-1]
2619	elif isinstance(x, Polynomial_dense_mod_p):
2620	if x.base_ring().characteristic():
2621	x=x._Polynomial_dense_mod_n__poly
2622	elif isinstance(x, (FiniteField_ext_pari,FiniteField_givaro)):
2623	if x.characteristic() == 2:
2624	x= list(x.modulus())
2625	elif isinstance(x, FiniteField_ext_pariElement):
2626	if x.parent().characteristic() == 2:
2627	x=x._pari_().centerlift().centerlift().subst('a',2).int_unsafe()
2628	x="0x"+hex(x)[2:][::-1]
2629	elif isinstance(x, FiniteField_givaroElement):
2630	x = "0x"+hex(int(x))[2:][::-1]
2631	s = str(x).replace(","," ")
2632	cdef ntl_GF2X n
2633	n = ntl_GF2X()
2634	_sig_on
2635	n.gf2x_x = str_to_GF2X(s)
2636	_sig_off
2637	return n
2638
2639
2640
2641	##############################################################################
2642	#
2643	# ntl_GF2E: GF(2**x) via NTL
2644	#
2645	# AUTHORS:
2646	# - Martin Albrecht <malb@informatik.uni-bremen.de>
2647	# 2006-01: initial version (based on cody by William Stein)
2648	#
2649	##############################################################################
2650
2651	def GF2X_hex_repr(have_hex=None):
2652	"""
2653	Represent GF2X and GF2E elements in the more compact
2654	hexadecimal form to the user.
2655
2656	If no parameter is provided the currently set value will be
2657	returned.
2658
2659	INPUT:
2660	have_hex if True hex representation will be used
2661	"""
2662	global __have_GF2X_hex_repr
2663
2664	if have_hex==None:
2665	return __have_GF2X_hex_repr
2666
2667	if have_hex==True:
2668	GF2X_hex(1)
2669	else:
2670	GF2X_hex(0)
2671	__have_GF2X_hex_repr=have_hex
2672
2673	def ntl_GF2E_modulus(p=None):
2674	"""
2675	Initializes the current modulus to P; required: deg(P) >= 1
2676
2677	The input is either ntl.GF2X or is tried to be converted to a
2678	ntl.GF2X element.
2679
2680	If no parameter p is given: Yields copy of the current GF2E
2681	modulus.
2682
2683	INPUT:
2684	p -- modulus
2685
2686	EXAMPLES:
2687	sage: ntl.GF2E_modulus([1,1,0,1,1,0,0,0,1])
2688	sage: ntl.GF2E_modulus().hex()
2689	'0xb11'
2690	"""
2691	global __have_GF2E_modulus
2692	cdef ntl_GF2X elem
2693
2694	if p==None:
2695	if __have_GF2E_modulus == True:
2696	return make_GF2X(GF2E_modulus())
2697	else:
2698	raise "NoModulus"
2699
2700	if not isinstance(p,ntl_GF2X):
2701	elem = make_new_GF2X(p)
2702	else:
2703	elem = p
2704
2705	if(elem.degree()<1):
2706	raise "DegreeToSmall"
2707
2708	ntl_GF2E_set_modulus(<GF2X*>elem.gf2x_x)
2709	__have_GF2E_modulus=True
2710
2711	def ntl_GF2E_modulus_degree():
2712	"""
2713	Returns deg(modulus) for GF2E elements
2714	"""
2715	if __have_GF2E_modulus:
2716	return GF2E_degree()
2717	else:
2718	raise "NoModulus"
2719
2720	def ntl_GF2E_sage(names='a'):
2721	"""
2722	Returns a SAGE FiniteField element matching the current modulus.
2723
2724	EXAMPLES:
2725	sage: ntl.GF2E_modulus([1,1,0,1,1,0,0,0,1])
2726	sage: ntl.GF2E_sage()
2727	Finite Field in a of size 2^8
2728	"""
2729	from sage.rings.finite_field import FiniteField_ext_pari
2730	f = ntl_GF2E_modulus()._sage_()
2731	return FiniteField_ext_pari(int(2)**GF2E_degree(),modulus=f,name=names)
2732
2733
2734	def ntl_GF2E_random():
2735	"""
2736	Returns a random element from GF2E modulo the current modulus.
2737	"""
2738	_sig_on
2739	return make_GF2E(GF2E_random());
2740
2741
2742	# make sure not to segfault
2743	__have_GF2E_modulus = False
2744
2745
2746	cdef class ntl_GF2E(ntl_GF2X):
2747	r"""
2748	The \\class{GF2E} represents a finite extension field over GF(2) using NTL.
2749	Elements are represented as polynomials over GF(2) modulo \\code{ntl.GF2E_modulus()}.
2750
2751	This modulus must be set using \\code{ ntl.GF2E_modulus(p) } and is unique for
2752	alle elements in ntl.GF2E. So it is not possible at the moment e.g. to have elements
2753	in GF(24) and GF(28) at the same time. You might however be lucky and get away
2754	with not touch the elements in GF(24) while having the GF(28) modulus set and vice
2755	versa.
2756	"""
2757
2758	# See ntl.pxd for definition of data members
2759	def __reduce__(self):
2760	raise NotImplementedError
2761
2762	def __dealloc__(self):
2763	del_GF2E(self.gf2e_x)
2764
2765	def __repr__(self):
2766	_sig_on
2767	return string(GF2E_to_str(self.gf2e_x))
2768
2769
2770	def __mul__(ntl_GF2E self, other):
2771	cdef ntl_GF2E y
2772	if not isinstance(other, ntl_GF2E):
2773	other = ntl_GF2E(other)
2774	y = other
2775	_sig_on
2776	return make_GF2E(GF2E_mul(self.gf2e_x, y.gf2e_x))
2777
2778	def __sub__(ntl_GF2E self, other):
2779	cdef ntl_GF2E y
2780	if not isinstance(other, ntl_GF2E):
2781	other = ntl_GF2E(other)
2782	y = other
2783	_sig_on
2784	return make_GF2E(GF2E_sub(self.gf2e_x, y.gf2e_x))
2785
2786	def __add__(ntl_GF2E self, other):
2787	cdef ntl_GF2E y
2788	if not isinstance(other, ntl_GF2E):
2789	other = ntl_GF2E(other)
2790	y = other
2791	_sig_on
2792	return make_GF2E(GF2E_add(self.gf2e_x, y.gf2e_x))
2793
2794	def __neg__(ntl_GF2E self):
2795	_sig_on
2796	return make_GF2E(GF2E_neg(self.gf2e_x))
2797
2798	def __pow__(ntl_GF2E self, long e, ignored):
2799	_sig_on
2800	return make_GF2E(GF2E_pow(self.gf2e_x, e))
2801
2802	def __cmp__(ntl_GF2E self, ntl_GF2E other):
2803	cdef int t
2804	_sig_on
2805	t = GF2E_eq(self.gf2e_x, other.gf2e_x)
2806	_sig_off
2807	if t:
2808	return 0
2809	return 1
2810
2811	def is_zero(ntl_GF2E self):
2812	"""
2813	Returns True if this element equals zero, False otherwise.
2814	"""
2815	return bool(GF2E_is_zero(self.gf2e_x))
2816
2817	def is_one(ntl_GF2E self):
2818	"""
2819	Returns True if this element equals one, False otherwise.
2820	"""
2821	return bool(GF2E_is_one(self.gf2e_x))
2822
2823	def __copy__(self):
2824	return make_GF2E(GF2E_copy(self.gf2e_x))
2825
2826	def copy(ntl_GF2E self):
2827	"""
2828	Returns a copy of this element.
2829	"""
2830	return make_GF2E(GF2E_copy(self.gf2e_x))
2831
2832	def trace(ntl_GF2E self):
2833	"""
2834	Returns the trace of this element.
2835	"""
2836	return GF2E_trace(self.gf2e_x)
2837
2838	def ntl_GF2X(ntl_GF2E self):
2839	"""
2840	Returns a ntl.GF2X copy of this element.
2841	"""
2842	return make_GF2X(self.gf2x_x)
2843
2844
2845	def _sage_(ntl_GF2E self, k=None, cache=None):
2846	"""
2847	Returns a \class{FiniteFieldElement} representation
2848	of this element. If a \class{FiniteField} k is provided
2849	it is constructed in this field if possible. A \class{FiniteField}
2850	will be constructed if none is provided.
2851
2852	INPUT:
2853	self -- \class{GF2E} element
2854	k -- optional GF(2**deg)
2855	cache -- optional NTL to SAGE conversion dictionary
2856
2857	OUTPUT:
2858	FiniteFieldElement over k
2859	"""
2860	cdef int i
2861	cdef int length
2862	deg= GF2E_degree()
2863
2864	if k==None:
2865	from sage.rings.finite_field import FiniteField_ext_pari
2866	f = ntl_GF2E_modulus()._sage_()
2867	k = FiniteField_ext_pari(2**deg,modulus=f)
2868
2869	if cache != None:
2870	try:
2871	return cache[self.hex()]
2872	except KeyError:
2873	pass
2874
2875
2876
2877	a=k.gen()
2878	l = self.list()
2879
2880	length = len(l)
2881	ret = 0
2882
2883	for i from 0 <= i < length:
2884	if l[i]==1:
2885	ret = ret + a**i
2886
2887	if cache != None:
2888	cache[self.hex()] = ret
2889
2890	return ret
2891
2892
2893	cdef set(self, void *y): # only used internally for initialization; assumes self.gf2e_x not set yet!
2894	self.gf2e_x = <GF2E*> y
2895
2896	cdef public make_GF2E(GF2E* x):
2897	cdef ntl_GF2E y
2898	_sig_off
2899	y = ntl_GF2E()
2900	y.gf2e_x = x
2901	y.gf2x_x = GF2E_ntl_GF2X(y.gf2e_x)
2902	return y
2903
2904	def make_new_GF2E(x=[]):
2905	"""
2906	Constructs a new finite field element in GF(2**x).
2907
2908	A modulus \emph{must} have been set with \code{ntl.GF2E_modulus(ntl.GF2X(<value>))}
2909	when calling this constructor. A value may be passed to this constructor. If you pass a string
2910	to the constructor please note that byte sequences and the hexadecimal notation are Little Endian in NTL.
2911	So e.g. '[0 1]' == '0x2' == x.
2912
2913	INPUT:
2914	x -- value to be assigned to this element. Same types as ntl.GF2X() are accepted.
2915
2916	OUTPUT:
2917	a new ntl.GF2E element
2918
2919	EXAMPLES:
2920	sage: m=ntl.GF2E_modulus(ntl.GF2X([1,1,0,1,1,0,0,0,1]))
2921	sage: ntl.GF2E(ntl.ZZ_pX([1,1,3]))
2922	[1 1 1]
2923	sage: ntl.GF2E('0x1c')
2924	[1 0 0 0 0 0 1 1]
2925	sage: ntl.GF2E('[1 0 1 0]')
2926	[1 0 1]
2927	sage: ntl.GF2E([1,0,1,0])
2928	[1 0 1]
2929	sage: ntl.GF2E(GF(28,'a').gen()20)
2930	[0 0 1 0 1 1 0 1]
2931	"""
2932	if not __have_GF2E_modulus:
2933	raise "NoModulus"
2934
2935	s = str(make_new_GF2X(x))
2936	cdef ntl_GF2E n
2937	n = ntl_GF2E()
2938	_sig_on
2939	n.gf2e_x = str_to_GF2E(s)
2940	n.gf2x_x = GF2E_ntl_GF2X(n.gf2e_x)
2941	_sig_off
2942	return n
2943
2944
2945	##############################################################################
2946	#
2947	# ntl_GF2EX: Polynomials over GF(2) via NTL
2948	#
2949	# AUTHORS:
2950	# - Martin Albrecht <malb@informatik.uni-bremen.de> 2006-01: initial version
2951	#
2952	##############################################################################
2953
2954
2955	cdef class ntl_GF2EX:
2956	r"""
2957	"""
2958	# See ntl.pxd for definition of data members
2959
2960	def __reduce__(self):
2961	raise NotImplementedError
2962
2963	def __dealloc__(self):
2964	del_GF2EX(self.x)
2965
2966	def __repr__(self):
2967	_sig_on
2968	return string(GF2EX_to_str(self.x))
2969
2970
2971	def __mul__(ntl_GF2EX self, other):
2972	cdef ntl_GF2EX y
2973	if not isinstance(other, ntl_GF2EX):
2974	other = ntl_GF2EX(other)
2975	y = other
2976	_sig_on
2977	return make_GF2EX(GF2EX_mul(self.x, y.x))
2978
2979	def __sub__(ntl_GF2EX self, other):
2980	cdef ntl_GF2EX y
2981	if not isinstance(other, ntl_GF2EX):
2982	other = ntl_GF2EX(other)
2983	y = other
2984	_sig_on
2985	return make_GF2EX(GF2EX_sub(self.x, y.x))
2986
2987	def __add__(ntl_GF2EX self, other):
2988	cdef ntl_GF2EX y
2989	if not isinstance(other, ntl_GF2EX):
2990	other = ntl_GF2EX(other)
2991	y = other
2992	_sig_on
2993	return make_GF2EX(GF2EX_add(self.x, y.x))
2994
2995	def __neg__(ntl_GF2EX self):
2996	_sig_on
2997	return make_GF2EX(GF2EX_neg(self.x))
2998
2999	def __pow__(ntl_GF2EX self, long e, ignored):
3000	_sig_on
3001	return make_GF2EX(GF2EX_pow(self.x, e))
3002
3003	cdef set(self, void *y): # only used internally for initialization; assumes self.x not set yet!
3004	self.x = <GF2EX*> y
3005
3006	cdef public make_GF2EX(GF2EX* x):
3007	cdef ntl_GF2EX y
3008	_sig_off
3009	y = ntl_GF2EX()
3010	y.x = x
3011	return y
3012
3013	def make_new_GF2EX(x='[]'):
3014	s = str(x)
3015	cdef ntl_GF2EX n
3016	n = ntl_GF2EX()
3017	_sig_on
3018	n.x = str_to_GF2EX(s)
3019	_sig_off
3020	return n
3021
3022
3023	##############################################################################
3024	#
3025	# ntl_mat_GF2E: Matrices over the GF(2**x) via NTL
3026	#
3027	# AUTHORS:
3028	# - Martin Albrecht <malb@informatik.uni-bremen.de>
3029	# 2006-01: initial version (based on cody by William Stein)
3030	#
3031	##############################################################################
3032
3033
3034	cdef class ntl_mat_GF2E:
3035	r"""
3036	The \class{mat_GF2E} class implements arithmetic with matrices over $GF(2**x)$.
3037	"""
3038	def __init__(self, nrows=0, ncols=0, v=None):
3039	"""
3040	Constructs a matrix over ntl.GF2E.
3041
3042	INPUT:
3043	nrows -- number of rows
3044	ncols -- nomber of columns
3045	v -- either list or Matrix over GF(2**x)
3046
3047	EXAMPLES:
3048	sage: ntl.GF2E_modulus([1,1,0,1,1,0,0,0,1])
3049	sage: m=ntl.mat_GF2E(10,10)
3050	sage: m=ntl.mat_GF2E(Matrix(GF(2**8, 'a'),10,10))
3051	sage: m=ntl.mat_GF2E(10,10,[ntl.GF2E_random() for x in xrange(10*10)])
3052	"""
3053
3054	if nrows is _INIT:
3055	return
3056
3057	cdef unsigned long _nrows, _ncols
3058
3059	import sage.matrix.matrix
3060	if sage.matrix.matrix.is_Matrix(nrows):
3061	_nrows = nrows.nrows()
3062	_ncols = nrows.ncols()
3063	v = nrows.list()
3064	else:
3065	_nrows = nrows
3066	_ncols = ncols
3067
3068	if not __have_GF2E_modulus:
3069	raise "NoModulus"
3070	cdef unsigned long i, j
3071	cdef ntl_GF2E tmp
3072
3073
3074	self.x = new_mat_GF2E(_nrows, _ncols)
3075	self.__nrows = _nrows
3076	self.__ncols = _ncols
3077	if v != None:
3078	_sig_on
3079	for i from 0 <= i < _nrows:
3080	for j from 0 <= j < _ncols:
3081	elem = v[i*_ncols+j]
3082	if not isinstance(elem, ntl_GF2E):
3083	tmp=make_new_GF2E(elem)
3084	else:
3085	tmp=elem
3086	mat_GF2E_setitem(self.x, i, j, <GF2E*> tmp.gf2e_x)
3087	_sig_off
3088
3089	def __reduce__(self):
3090	raise NotImplementedError
3091
3092
3093	def __dealloc__(self):
3094	del_mat_GF2E(self.x)
3095
3096	def __repr__(self):
3097	_sig_on
3098	return string(mat_GF2E_to_str(self.x))
3099
3100	def __mul__(ntl_mat_GF2E self, other):
3101	cdef ntl_mat_GF2E y
3102	if not isinstance(other, ntl_mat_GF2E):
3103	other = ntl_mat_GF2E(other)
3104	y = other
3105	_sig_on
3106	return make_mat_GF2E(mat_GF2E_mul(self.x, y.x))
3107
3108	def __sub__(ntl_mat_GF2E self, other):
3109	cdef ntl_mat_GF2E y
3110	if not isinstance(other, ntl_mat_GF2E):
3111	other = ntl_mat_GF2E(other)
3112	y = other
3113	_sig_on
3114	return make_mat_GF2E(mat_GF2E_sub(self.x, y.x))
3115
3116	def __add__(ntl_mat_GF2E self, other):
3117	cdef ntl_mat_GF2E y
3118	if not isinstance(other, ntl_mat_GF2E):
3119	other = ntl_mat_GF2E(other)
3120	y = other
3121	_sig_on
3122	return make_mat_GF2E(mat_GF2E_add(self.x, y.x))
3123
3124	def __pow__(ntl_mat_GF2E self, long e, ignored):
3125	_sig_on
3126	return make_mat_GF2E(mat_GF2E_pow(self.x, e))
3127
3128	def nrows(self):
3129	"""
3130	Number of rows
3131	"""
3132	return self.__nrows
3133
3134	def ncols(self):
3135	"""
3136	Number of columns
3137	"""
3138	return self.__ncols
3139
3140	def __setitem__(self, ij, x):
3141	cdef ntl_GF2E y
3142	cdef int i, j
3143	if not isinstance(x, ntl_GF2E):
3144	x = make_new_GF2E(x)
3145	y = x
3146
3147	from sage.rings.integer import Integer
3148	if isinstance(ij, tuple) and len(ij) == 2:
3149	i, j = ij
3150	elif self.ncols()==1 and (isinstance(ij, Integer) or type(ij)==int):
3151	i, j = ij,0
3152	elif self.nrows()==1 and (isinstance(ij, Integer) or type(ij)==int):
3153	i, j = 0,ij
3154	else:
3155	raise TypeError, 'ij is not a matrix index'
3156
3157	if i < 0 or i >= self.__nrows or j < 0 or j >= self.__ncols:
3158	raise IndexError, "array index out of range"
3159	mat_GF2E_setitem(self.x, i, j, <GF2E*> y.gf2e_x)
3160
3161	def __getitem__(self, ij):
3162	cdef int i, j
3163	from sage.rings.integer import Integer
3164	if isinstance(ij, tuple) and len(ij) == 2:
3165	i, j = ij
3166	elif self.ncols()==1 and (isinstance(ij, Integer) or type(ij)==int):
3167	i, j = ij,0
3168	elif self.nrows()==1 and (isinstance(ij, Integer) or type(ij)==int):
3169	i, j = 0,ij
3170	else:
3171	raise TypeError, 'ij is not a matrix index'
3172	if i < 0 or i >= self.__nrows or j < 0 or j >= self.__ncols:
3173	raise IndexError, "array index out of range"
3174	return make_GF2E(mat_GF2E_getitem(self.x, i+1, j+1))
3175
3176	def determinant(self):
3177	"""
3178	Returns the determinant.
3179	"""
3180	_sig_on
3181	return make_GF2E(mat_GF2E_determinant(self.x))
3182
3183	def echelon_form(self,ncols=0):
3184	"""
3185	Performs unitary row operations so as to bring this matrix into row echelon
3186	form. If the optional argument \code{ncols} is supplied, stops when first ncols
3187	columns are in echelon form. The return value is the rank (or the
3188	rank of the first ncols columns).
3189
3190	INPUT:
3191	ncols -- number of columns to process
3192
3193	TODO: what is the output; does it return the rank?
3194	"""
3195	cdef long w
3196	w = ncols
3197	_sig_on
3198	return mat_GF2E_gauss(self.x, w)
3199
3200	def list(self):
3201	"""
3202	Returns a list of the entries in this matrix
3203
3204	EXAMPLES:
3205	sage: ntl.GF2E_modulus([1,1,0,1,1,0,0,0,1])
3206	sage: m = ntl.mat_GF2E(2,2,[ntl.GF2E_random() for x in xrange(2*2)])
3207	sage: m.list() # random output
3208	[[1 0 1 0 1 0 1 1], [0 1 0 0 0 0 1], [0 0 0 1 0 0 1], [1 1 1 0 0 0 0 1]]
3209	"""
3210	cdef unsigned long i, j
3211	v = []
3212	for i from 0 <= i < self.__nrows:
3213	for j from 0 <= j < self.__ncols:
3214	v.append(self[i,j])
3215	return v
3216
3217	def is_zero(self):
3218	cdef long isZero
3219	_sig_on
3220	isZero = mat_GF2E_is_zero(self.x)
3221	_sig_off
3222	if isZero==0:
3223	return False
3224	else:
3225	return True
3226
3227	def _sage_(ntl_mat_GF2E self, k=None, cache=None):
3228	"""
3229	Returns a \class{Matrix} over a FiniteField representation
3230	of this element.
3231
3232	INPUT:
3233	self -- \class{mat_GF2E} element
3234	k -- optional GF(2**deg)
3235	cache -- optional NTL to SAGE conversion dictionary
3236
3237	OUTPUT:
3238	Matrix over k
3239	"""
3240	if k==None:
3241	k = ntl_GF2E_sage()
3242	l = []
3243	for elem in self.list():
3244	l.append(elem._sage_(k, cache))
3245
3246	from sage.matrix.constructor import Matrix
3247	return Matrix(k,self.nrows(),self.ncols(),l)
3248
3249	def transpose(ntl_mat_GF2E self):
3250	"""
3251	Returns the transposed matrix of self.
3252
3253	OUTPUT:
3254	transposed Matrix
3255	"""
3256	_sig_on
3257	return make_mat_GF2E(mat_GF2E_transpose(self.x))
3258
3259	cdef make_mat_GF2E(mat_GF2E* x):
3260	cdef ntl_mat_GF2E y
3261	_sig_off
3262	y = ntl_mat_GF2E(_INIT)
3263	y.x = x
3264	y.__nrows = mat_GF2E_nrows(y.x);
3265	y.__ncols = mat_GF2E_ncols(y.x);
3266	return y

Note: See TracBrowser for help on using the repository browser.

Download in other formats: