001/*
002 * $Id$
003 */
004
005package edu.jas.arith;
006
007
008import java.io.Reader;
009import java.util.ArrayList;
010import java.util.Iterator;
011import java.util.List;
012import java.util.Random;
013
014import edu.jas.kern.StringUtil;
015
016
017/**
018 * ModIntRing factory with RingFactory interface. Effectively immutable.
019 * @author Heinz Kredel
020 */
021
022public final class ModIntRing implements ModularRingFactory<ModInt>, Iterable<ModInt> {
023
024
025    /**
026     * Module part of the factory data structure.
027     */
028    public final int 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    private int isField = -1; // initially unknown
041
042
043    /*
044     * Certainty if module is probable prime.
045     */
046    //private final int certainty = 10;
047
048
049    /**
050     * maximal representable integer.
051     */
052    public final static java.math.BigInteger MAX_INT = new java.math.BigInteger(
053                    String.valueOf(Short.MAX_VALUE)); // not larger!
054
055
056    /**
057     * The constructor creates a ModIntRing object from a int integer as module
058     * part.
059     * @param m int integer.
060     */
061    public ModIntRing(int m) {
062        modul = m;
063    }
064
065
066    /**
067     * The constructor creates a ModIntRing object from a int integer as module
068     * part.
069     * @param m int integer.
070     * @param isField indicator if m is prime.
071     */
072    public ModIntRing(int m, boolean isField) {
073        modul = m;
074        this.isField = (isField ? 1 : 0);
075    }
076
077
078    /**
079     * The constructor creates a ModIntRing object from a Int integer as module
080     * part.
081     * @param m Int integer.
082     */
083    public ModIntRing(Integer m) {
084        this(m.intValue());
085    }
086
087
088    /**
089     * The constructor creates a ModIntRing object from a Int integer as module
090     * part.
091     * @param m Int integer.
092     * @param isField indicator if m is prime.
093     */
094    public ModIntRing(Integer m, boolean isField) {
095        this(m.intValue(), isField);
096    }
097
098
099    /**
100     * The constructor creates a ModIntRing object from a BigInteger converted
101     * to int as module part.
102     * @param m java.math.BigInteger.
103     */
104    public ModIntRing(java.math.BigInteger m) {
105        this(m.intValueExact());
106        if (MAX_INT.compareTo(m) < 0) { // m > max
107            //System.out.println("modul to large for int " + m + ",max=" + MAX_INT);
108            throw new IllegalArgumentException("modul to large for int " + m + ", max=" + MAX_INT);
109        }
110    }
111
112
113    /**
114     * The constructor creates a ModIntRing object from a BigInteger converted
115     * to int as module part.
116     * @param m java.math.BigInteger.
117     * @param isField indicator if m is prime.
118     */
119    public ModIntRing(java.math.BigInteger m, boolean isField) {
120        this(m.intValueExact(), isField);
121        if (MAX_INT.compareTo(m) < 0) { // m > max
122            //System.out.println("modul to large for int " + m + ",max=" + MAX_INT);
123            throw new IllegalArgumentException("modul to large for int " + m + ", max=" + MAX_INT);
124        }
125    }
126
127
128    /**
129     * The constructor creates a ModIntRing object from a String object as
130     * module part.
131     * @param m String.
132     */
133    public ModIntRing(String m) {
134        this(Integer.valueOf(m.trim()));
135    }
136
137
138    /**
139     * The constructor creates a ModIntRing object from a String object as
140     * module part.
141     * @param m String.
142     * @param isField indicator if m is prime.
143     */
144    public ModIntRing(String m, boolean isField) {
145        this(Integer.valueOf(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(Integer.toString(modul));
155    }
156
157
158    /**
159     * Get the module part as int.
160     * @return modul.
161     */
162    public int getIntModul() {
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 ModInt element c.
178     * @param c
179     * @return a ModInt of c.
180     */
181    public ModInt create(java.math.BigInteger c) {
182        return new ModInt(this, c);
183    }
184
185
186    /**
187     * Create ModInt element c.
188     * @param c
189     * @return a ModInt of c.
190     */
191    public ModInt create(int c) {
192        return new ModInt(this, c);
193    }
194
195
196    /**
197     * Create ModInt element c.
198     * @param c
199     * @return a ModInt of c.
200     */
201    public ModInt create(String c) {
202        return parse(c);
203    }
204
205
206    /**
207     * Copy ModInt element c.
208     * @param c
209     * @return a copy of c.
210     */
211    public ModInt copy(ModInt c) {
212        return new ModInt(this, c.val);
213    }
214
215
216    /**
217     * Get the zero element.
218     * @return 0 as ModInt.
219     */
220    public ModInt getZERO() {
221        return new ModInt(this, 0);
222    }
223
224
225    /**
226     * Get the one element.
227     * @return 1 as ModInt.
228     */
229    public ModInt getONE() {
230        return new ModInt(this, 1);
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<ModInt> generators() {
240        List<ModInt> g = new ArrayList<ModInt>(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(Integer.toString(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(Integer.toString(modul));
302    }
303
304
305    /**
306     * Get a ModInt element from a BigInteger value.
307     * @param a BigInteger.
308     * @return a ModInt.
309     */
310    public ModInt fromInteger(java.math.BigInteger a) {
311        return new ModInt(this, a);
312    }
313
314
315    /**
316     * Get a ModInt element from a int value.
317     * @param a int.
318     * @return a ModInt.
319     */
320    public ModInt fromInteger(int a) {
321        return new ModInt(this, a);
322    }
323
324
325    /**
326     * Get a ModInt element from a long value.
327     * @param a lon.
328     * @return a ModInt.
329     */
330    public ModInt fromInteger(long a) {
331        return new ModInt(this, a);
332    }
333
334
335    /**
336     * Get the String representation.
337     * @see java.lang.Object#toString()
338     */
339    @Override
340    public String toString() {
341        return " mod(" + modul + ")"; //",max="  + MAX_INT + ")";
342    }
343
344
345    /**
346     * Get a scripting compatible string representation.
347     * @return script compatible representation for this ElemFactory.
348     * @see edu.jas.structure.ElemFactory#toScript()
349     */
350    @Override
351    public String toScript() {
352        // Python and Ruby case
353        if (isField()) {
354            return "GFI(" + modul + ")";
355        }
356        return "ZMI(" + modul + ")";
357    }
358
359
360    /**
361     * Comparison with any other object.
362     * @see java.lang.Object#equals(java.lang.Object)
363     */
364    @Override
365    public boolean equals(Object b) {
366        if (!(b instanceof ModIntRing)) {
367            return false;
368        }
369        ModIntRing m = (ModIntRing) b;
370        return (modul == m.modul);
371    }
372
373
374    /**
375     * Hash code for this ModIntRing.
376     * @see java.lang.Object#hashCode()
377     */
378    @Override
379    public int hashCode() {
380        return modul;
381    }
382
383
384    /**
385     * ModInt random.
386     * @param n such that 0 &le; v &le; (2<sup>n</sup>-1).
387     * @return a random integer mod modul.
388     */
389    public ModInt random(int n) {
390        return random(n, random);
391    }
392
393
394    /**
395     * ModInt random.
396     * @param n such that 0 &le; v &le; (2<sup>n</sup>-1).
397     * @param rnd is a source for random bits.
398     * @return a random integer mod modul.
399     */
400    public ModInt random(int n, Random rnd) {
401        java.math.BigInteger v = new java.math.BigInteger(n, rnd);
402        return new ModInt(this, v); // rnd.nextInt() not ok
403    }
404
405
406    /**
407     * Parse ModInt from String.
408     * @param s String.
409     * @return ModInt from s.
410     */
411    public ModInt parse(String s) {
412        return new ModInt(this, s);
413    }
414
415
416    /**
417     * Parse ModInt from Reader.
418     * @param r Reader.
419     * @return next ModInt from r.
420     */
421    public ModInt parse(Reader r) {
422        return parse(StringUtil.nextString(r));
423    }
424
425
426    /**
427     * ModInt chinese remainder algorithm. This is a factory method. Assert
428     * c.modul &ge; a.modul and c.modul * a.modul = this.modul.
429     * @param c ModInt.
430     * @param ci inverse of c.modul in ring of a.
431     * @param a other ModInt.
432     * @return S, with S mod c.modul == c and S mod a.modul == a.
433     */
434    public ModInt chineseRemainder(ModInt c, ModInt ci, ModInt a) {
435        //if (true) { 
436        //    if (c.ring.modul < a.ring.modul) {
437        //        System.out.println("ModInt error " + c.ring + ", " + a.ring);
438        //    }
439        //}
440        ModInt b = a.ring.fromInteger(c.val); // c mod a.modul
441        ModInt d = a.subtract(b); // a-c mod a.modul
442        if (d.isZERO()) {
443            return new ModInt(this, c.val);
444        }
445        b = d.multiply(ci); // b = (a-c)*ci mod a.modul
446        // (c.modul*b)+c mod this.modul = c mod c.modul = 
447        // (c.modul*ci*(a-c)+c) mod a.modul = a mod a.modul
448        int s = c.ring.modul * b.val;
449        s = s + c.val;
450        return new ModInt(this, s);
451    }
452
453
454    /**
455     * Modular digit list chinese remainder algorithm. m1 and m2 are positive
456     * beta-integers, with GCD(m1,m2)=1 and m=m1*m2 less than beta. L1 and L2
457     * are lists of elements of Z(m1) and Z(m2) respectively. L is a list of all
458     * a in Z(m) such that a is congruent to a1 modulo m1 and a is congruent to
459     * a2 modulo m2 with a1 in L1 and a2 in L2. This is a factory method. Assert
460     * c.modul &ge; a.modul and c.modul * a.modul = this.modul.
461     * @param m1 ModInt.
462     * @param m2 other ModInt.
463     * @return L list of congruences.
464     */
465    public static List<ModInt> chineseRemainder(ModInt m1, ModInt m2, List<ModInt> L1, List<ModInt> L2) {
466        int mm = m1.ring.modul * m2.ring.modul;
467        ModIntRing m = new ModIntRing(mm);
468        ModInt m21 = m2.ring.fromInteger(m1.ring.modul);
469        ModInt mi1 = m21.inverse();
470
471        List<ModInt> L = new ArrayList<ModInt>();
472        for (ModInt a : L1) {
473            for (ModInt b : L2) {
474                ModInt c = m.chineseRemainder(a, mi1, b);
475                L.add(c);
476            }
477        }
478        return L;
479    }
480
481
482    /**
483     * Get a ModInt iterator.
484     * @return a iterator over all modular integers in this ring.
485     */
486    public Iterator<ModInt> iterator() {
487        return new ModIntIterator(this);
488    }
489
490}
491
492
493/**
494 * Modular integer iterator.
495 * @author Heinz Kredel
496 */
497class ModIntIterator implements Iterator<ModInt> {
498
499
500    /**
501     * data structure.
502     */
503    int curr;
504
505
506    final ModIntRing ring;
507
508
509    /**
510     * ModInt iterator constructor.
511     * @param fac modular integer factory;
512     */
513    public ModIntIterator(ModIntRing fac) {
514        curr = 0;
515        ring = fac;
516    }
517
518
519    /**
520     * Test for availability of a next element.
521     * @return true if the iteration has more elements, else false.
522     */
523    public synchronized boolean hasNext() {
524        return curr < ring.modul;
525    }
526
527
528    /**
529     * Get next integer.
530     * @return next integer.
531     */
532    public synchronized ModInt next() {
533        ModInt i = new ModInt(ring, curr);
534        curr++;
535        return i;
536    }
537
538
539    /**
540     * Remove an element if allowed.
541     */
542    public void remove() {
543        throw new UnsupportedOperationException("cannot remove elements");
544    }
545}