Source code

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 * ModLongRing factory with RingFactory interface. Effectively immutable.
019 * @author Heinz Kredel
020 */
021
022public 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    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_LONG = new java.math.BigInteger(
053                    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.longValueExact());
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 + ", max=" + MAX_LONG);
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.longValueExact(), 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 + ", max=" + MAX_LONG);
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(Long.valueOf(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(Long.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(Long.toString(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(Long.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(Long.toString(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    @Override
341    public String toScript() {
342        // Python and Ruby case
343        if (isField()) {
344            return "GFL(" + modul + ")";
345        }
346        return "ZML(" + modul + ")";
347    }
348
349
350    /**
351     * Comparison with any other object.
352     * @see java.lang.Object#equals(java.lang.Object)
353     */
354    @Override
355    public boolean equals(Object b) {
356        if (!(b instanceof ModLongRing)) {
357            return false;
358        }
359        ModLongRing m = (ModLongRing) b;
360        return (modul == m.modul);
361    }
362
363
364    /**
365     * Hash code for this ModLongRing.
366     * @see java.lang.Object#hashCode()
367     */
368    @Override
369    public int hashCode() {
370        return (int) modul;
371    }
372
373
374    /**
375     * ModLong random.
376     * @param n such that 0 &le; v &le; (2<sup>n</sup>-1).
377     * @return a random integer mod modul.
378     */
379    public ModLong random(int n) {
380        return random(n, random);
381    }
382
383
384    /**
385     * ModLong random.
386     * @param n such that 0 &le; v &le; (2<sup>n</sup>-1).
387     * @param rnd is a source for random bits.
388     * @return a random integer mod modul.
389     */
390    public ModLong random(int n, Random rnd) {
391        java.math.BigInteger v = new java.math.BigInteger(n, rnd);
392        return new ModLong(this, v); // rnd.nextLong() not ok
393    }
394
395
396    /**
397     * Parse ModLong from String.
398     * @param s String.
399     * @return ModLong from s.
400     */
401    public ModLong parse(String s) {
402        return new ModLong(this, s);
403    }
404
405
406    /**
407     * Parse ModLong from Reader.
408     * @param r Reader.
409     * @return next ModLong from r.
410     */
411    public ModLong parse(Reader r) {
412        return parse(StringUtil.nextString(r));
413    }
414
415
416    /**
417     * ModLong chinese remainder algorithm. This is a factory method. Assert
418     * c.modul &ge; a.modul and c.modul * a.modul = this.modul.
419     * @param c ModLong.
420     * @param ci inverse of c.modul in ring of a.
421     * @param a other ModLong.
422     * @return S, with S mod c.modul == c and S mod a.modul == a.
423     */
424    public ModLong chineseRemainder(ModLong c, ModLong ci, ModLong a) {
425        //if (true) { 
426        //    if (c.ring.modul < a.ring.modul) {
427        //        System.out.println("ModLong error " + c.ring + ", " + a.ring);
428        //    }
429        //}
430        ModLong b = a.ring.fromInteger(c.val); // c mod a.modul
431        ModLong d = a.subtract(b); // a-c mod a.modul
432        if (d.isZERO()) {
433            return new ModLong(this, c.val);
434        }
435        b = d.multiply(ci); // b = (a-c)*ci mod a.modul
436        // (c.modul*b)+c mod this.modul = c mod c.modul = 
437        // (c.modul*ci*(a-c)+c) mod a.modul = a mod a.modul
438        long s = c.ring.modul * b.val;
439        s = s + c.val;
440        return new ModLong(this, s);
441    }
442
443
444    /**
445     * Modular digit list chinese remainder algorithm. m1 and m2 are positive
446     * beta-integers, with GCD(m1,m2)=1 and m=m1*m2 less than beta. L1 and L2
447     * are lists of elements of Z(m1) and Z(m2) respectively. L is a list of all
448     * a in Z(m) such that a is congruent to a1 modulo m1 and a is congruent to
449     * a2 modulo m2 with a1 in L1 and a2 in L2. This is a factory method. Assert
450     * c.modul &ge; a.modul and c.modul * a.modul = this.modul.
451     * @param m1 ModLong.
452     * @param m2 other ModLong.
453     * @return L list of congruences.
454     */
455    public static List<ModLong> chineseRemainder(ModLong m1, ModLong m2, List<ModLong> L1, List<ModLong> L2) {
456        long mm = m1.ring.modul * m2.ring.modul;
457        ModLongRing m = new ModLongRing(mm);
458        ModLong m21 = m2.ring.fromInteger(m1.ring.modul);
459        ModLong mi1 = m21.inverse();
460
461        List<ModLong> L = new ArrayList<ModLong>();
462        for (ModLong a : L1) {
463            for (ModLong b : L2) {
464                ModLong c = m.chineseRemainder(a, mi1, b);
465                L.add(c);
466            }
467        }
468        return L;
469    }
470
471
472    /**
473     * Get a ModLong iterator.
474     * @return a iterator over all modular integers in this ring.
475     */
476    public Iterator<ModLong> iterator() {
477        return new ModLongIterator(this);
478    }
479
480}
481
482
483/**
484 * Modular integer iterator.
485 * @author Heinz Kredel
486 */
487class ModLongIterator implements Iterator<ModLong> {
488
489
490    /**
491     * data structure.
492     */
493    long curr;
494
495
496    final ModLongRing ring;
497
498
499    /**
500     * ModLong iterator constructor.
501     * @param fac modular integer factory;
502     */
503    public ModLongIterator(ModLongRing fac) {
504        curr = 0L;
505        ring = fac;
506    }
507
508
509    /**
510     * Test for availability of a next element.
511     * @return true if the iteration has more elements, else false.
512     */
513    public synchronized boolean hasNext() {
514        return curr < ring.modul;
515    }
516
517
518    /**
519     * Get next integer.
520     * @return next integer.
521     */
522    public synchronized ModLong next() {
523        ModLong i = new ModLong(ring, curr);
524        curr++;
525        return i;
526    }
527
528
529    /**
530     * Remove an element if allowed.
531     */
532    public void remove() {
533        throw new UnsupportedOperationException("cannot remove elements");
534    }
535}