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