1 // Modular integer operations.
3 #ifndef _CL_MODINTEGER_H
4 #define _CL_MODINTEGER_H
6 #include "cln/object.h"
8 #include "cln/integer.h"
9 #include "cln/random.h"
10 #include "cln/malloc.h"
12 #include "cln/proplist.h"
13 #include "cln/condition.h"
14 #include "cln/abort.h"
15 #undef random // Linux defines random() as a macro!
19 // Representation of an element of a ring Z/mZ.
21 // To protect against mixing elements of different modular rings, such as
22 // (3 mod 4) + (2 mod 5), every modular integer carries its ring in itself.
25 // Representation of a ring Z/mZ.
27 class cl_heap_modint_ring;
29 class cl_modint_ring : public cl_ring {
31 // Default constructor.
33 // Constructor. Takes a cl_heap_modint_ring*, increments its refcount.
34 cl_modint_ring (cl_heap_modint_ring* r);
36 cl_modint_ring (const cl_modint_ring&);
37 // Assignment operator.
38 cl_modint_ring& operator= (const cl_modint_ring&);
39 // Automatic dereferencing.
40 cl_heap_modint_ring* operator-> () const
41 { return (cl_heap_modint_ring*)heappointer; }
45 extern const cl_modint_ring cl_modint0_ring;
46 // Default constructor. This avoids dealing with NULL pointers.
47 inline cl_modint_ring::cl_modint_ring ()
48 : cl_ring (as_cl_private_thing(cl_modint0_ring)) {}
50 // Copy constructor and assignment operator.
51 CL_DEFINE_COPY_CONSTRUCTOR2(cl_modint_ring,cl_ring)
52 CL_DEFINE_ASSIGNMENT_OPERATOR(cl_modint_ring,cl_modint_ring)
54 // Normal constructor for `cl_modint_ring'.
55 inline cl_modint_ring::cl_modint_ring (cl_heap_modint_ring* r)
56 : cl_ring ((cl_private_thing) (cl_inc_pointer_refcount((cl_heap*)r), r)) {}
58 // Operations on modular integer rings.
60 inline bool operator== (const cl_modint_ring& R1, const cl_modint_ring& R2)
61 { return (R1.pointer == R2.pointer); }
62 inline bool operator!= (const cl_modint_ring& R1, const cl_modint_ring& R2)
63 { return (R1.pointer != R2.pointer); }
64 inline bool operator== (const cl_modint_ring& R1, cl_heap_modint_ring* R2)
65 { return (R1.pointer == R2); }
66 inline bool operator!= (const cl_modint_ring& R1, cl_heap_modint_ring* R2)
67 { return (R1.pointer != R2); }
70 // Condition raised when a probable prime is discovered to be composite.
71 struct cl_composite_condition : public cl_condition {
72 SUBCLASS_cl_condition()
73 cl_I p; // the non-prime
74 cl_I factor; // a nontrivial factor, or 0
76 cl_composite_condition (const cl_I& _p)
79 cl_composite_condition (const cl_I& _p, const cl_I& _f)
82 // Implement general condition methods.
83 const char * name () const;
84 void print (std::ostream&) const;
85 ~cl_composite_condition () {}
89 // Representation of an element of a ring Z/mZ.
91 class _cl_MI /* cf. _cl_ring_element */ {
93 cl_I rep; // representative, integer >=0, <m
94 // (maybe the Montgomery representative!)
95 // Default constructor.
99 _cl_MI (const cl_heap_modint_ring* R, const cl_I& r) : rep (r) { (void)R; }
100 _cl_MI (const cl_modint_ring& R, const cl_I& r) : rep (r) { (void)R; }
103 CL_DEFINE_CONVERTER(_cl_ring_element)
104 public: // Ability to place an object at a given address.
105 void* operator new (size_t size) { return malloc_hook(size); }
106 void* operator new (size_t size, _cl_MI* ptr) { (void)size; return ptr; }
107 void operator delete (void* ptr) { free_hook(ptr); }
110 class cl_MI /* cf. cl_ring_element */ : public _cl_MI {
112 cl_modint_ring _ring; // ring Z/mZ
114 const cl_modint_ring& ring () const { return _ring; }
115 // Default constructor.
116 cl_MI () : _cl_MI (), _ring () {}
119 cl_MI (const cl_modint_ring& R, const cl_I& r) : _cl_MI (R,r), _ring (R) {}
120 cl_MI (const cl_modint_ring& R, const _cl_MI& r) : _cl_MI (r), _ring (R) {}
123 CL_DEFINE_CONVERTER(cl_ring_element)
125 void debug_print () const;
126 public: // Ability to place an object at a given address.
127 void* operator new (size_t size) { return malloc_hook(size); }
128 void* operator new (size_t size, cl_MI* ptr) { (void)size; return ptr; }
129 void operator delete (void* ptr) { free_hook(ptr); }
133 // Representation of an element of a ring Z/mZ or an exception.
139 cl_composite_condition* condition;
141 cl_MI_x (cl_composite_condition* c) : value (), condition (c) {}
142 cl_MI_x (const cl_MI& x) : value (x), condition (NULL) {}
144 //operator cl_MI& () { if (condition) cl_abort(); return value; }
145 //operator const cl_MI& () const { if (condition) cl_abort(); return value; }
146 operator cl_MI () const { if (condition) cl_abort(); return value; }
152 struct _cl_modint_setops /* cf. _cl_ring_setops */ {
154 void (* fprint) (cl_heap_modint_ring* R, std::ostream& stream, const _cl_MI& x);
156 cl_boolean (* equal) (cl_heap_modint_ring* R, const _cl_MI& x, const _cl_MI& y);
158 const _cl_MI (* random) (cl_heap_modint_ring* R, random_state& randomstate);
160 struct _cl_modint_addops /* cf. _cl_ring_addops */ {
162 const _cl_MI (* zero) (cl_heap_modint_ring* R);
163 cl_boolean (* zerop) (cl_heap_modint_ring* R, const _cl_MI& x);
165 const _cl_MI (* plus) (cl_heap_modint_ring* R, const _cl_MI& x, const _cl_MI& y);
167 const _cl_MI (* minus) (cl_heap_modint_ring* R, const _cl_MI& x, const _cl_MI& y);
169 const _cl_MI (* uminus) (cl_heap_modint_ring* R, const _cl_MI& x);
171 struct _cl_modint_mulops /* cf. _cl_ring_mulops */ {
173 const _cl_MI (* one) (cl_heap_modint_ring* R);
174 // canonical homomorphism
175 const _cl_MI (* canonhom) (cl_heap_modint_ring* R, const cl_I& x);
177 const _cl_MI (* mul) (cl_heap_modint_ring* R, const _cl_MI& x, const _cl_MI& y);
179 const _cl_MI (* square) (cl_heap_modint_ring* R, const _cl_MI& x);
181 const _cl_MI (* expt_pos) (cl_heap_modint_ring* R, const _cl_MI& x, const cl_I& y);
183 const cl_MI_x (* recip) (cl_heap_modint_ring* R, const _cl_MI& x);
185 const cl_MI_x (* div) (cl_heap_modint_ring* R, const _cl_MI& x, const _cl_MI& y);
187 const cl_MI_x (* expt) (cl_heap_modint_ring* R, const _cl_MI& x, const cl_I& y);
188 // x -> x mod m for x>=0
189 const cl_I (* reduce_modulo) (cl_heap_modint_ring* R, const cl_I& x);
190 // some inverse of canonical homomorphism
191 const cl_I (* retract) (cl_heap_modint_ring* R, const _cl_MI& x);
193 typedef const _cl_modint_setops cl_modint_setops;
194 typedef const _cl_modint_addops cl_modint_addops;
195 typedef const _cl_modint_mulops cl_modint_mulops;
197 // Representation of the ring Z/mZ.
199 // Currently rings are garbage collected only when they are not referenced
200 // any more and when the ring table gets full.
202 // Modular integer rings are kept unique in memory. This way, ring equality
203 // can be checked very efficiently by a simple pointer comparison.
205 class cl_heap_modint_ring /* cf. cl_heap_ring */ : public cl_heap {
206 SUBCLASS_cl_heap_ring()
208 cl_property_list properties;
210 cl_modint_setops* setops;
211 cl_modint_addops* addops;
212 cl_modint_mulops* mulops;
214 cl_I modulus; // m, normalized to be >= 0
216 // Low-level operations.
217 void _fprint (std::ostream& stream, const _cl_MI& x)
218 { setops->fprint(this,stream,x); }
219 cl_boolean _equal (const _cl_MI& x, const _cl_MI& y)
220 { return setops->equal(this,x,y); }
221 const _cl_MI _random (random_state& randomstate)
222 { return setops->random(this,randomstate); }
223 const _cl_MI _zero ()
224 { return addops->zero(this); }
225 cl_boolean _zerop (const _cl_MI& x)
226 { return addops->zerop(this,x); }
227 const _cl_MI _plus (const _cl_MI& x, const _cl_MI& y)
228 { return addops->plus(this,x,y); }
229 const _cl_MI _minus (const _cl_MI& x, const _cl_MI& y)
230 { return addops->minus(this,x,y); }
231 const _cl_MI _uminus (const _cl_MI& x)
232 { return addops->uminus(this,x); }
234 { return mulops->one(this); }
235 const _cl_MI _canonhom (const cl_I& x)
236 { return mulops->canonhom(this,x); }
237 const _cl_MI _mul (const _cl_MI& x, const _cl_MI& y)
238 { return mulops->mul(this,x,y); }
239 const _cl_MI _square (const _cl_MI& x)
240 { return mulops->square(this,x); }
241 const _cl_MI _expt_pos (const _cl_MI& x, const cl_I& y)
242 { return mulops->expt_pos(this,x,y); }
243 const cl_MI_x _recip (const _cl_MI& x)
244 { return mulops->recip(this,x); }
245 const cl_MI_x _div (const _cl_MI& x, const _cl_MI& y)
246 { return mulops->div(this,x,y); }
247 const cl_MI_x _expt (const _cl_MI& x, const cl_I& y)
248 { return mulops->expt(this,x,y); }
249 const cl_I _reduce_modulo (const cl_I& x)
250 { return mulops->reduce_modulo(this,x); }
251 const cl_I _retract (const _cl_MI& x)
252 { return mulops->retract(this,x); }
253 // High-level operations.
254 void fprint (std::ostream& stream, const cl_MI& x)
256 if (!(x.ring() == this)) cl_abort();
259 cl_boolean equal (const cl_MI& x, const cl_MI& y)
261 if (!(x.ring() == this)) cl_abort();
262 if (!(y.ring() == this)) cl_abort();
265 const cl_MI random (random_state& randomstate = default_random_state)
267 return cl_MI(this,_random(randomstate));
271 return cl_MI(this,_zero());
273 cl_boolean zerop (const cl_MI& x)
275 if (!(x.ring() == this)) cl_abort();
278 const cl_MI plus (const cl_MI& x, const cl_MI& y)
280 if (!(x.ring() == this)) cl_abort();
281 if (!(y.ring() == this)) cl_abort();
282 return cl_MI(this,_plus(x,y));
284 const cl_MI minus (const cl_MI& x, const cl_MI& y)
286 if (!(x.ring() == this)) cl_abort();
287 if (!(y.ring() == this)) cl_abort();
288 return cl_MI(this,_minus(x,y));
290 const cl_MI uminus (const cl_MI& x)
292 if (!(x.ring() == this)) cl_abort();
293 return cl_MI(this,_uminus(x));
297 return cl_MI(this,_one());
299 const cl_MI canonhom (const cl_I& x)
301 return cl_MI(this,_canonhom(x));
303 const cl_MI mul (const cl_MI& x, const cl_MI& y)
305 if (!(x.ring() == this)) cl_abort();
306 if (!(y.ring() == this)) cl_abort();
307 return cl_MI(this,_mul(x,y));
309 const cl_MI square (const cl_MI& x)
311 if (!(x.ring() == this)) cl_abort();
312 return cl_MI(this,_square(x));
314 const cl_MI expt_pos (const cl_MI& x, const cl_I& y)
316 if (!(x.ring() == this)) cl_abort();
317 return cl_MI(this,_expt_pos(x,y));
319 const cl_MI_x recip (const cl_MI& x)
321 if (!(x.ring() == this)) cl_abort();
324 const cl_MI_x div (const cl_MI& x, const cl_MI& y)
326 if (!(x.ring() == this)) cl_abort();
327 if (!(y.ring() == this)) cl_abort();
330 const cl_MI_x expt (const cl_MI& x, const cl_I& y)
332 if (!(x.ring() == this)) cl_abort();
335 const cl_I reduce_modulo (const cl_I& x)
337 return _reduce_modulo(x);
339 const cl_I retract (const cl_MI& x)
341 if (!(x.ring() == this)) cl_abort();
345 sintL bits; // number of bits needed to represent a representative, or -1
346 int log2_bits; // log_2(bits), or -1
347 // Property operations.
348 cl_property* get_property (const cl_symbol& key)
349 { return properties.get_property(key); }
350 void add_property (cl_property* new_property)
351 { properties.add_property(new_property); }
353 cl_heap_modint_ring (cl_I m, cl_modint_setops*, cl_modint_addops*, cl_modint_mulops*);
354 // This class is intented to be subclassable, hence needs a virtual destructor.
355 virtual ~cl_heap_modint_ring () {}
357 virtual void dummy ();
359 #define SUBCLASS_cl_heap_modint_ring() \
360 SUBCLASS_cl_heap_ring()
362 // Lookup or create a modular integer ring Z/mZ
363 extern const cl_modint_ring find_modint_ring (const cl_I& m);
366 // Runtime typing support.
367 extern cl_class cl_class_modint_ring;
370 // Operations on modular integers.
373 inline void fprint (std::ostream& stream, const cl_MI& x)
374 { x.ring()->fprint(stream,x); }
375 CL_DEFINE_PRINT_OPERATOR(cl_MI)
378 inline const cl_MI operator+ (const cl_MI& x, const cl_MI& y)
379 { return x.ring()->plus(x,y); }
380 inline const cl_MI operator+ (const cl_MI& x, const cl_I& y)
381 { return x.ring()->plus(x,x.ring()->canonhom(y)); }
382 inline const cl_MI operator+ (const cl_I& x, const cl_MI& y)
383 { return y.ring()->plus(y.ring()->canonhom(x),y); }
386 inline const cl_MI operator- (const cl_MI& x)
387 { return x.ring()->uminus(x); }
390 inline const cl_MI operator- (const cl_MI& x, const cl_MI& y)
391 { return x.ring()->minus(x,y); }
392 inline const cl_MI operator- (const cl_MI& x, const cl_I& y)
393 { return x.ring()->minus(x,x.ring()->canonhom(y)); }
394 inline const cl_MI operator- (const cl_I& x, const cl_MI& y)
395 { return y.ring()->minus(y.ring()->canonhom(x),y); }
398 extern const cl_MI operator<< (const cl_MI& x, sintL y); // assume 0 <= y < 2^31
399 extern const cl_MI operator>> (const cl_MI& x, sintL y); // assume m odd, 0 <= y < 2^31
402 inline bool operator== (const cl_MI& x, const cl_MI& y)
403 { return x.ring()->equal(x,y); }
404 inline bool operator!= (const cl_MI& x, const cl_MI& y)
405 { return !x.ring()->equal(x,y); }
406 inline bool operator== (const cl_MI& x, const cl_I& y)
407 { return x.ring()->equal(x,x.ring()->canonhom(y)); }
408 inline bool operator!= (const cl_MI& x, const cl_I& y)
409 { return !x.ring()->equal(x,x.ring()->canonhom(y)); }
410 inline bool operator== (const cl_I& x, const cl_MI& y)
411 { return y.ring()->equal(y.ring()->canonhom(x),y); }
412 inline bool operator!= (const cl_I& x, const cl_MI& y)
413 { return !y.ring()->equal(y.ring()->canonhom(x),y); }
415 // Compare against 0.
416 inline cl_boolean zerop (const cl_MI& x)
417 { return x.ring()->zerop(x); }
420 inline const cl_MI operator* (const cl_MI& x, const cl_MI& y)
421 { return x.ring()->mul(x,y); }
424 inline const cl_MI square (const cl_MI& x)
425 { return x.ring()->square(x); }
427 // Exponentiation x^y, where y > 0.
428 inline const cl_MI expt_pos (const cl_MI& x, const cl_I& y)
429 { return x.ring()->expt_pos(x,y); }
432 inline const cl_MI recip (const cl_MI& x)
433 { return x.ring()->recip(x); }
436 inline const cl_MI div (const cl_MI& x, const cl_MI& y)
437 { return x.ring()->div(x,y); }
438 inline const cl_MI div (const cl_MI& x, const cl_I& y)
439 { return x.ring()->div(x,x.ring()->canonhom(y)); }
440 inline const cl_MI div (const cl_I& x, const cl_MI& y)
441 { return y.ring()->div(y.ring()->canonhom(x),y); }
443 // Exponentiation x^y.
444 inline const cl_MI expt (const cl_MI& x, const cl_I& y)
445 { return x.ring()->expt(x,y); }
447 // Scalar multiplication.
448 inline const cl_MI operator* (const cl_I& x, const cl_MI& y)
449 { return y.ring()->mul(y.ring()->canonhom(x),y); }
450 inline const cl_MI operator* (const cl_MI& x, const cl_I& y)
451 { return x.ring()->mul(x.ring()->canonhom(y),x); }
453 // TODO: implement gcd, index (= gcd), unitp, sqrtp
456 // Debugging support.
458 extern int cl_MI_debug_module;
459 static void* const cl_MI_debug_dummy[] = { &cl_MI_debug_dummy,
466 #endif /* _CL_MODINTEGER_H */