Context Navigation

source: sage/libs/ntl/ntl.pyx @ 3173:8ef6a6e960f0

Visit:

Revision 3173:8ef6a6e960f0, 94.2 KB checked in by William Stein <wstein@…>, 6 years ago (diff)
merge

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

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

Download in other formats: