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