source: trunk/linbox/linbox/field/NTL/ntl-ZZ_p.h @ 4093

Revision 4093, 11.6 KB checked in by saunders, 3 years ago (diff)

NonZeroRandIter? no longer a field member type. Use NonzeroRandIter? in randiter/nonzero.h

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
Line 
1/* -*- mode: C++; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
2// vim:sts=8:sw=8:ts=8:noet:sr:cino=>s,f0,{0,g0,(0,\:0,t0,+0,=s
3/* linbox/field/ntl.h
4 * Copyright (C) 1999-2005 William J Turner,
5 *               2001 Bradford Hovinen
6 * Copyright (C) 2011 LinBox
7 *
8 * Written by W. J. Turner <wjturner@acm.org>,
9 *            Bradford Hovinen <hovinen@cis.udel.edu>
10 *
11 * See COPYING for license information.
12 */
13
14/*! @file field/NTL/ntl-ZZ_p.h
15 * @ingroup field
16 * @ingroup NTL
17 * @brief NO DOC
18 */
19
20#ifndef __LINBOX_field_ntl_zz_p_H
21#define __LINBOX_field_ntl_zz_p_H
22
23#ifndef __LINBOX_HAVE_NTL
24#error "you need NTL here"
25#endif
26
27#include <sys/time.h>
28#include <NTL/ZZ_p.h>
29#include <NTL/ZZ.h>
30
31#include "linbox/linbox-config.h"
32#include "linbox/util/debug.h"
33
34#include "linbox/field/unparametric.h"
35#include "linbox/randiter/unparametric.h"
36#include "linbox/field/field-traits.h"
37
38
39// Namespace in which all LinBox library code resides
40namespace LinBox
41{
42
43        //@{
44
45        /** Conversion of field element to an integer.
46         * This function assumes the output field element x has already been
47         * constructed, but that it is not already initialized.
48         * This done by converting to a std::string : inefficient but correct.
49         * @return reference to integer.
50         * @param x reference to integer to contain output (reference returned).
51         * @param y constant reference to field element.
52         */
53        template <>
54        integer& Caster(integer& x, const NTL::ZZ_p& y)
55        {
56                NTL::ZZ iy = y._ZZ_p__rep;
57
58                long nb = NTL::NumBytes(iy);
59                unsigned char *txt;
60                typedef unsigned char u_char;
61                txt = new u_char[nb + 68];
62                //                         if (!txt) Error("out of memory");
63                BytesFromZZ(txt, iy, nb);
64
65                x = 0;
66                for (long i = 0; i < nb; i++) {
67                        x += LinBox::integer( (unsigned long)txt[i] )<<(8*i) ;
68                }
69                delete [] txt;
70                return x;
71        }
72
73        //dpritcha
74        template<>
75        double& Caster(double& x, const NTL::ZZ_p& y)
76        {
77                x = NTL::to_double(NTL::rep(y));
78                return x;
79        }
80
81        /**\brief Initialization of field element from an integer.
82         * Behaves like C++ allocator construct.
83         * This function assumes the output field element x has already been
84         * constructed, but that it is not already initialized.
85         * This done by converting to a std::string : inefficient but correct.
86         * @return reference to field element.
87         * @param x field element to contain output (reference returned).
88         * @param y integer.
89         \ingroup field
90         */
91        template <>
92        NTL::ZZ_p& Caster(NTL::ZZ_p& x, const integer& y)
93        {
94                return x = NTL::to_ZZ_p( NTL::to_ZZ( (static_cast<const std::string>(y)).c_str() ) );
95        }
96        template <>
97        NTL::ZZ_p& Caster(NTL::ZZ_p& x, const double& y)
98        {
99                return x = NTL::to_ZZ_p( NTL::to_ZZ((long)(y) ) );
100        }
101        template <>
102        NTL::ZZ_p& Caster(NTL::ZZ_p& x, const int& y)
103        {
104                return x = NTL::to_ZZ_p( NTL::to_ZZ((long)(y) ) );
105        }
106        template <>
107        NTL::ZZ_p& Caster(NTL::ZZ_p& x, const unsigned long& y)
108        {
109                return x = NTL::to_ZZ_p( NTL::to_ZZ((long)(y) ) );
110        }
111        template <>
112        NTL::ZZ_p& Caster(NTL::ZZ_p& x, const unsigned int& y)
113        {
114                return x = NTL::to_ZZ_p( NTL::to_ZZ((long)(y) ) );
115        }
116
117        //@} doc of NTL_ZZ_p
118
119
120        class NTL_ZZ_p_Initialiser {
121        public :
122                NTL_ZZ_p_Initialiser( const Integer & q, size_t e = 1) {
123                        linbox_check(e == 1);
124                        if ( q > 0 )
125                                NTL::ZZ_p::init(NTL::to_ZZ((std::string(q)).data())); // it's an error if q not prime, e not 1
126                }
127
128                template <class ElementInt>
129                NTL_ZZ_p_Initialiser(const ElementInt& d) {
130                        NTL::ZZ_p::init (NTL::to_ZZ(d));
131                }
132
133                NTL_ZZ_p_Initialiser (const NTL::ZZ& d) {
134                        NTL::ZZ_p::init(d);
135                }
136
137                NTL_ZZ_p_Initialiser () { }
138
139        };
140
141        /**
142         *
143         * @brief Wrapper of zz_p from NTL.
144         * Uses nice mod p via floating pt trick.
145         *
146         */
147        struct NTL_ZZ_p: public NTL_ZZ_p_Initialiser, public FFPACK::UnparametricOperations<NTL::ZZ_p> {
148                typedef NTL::ZZ_p Element ;
149                typedef FFPACK::UnparametricOperations<Element> Father_t ;
150
151                typedef UnparametricRandIter<Element> RandIter;
152
153                const Element zero,one,mOne ;
154
155                /** @name NTL_ZZ_p
156                 * @brief Arbitrary precision integers modulus a positive integer.
157
158                 * While NTL allows any integer to serve as the modulus, only prime
159                 * moduli yield fields.  Therefore, while arthmetic operations may be
160                 * valid for any modulus, only prime moduli are supported in this
161                 * implementation.  The primality of the modulus will not be checked, so
162                 * it is the programmer's responsibility to supply a prime modulus.
163                 * These specializations allow the \ref UnparametricField template class to be
164                 * used to wrap NTL's <code>ZZ_p</code> class as a LinBox field.
165                 */
166                NTL_ZZ_p(integer q, size_t e = 1) :
167                        NTL_ZZ_p_Initialiser(q,e),Father_t ()
168                        ,zero( NTL::to_ZZ_p(0)),one( NTL::to_ZZ_p(1)),mOne(-one)
169                {
170                        // no default - allow initialization of ZZ_p directly by user.
171                }
172
173                NTL_ZZ_p( NTL::ZZ d, size_t e = 1) :
174                        NTL_ZZ_p_Initialiser(d),Father_t()
175                        ,zero( NTL::to_ZZ_p(0)),one( NTL::to_ZZ_p(1)),mOne(-one)
176                {
177                        linbox_check(e == 1);
178                }
179                NTL_ZZ_p() :
180                        NTL_ZZ_p_Initialiser(), Father_t()
181                        ,zero( NTL::to_ZZ_p(0)),one( NTL::to_ZZ_p(1)),mOne(-one)
182                {}
183
184                Element& init(Element& x, const integer& y) const
185                {
186                        return Caster(x,y);
187                }
188
189                Element& init(Element& x, const double& y) const
190                {
191                        double z = fmod(y,NTL::to_double(Element::modulus()));
192                        if (z > 0) z += 0.5;
193                        else z -= 0.5;
194                        return x = NTL::to_ZZ_p(static_cast<long>(z)); //rounds towards 0
195                }
196
197                /** Specialization for NTL::ZZ
198                 *
199                 * @return reference to field element.
200                 * @param x field element to contain output (reference returned)
201                 * @param y NTL::ZZ.
202                 */
203                Element& init(Element& x, const NTL::ZZ& y) const
204                {
205                        return x = NTL::to_ZZ_p( y );
206                }
207
208                Element& init(Element& x) const
209                {
210                        return x = NTL::to_ZZ_p( 0L );
211                }
212
213                Element& init(Element& x, const Element& y) const
214                {
215                        return x = y ;
216                }
217
218                template <class ANY> //dpritcha--FIX
219                Element& init(Element& x, const ANY& y) const
220                {
221                        return x = NTL::to_ZZ_p((long)(y));
222                }
223
224                /** Specialization for NTL::ZZ.
225                 *
226                 * @return reference to  NTL::ZZ
227                 * @param x  NTL::ZZ to contain output (reference returned).
228                 * @param y constant reference to field element.
229                 */
230                NTL::ZZ& convert(NTL::ZZ& x, const Element& y) const
231                {
232                        return x = y._ZZ_p__rep;
233                }
234
235                /** Conversion of field element to an integer.
236                 * This function assumes the output field element x has already been
237                 * constructed, but that it is not already initialized.
238                 * This done by converting to a std::string : inefficient but correct.
239                 * @return reference to integer.
240                 * @param x reference to integer to contain output (reference returned).
241                 * @param y constant reference to field element.
242                 */
243                integer& convert(integer& x, const Element& y) const
244                {
245                        NTL::ZZ iy = y._ZZ_p__rep;
246
247                        long nb = NTL::NumBytes(iy);
248                        unsigned char *txt;
249                        typedef unsigned char u_char;
250                        txt = new u_char[nb + 68];
251                        //                         if (!txt) Error("out of memory");
252                        BytesFromZZ(txt, iy, nb);
253
254                        x = 0;
255                        for (long i = 0; i < nb; i++) {
256                                x += LinBox::integer( (unsigned long)txt[i] )<<(8*i) ;
257                        }
258                        delete [] txt;
259                        return x;
260                };
261
262                double& convert(double& x, const Element& y) const
263                {
264                        x = NTL::to_double(NTL::rep(y));
265                        return x;
266                }
267
268                template <class ANY>
269                ANY& convert(ANY& x, const Element& y) const
270                {
271                        return x = (ANY)(rep(y));
272                }
273
274                static inline integer getMaxModulus()
275                {
276                        return integer( -1 );
277                }
278
279                Element& pow( Element& res, const Element& x, long exp ) const
280                {
281                        NTL::power( res, x, exp );
282                        return res;
283                }
284
285                Element& powin( Element& x, long exp ) const
286                {
287                        return x = NTL::power(x,exp);
288                }
289
290                /** Cardinality.
291                 * Return integer representing cardinality of the field.
292                 * Returns the modulus of the field, which should be prime.
293                 * @return integer representing cardinality of the field
294                 */
295                integer& cardinality(integer& c) const
296                {
297                        return c = static_cast<integer>(to_long(Element::modulus()));
298                }
299
300                integer cardinality() const
301                {
302                        return static_cast<integer>(to_long(Element::modulus()));
303                }
304
305                /** Characteristic.
306                 * Return integer representing characteristic of the field.
307                 * Returns the modulus of the field, which should be prime.
308                 * @return integer representing characteristic of the field.
309                 */
310                integer& characteristic(integer& c) const
311                //FIXME we shouldn't go thru long here as p may be larger than that.
312                // check if NTL has cast ZZp to gmp integers.
313                {
314                        return c = static_cast<integer>(to_long(Element::modulus()));
315                }
316
317                size_t& characteristic(size_t & c) const
318                {
319                        return c = to_long(Element::modulus());
320                }
321
322                integer characteristic() const
323                {
324                        return static_cast<integer>(to_long(Element::modulus()));
325                }
326
327                /** Multiplicative Inverse.
328                 * x = 1 / y
329                 * This function assumes both field elements have already been
330                 * constructed and initialized.
331                 * @return reference to x.
332                 * @param  x field element (reference returned).
333                 * @param  y field element.
334                 */
335                Element&
336                inv(Element& x, const Element& y) const
337                {
338                        return x = NTL::inv(y);
339                }
340
341                /** Zero equality.
342                 * Test if field element is equal to zero.
343                 * This function assumes the field element has already been
344                 * constructed and initialized.
345                 * In this specialization, NTL's IsZero function is called.
346                 * @return boolean true if equals zero, false if not.
347                 * @param  x field element.
348                 */
349                bool isZero(const Element& x) const
350                {
351                        return static_cast<bool>(IsZero(x));
352                }
353
354                /** One equality.
355                 * Test if field element is equal to one.
356                 * This function assumes the field element has already been
357                 * constructed and initialized.
358                 * In this specialization, NTL's IsOne function is called.
359                 * @return boolean true if equals one, false if not.
360                 * @param  x field element.
361                 */
362                bool isOne(const Element& x) const
363                {
364                        return static_cast<bool>(IsOne(x));
365                }
366
367                /** Inplace Multiplicative Inverse.
368                 * x = 1 / x
369                 * This function assumes both field elements have already been
370                 * constructed and initialized.
371                 * @return reference to x.
372                 * @param  x field element (reference returned).
373                 */
374                Element& invin(Element& x) const
375                {
376                        return x = NTL::inv(x);
377                }
378
379                /** Print field.
380                 * @return output stream to which field is written.
381                 * @param  os  output stream to which field is written.
382                 */
383                std::ostream& write(std::ostream& os) const
384                {
385                        return os << "unparameterized field Element with p = "
386                        << Element::modulus();
387                }
388
389                std::ostream &write (std::ostream &os, const Element &x) const { return FFPACK::UnparametricOperations<Element>::write(os,x); }
390        };
391
392        template <class Ring>
393        struct ClassifyRing;
394
395        template <>
396        struct ClassifyRing<NTL_ZZ_p > {
397                typedef RingCategories::ModularTag categoryTag;
398        };
399
400        /// Constructor for random field element generator
401        template <>
402        class UnparametricRandIter<NTL::ZZ_p> {
403        protected:
404                integer _size,_seed;
405        public:
406
407                UnparametricRandIter<NTL::ZZ_p> (const NTL_ZZ_p & F,
408                                                 const integer& size = 0,
409                                                 const integer& seed = 0) :
410                        _size(size), _seed(seed)
411                {
412                        if (_seed == integer(0)) _seed = integer(time(NULL));
413
414                        integer cardinality;
415                        F.cardinality(cardinality);
416                        if (_size > cardinality)
417                                _size = 0;
418
419#ifdef TRACE
420                        std::cout << "created random generator with size " << _size
421                        << " and seed " << _seed << std::endl;
422#endif // TRACE
423
424                        // Seed random number generator
425                        NTL::SetSeed(NTL::to_ZZ(static_cast<long>(_seed)));
426                }
427
428                // UnparametricRandIter<NTL::ZZ_p>(const NTL_ZZ_p& R) :
429                        // _size(R._size), _seed(R._seed)
430                // {
431                        // if(_seed == 0)
432                                // NTL::SetSeed(NTL::to_ZZ(time(0)));
433                        // else
434                                // NTL::SetSeed(NTL::to_ZZ( static_cast<long>(_seed)) );
435                // }
436
437
438                /// Random field element creator.
439                NTL::ZZ_p& random(NTL::ZZ_p& x) const
440                {
441                        if (_size == 0) {
442                                return x = NTL::random_ZZ_p();
443                        }
444                        else {
445                                return x = NTL::to_ZZ_p(NTL::RandomBnd(static_cast<long>(_size)));
446                        }
447                }
448
449
450        };
451
452
453} // namespace LinBox
454
455#endif // __LINBOX_field_ntl_zz_p_H
456
Note: See TracBrowser for help on using the repository browser.