001 /*
002 * $Id: ModLongRing.java 3355 2010-10-23 16:01:52Z kredel $
003 */
004
005 package edu.jas.arith;
006
007
008 import java.io.Reader;
009 import java.util.ArrayList;
010 import java.util.List;
011 import java.util.Random;
012 import java.util.Iterator;
013
014 import edu.jas.kern.StringUtil;
015
016
017 /**
018 * ModLongRing factory with RingFactory interface. Effectively immutable.
019 * @author Heinz Kredel
020 */
021
022 public final class ModLongRing implements ModularRingFactory<ModLong>, Iterable<ModLong> {
023
024
025 /**
026 * Module part of the factory data structure.
027 */
028 public final long modul;
029
030
031 /**
032 * Random number generator.
033 */
034 private final static Random random = new Random();
035
036
037 /**
038 * Indicator if this ring is a field.
039 */
040 protected int isField = -1; // initially unknown
041
042
043 /**
044 * Certainty if module is probable prime.
045 */
046 protected int certainty = 10;
047
048
049 /**
050 * maximal representable integer.
051 */
052 public final static java.math.BigInteger MAX_LONG
053 = new java.math.BigInteger(String.valueOf(Integer.MAX_VALUE)); // not larger!
054
055
056 /**
057 * The constructor creates a ModLongRing object from a long integer as
058 * module part.
059 * @param m long integer.
060 */
061 public ModLongRing(long m) {
062 modul = m;
063 }
064
065
066 /**
067 * The constructor creates a ModLongRing object from a long integer as
068 * module part.
069 * @param m long integer.
070 * @param isField indicator if m is prime.
071 */
072 public ModLongRing(long m, boolean isField) {
073 modul = m;
074 this.isField = (isField ? 1 : 0);
075 }
076
077
078 /**
079 * The constructor creates a ModLongRing object from a Long integer as
080 * module part.
081 * @param m Long integer.
082 */
083 public ModLongRing(Long m) {
084 this(m.longValue());
085 }
086
087
088 /**
089 * The constructor creates a ModLongRing object from a Long integer as
090 * module part.
091 * @param m Long integer.
092 * @param isField indicator if m is prime.
093 */
094 public ModLongRing(Long m, boolean isField) {
095 this(m.longValue(), isField);
096 }
097
098
099 /**
100 * The constructor creates a ModLongRing object from a BigInteger converted
101 * to long as module part.
102 * @param m java.math.BigInteger.
103 */
104 public ModLongRing(java.math.BigInteger m) {
105 this(m.longValue());
106 if (MAX_LONG.compareTo(m) <= 0) { // m >= max
107 System.out.println("modul to large for long " + m + ",max=" + MAX_LONG);
108 throw new IllegalArgumentException("modul to large for long " + m);
109 }
110 }
111
112
113 /**
114 * The constructor creates a ModLongRing object from a BigInteger converted
115 * to long as module part.
116 * @param m java.math.BigInteger.
117 * @param isField indicator if m is prime.
118 */
119 public ModLongRing(java.math.BigInteger m, boolean isField) {
120 this(m.longValue(), isField);
121 if (MAX_LONG.compareTo(m) <= 0) { // m >= max
122 System.out.println("modul to large for long " + m + ",max=" + MAX_LONG);
123 throw new IllegalArgumentException("modul to large for long " + m);
124 }
125 }
126
127
128 /**
129 * The constructor creates a ModLongRing object from a String object as
130 * module part.
131 * @param m String.
132 */
133 public ModLongRing(String m) {
134 this(new Long(m.trim()));
135 }
136
137
138 /**
139 * The constructor creates a ModLongRing object from a String object as
140 * module part.
141 * @param m String.
142 * @param isField indicator if m is prime.
143 */
144 public ModLongRing(String m, boolean isField) {
145 this(new Long(m.trim()), isField);
146 }
147
148
149 /**
150 * Get the module part as BigInteger.
151 * @return modul.
152 */
153 public java.math.BigInteger getModul() {
154 return new java.math.BigInteger("" + modul);
155 }
156
157
158 /**
159 * Get the module part as long.
160 * @return modul.
161 */
162 public long getLongModul() {
163 return modul;
164 }
165
166
167 /**
168 * Get the module part as BigInteger.
169 * @return modul.
170 */
171 public BigInteger getIntegerModul() {
172 return new BigInteger(modul);
173 }
174
175
176 /**
177 * Create ModLong element c.
178 * @param c
179 * @return a ModLong of c.
180 */
181 public ModLong create(java.math.BigInteger c) {
182 return new ModLong(this, c);
183 }
184
185
186 /**
187 * Create ModLong element c.
188 * @param c
189 * @return a ModLong of c.
190 */
191 public ModLong create(long c) {
192 return new ModLong(this, c);
193 }
194
195
196 /**
197 * Create ModLong element c.
198 * @param c
199 * @return a ModLong of c.
200 */
201 public ModLong create(String c) {
202 return parse(c);
203 }
204
205
206 /**
207 * Copy ModLong element c.
208 * @param c
209 * @return a copy of c.
210 */
211 public ModLong copy(ModLong c) {
212 return new ModLong(this, c.val);
213 }
214
215
216 /**
217 * Get the zero element.
218 * @return 0 as ModLong.
219 */
220 public ModLong getZERO() {
221 return new ModLong(this, 0L);
222 }
223
224
225 /**
226 * Get the one element.
227 * @return 1 as ModLong.
228 */
229 public ModLong getONE() {
230 return new ModLong(this, 1L);
231 }
232
233
234 /**
235 * Get a list of the generating elements.
236 * @return list of generators for the algebraic structure.
237 * @see edu.jas.structure.ElemFactory#generators()
238 */
239 public List<ModLong> generators() {
240 List<ModLong> g = new ArrayList<ModLong>(1);
241 g.add(getONE());
242 return g;
243 }
244
245
246 /**
247 * Is this structure finite or infinite.
248 * @return true if this structure is finite, else false.
249 * @see edu.jas.structure.ElemFactory#isFinite()
250 */
251 public boolean isFinite() {
252 return true;
253 }
254
255
256 /**
257 * Query if this ring is commutative.
258 * @return true.
259 */
260 public boolean isCommutative() {
261 return true;
262 }
263
264
265 /**
266 * Query if this ring is associative.
267 * @return true.
268 */
269 public boolean isAssociative() {
270 return true;
271 }
272
273
274 /**
275 * Query if this ring is a field.
276 * @return true if module is prime, else false.
277 */
278 public boolean isField() {
279 if (isField > 0) {
280 return true;
281 }
282 if (isField == 0) {
283 return false;
284 }
285 //System.out.println("isProbablePrime " + modul + " = " + modul.isProbablePrime(certainty));
286 java.math.BigInteger m = new java.math.BigInteger("" + modul);
287 if (m.isProbablePrime(m.bitLength())) {
288 isField = 1;
289 return true;
290 }
291 isField = 0;
292 return false;
293 }
294
295
296 /**
297 * Characteristic of this ring.
298 * @return characteristic of this ring.
299 */
300 public java.math.BigInteger characteristic() {
301 return new java.math.BigInteger("" + modul);
302 }
303
304
305 /**
306 * Get a ModLong element from a BigInteger value.
307 * @param a BigInteger.
308 * @return a ModLong.
309 */
310 public ModLong fromInteger(java.math.BigInteger a) {
311 return new ModLong(this, a);
312 }
313
314
315 /**
316 * Get a ModLong element from a long value.
317 * @param a long.
318 * @return a ModLong.
319 */
320 public ModLong fromInteger(long a) {
321 return new ModLong(this, a);
322 }
323
324
325 /**
326 * Get the String representation.
327 * @see java.lang.Object#toString()
328 */
329 @Override
330 public String toString() {
331 return " mod(" + modul + ")"; //",max=" + MAX_LONG + ")";
332 }
333
334
335 /**
336 * Get a scripting compatible string representation.
337 * @return script compatible representation for this ElemFactory.
338 * @see edu.jas.structure.ElemFactory#toScript()
339 */
340 //JAVA6only: @Override
341 public String toScript() {
342 // Python case
343 return "ZL(" + modul + ")";
344 }
345
346
347 /**
348 * Comparison with any other object.
349 * @see java.lang.Object#equals(java.lang.Object)
350 */
351 @Override
352 public boolean equals(Object b) {
353 if (!(b instanceof ModLongRing)) {
354 return false;
355 }
356 ModLongRing m = (ModLongRing) b;
357 return (modul == m.modul);
358 }
359
360
361 /**
362 * Hash code for this ModLongRing.
363 * @see java.lang.Object#hashCode()
364 */
365 @Override
366 public int hashCode() {
367 return (int) modul;
368 }
369
370
371 /**
372 * ModLong random.
373 * @param n such that 0 ≤ v ≤ (2<sup>n</sup>-1).
374 * @return a random integer mod modul.
375 */
376 public ModLong random(int n) {
377 return random(n, random);
378 }
379
380
381 /**
382 * ModLong random.
383 * @param n such that 0 ≤ v ≤ (2<sup>n</sup>-1).
384 * @param rnd is a source for random bits.
385 * @return a random integer mod modul.
386 */
387 public ModLong random(int n, Random rnd) {
388 java.math.BigInteger v = new java.math.BigInteger(n, rnd);
389 return new ModLong(this, v); // rnd.nextLong() not ok
390 }
391
392
393 /**
394 * Parse ModLong from String.
395 * @param s String.
396 * @return ModLong from s.
397 */
398 public ModLong parse(String s) {
399 return new ModLong(this, s);
400 }
401
402
403 /**
404 * Parse ModLong from Reader.
405 * @param r Reader.
406 * @return next ModLong from r.
407 */
408 public ModLong parse(Reader r) {
409 return parse(StringUtil.nextString(r));
410 }
411
412
413 /**
414 * ModLong chinese remainder algorithm. This is a factory method. Assert
415 * c.modul >= a.modul and c.modul * a.modul = this.modul.
416 * @param c ModLong.
417 * @param ci inverse of c.modul in ring of a.
418 * @param a other ModLong.
419 * @return S, with S mod c.modul == c and S mod a.modul == a.
420 */
421 public ModLong chineseRemainder(ModLong c, ModLong ci, ModLong a) {
422 if (true) { // debug
423 if (c.ring.modul < a.ring.modul) {
424 System.out.println("ModLong error " + c.ring + ", " + a.ring);
425 }
426 }
427 ModLong b = a.ring.fromInteger(c.val); // c mod a.modul
428 ModLong d = a.subtract(b); // a-c mod a.modul
429 if (d.isZERO()) {
430 return new ModLong(this, c.val);
431 }
432 b = d.multiply(ci); // b = (a-c)*ci mod a.modul
433 // (c.modul*b)+c mod this.modul = c mod c.modul =
434 // (c.modul*ci*(a-c)+c) mod a.modul = a mod a.modul
435 long s = c.ring.modul * b.val;
436 s = s + c.val;
437 return new ModLong(this, s);
438 }
439
440
441 /** Get a ModLong iterator.
442 * @return a iterator over all modular integers in this ring.
443 */
444 public Iterator<ModLong> iterator() {
445 return new ModLongIterator(this);
446 }
447
448 }
449
450
451 /**
452 * Modular integer iterator.
453 * @author Heinz Kredel
454 */
455 class ModLongIterator implements Iterator<ModLong> {
456
457
458 /**
459 * data structure.
460 */
461 long curr;
462
463
464 final ModLongRing ring;
465
466
467 /**
468 * ModLong iterator constructor.
469 * @param fac modular integer factory;
470 */
471 public ModLongIterator(ModLongRing fac) {
472 curr = 0L;
473 ring = fac;
474 }
475
476
477 /**
478 * Test for availability of a next element.
479 * @return true if the iteration has more elements, else false.
480 */
481 public synchronized boolean hasNext() {
482 return curr < ring.modul;
483 }
484
485
486 /**
487 * Get next integer.
488 * @return next integer.
489 */
490 public synchronized ModLong next() {
491 ModLong i = new ModLong(ring,curr);
492 curr++;
493 return i;
494 }
495
496
497 /**
498 * Remove an element if allowed.
499 */
500 public void remove() {
501 throw new UnsupportedOperationException("cannnot remove elements");
502 }
503 }