001 /*
002 * $Id: ModLong.java 3501 2011-01-23 19:33:54Z kredel $
003 */
004
005 package edu.jas.arith;
006
007
008 import edu.jas.structure.GcdRingElem;
009 import edu.jas.structure.NotInvertibleException;
010
011
012 /**
013 * ModLong class with RingElem interface. Objects of this class are immutable.
014 * @author Heinz Kredel
015 * @see ModInteger
016 */
017
018 public final class ModLong implements GcdRingElem<ModLong>, Modular {
019
020
021 /**
022 * ModLongRing reference.
023 */
024 public final ModLongRing ring;
025
026
027 /**
028 * Value part of the element data structure.
029 */
030 protected final long val;
031
032
033 /**
034 * The constructor creates a ModLong object from a ModLongRing and a value
035 * part.
036 * @param m ModLongRing.
037 * @param a math.BigInteger.
038 */
039 public ModLong(ModLongRing m, java.math.BigInteger a) {
040 this(m, a.mod(new java.math.BigInteger("" + m.modul)).longValue());
041 }
042
043
044 /**
045 * The constructor creates a ModLong object from a ModLongRing and a long
046 * value part.
047 * @param m ModLongRing.
048 * @param a long.
049 */
050 public ModLong(ModLongRing m, long a) {
051 ring = m;
052 long v = a % ring.modul;
053 val = (v >= 0L ? v : v + ring.modul);
054 }
055
056
057 /**
058 * The constructor creates a ModLong object from a ModLongRing and a Long
059 * value part.
060 * @param m ModLongRing.
061 * @param a Long.
062 */
063 public ModLong(ModLongRing m, Long a) {
064 this(m, a.longValue());
065 }
066
067
068 /**
069 * The constructor creates a ModLong object from a ModLongRing and a String
070 * value part.
071 * @param m ModLongRing.
072 * @param s String.
073 */
074 public ModLong(ModLongRing m, String s) {
075 this(m, new Long(s.trim()));
076 }
077
078
079 /**
080 * The constructor creates a 0 ModLong object from a given ModLongRing.
081 * @param m ModLongRing.
082 */
083 public ModLong(ModLongRing m) {
084 this(m, 0L);
085 }
086
087
088 /**
089 * Get the value part.
090 * @return val.
091 */
092 public long getVal() {
093 return val;
094 }
095
096
097 /**
098 * Get the module part.
099 * @return modul.
100 */
101 public long getModul() {
102 return ring.modul;
103 }
104
105
106 /**
107 * Get the corresponding element factory.
108 * @return factory for this Element.
109 * @see edu.jas.structure.Element#factory()
110 */
111 public ModLongRing factory() {
112 return ring;
113 }
114
115
116 /**
117 * Get the symmetric value part.
118 * @return val with -modul/2 <= val < modul/2.
119 */
120 public long getSymmetricVal() {
121 if ((val + val) > ring.modul) {
122 // val > m/2 as 2*val > m, make symmetric to 0
123 return val - ring.modul;
124 }
125 return val;
126 }
127
128
129 /**
130 * Return a BigInteger from this Element.
131 * @return a BigInteger of this.
132 */
133 public BigInteger getInteger() {
134 return new BigInteger(val);
135 }
136
137
138 /**
139 * Return a symmetric BigInteger from this Element.
140 * @return a symmetric BigInteger of this.
141 */
142 public BigInteger getSymmetricInteger() {
143 long v = val;
144 if ((val + val) > ring.modul) {
145 // val > m/2 as 2*val > m, make symmetric to 0
146 v = val - ring.modul;
147 }
148 return new BigInteger(v);
149 }
150
151
152 /**
153 * Clone this.
154 * @see java.lang.Object#clone()
155 */
156 @Override
157 public ModLong clone() {
158 return new ModLong(ring, val);
159 }
160
161
162 /**
163 * Is ModLong number zero.
164 * @return If this is 0 then true is returned, else false.
165 * @see edu.jas.structure.RingElem#isZERO()
166 */
167 public boolean isZERO() {
168 return val == 0L;
169 }
170
171
172 /**
173 * Is ModLong number one.
174 * @return If this is 1 then true is returned, else false.
175 * @see edu.jas.structure.RingElem#isONE()
176 */
177 public boolean isONE() {
178 return val == 1L;
179 }
180
181
182 /**
183 * Is ModLong number a unit.
184 * @return If this is a unit then true is returned, else false.
185 * @see edu.jas.structure.RingElem#isUnit()
186 */
187 public boolean isUnit() {
188 if (isZERO()) {
189 return false;
190 }
191 if (ring.isField()) {
192 return true;
193 }
194 long g = gcd(ring.modul, val);
195 return (g == 1L || g == -1L);
196 }
197
198
199 /**
200 * Get the String representation.
201 * @see java.lang.Object#toString()
202 */
203 @Override
204 public String toString() {
205 return "" + val;
206 }
207
208
209 /**
210 * Get a scripting compatible string representation.
211 * @return script compatible representation for this Element.
212 * @see edu.jas.structure.Element#toScript()
213 */
214 //JAVA6only: @Override
215 public String toScript() {
216 // Python case
217 return toString();
218 }
219
220
221 /**
222 * Get a scripting compatible string representation of the factory.
223 * @return script compatible representation for this ElemFactory.
224 * @see edu.jas.structure.Element#toScriptFactory()
225 */
226 //JAVA6only: @Override
227 public String toScriptFactory() {
228 // Python case
229 return factory().toScript();
230 }
231
232
233 /**
234 * ModLong comparison.
235 * @param b ModLong.
236 * @return sign(this-b).
237 */
238 //JAVA6only: @Override
239 public int compareTo(ModLong b) {
240 long v = b.val;
241 if (ring != b.ring) {
242 v = v % ring.modul;
243 }
244 if (val > v) {
245 return 1;
246 }
247 return (val < v ? -1 : 0);
248 }
249
250
251 /**
252 * Comparison with any other object.
253 * @see java.lang.Object#equals(java.lang.Object)
254 */
255 @Override
256 public boolean equals(Object b) {
257 if (!(b instanceof ModLong)) {
258 return false;
259 }
260 return (0 == compareTo((ModLong) b));
261 }
262
263
264 /**
265 * Hash code for this ModLong.
266 * @see java.lang.Object#hashCode()
267 */
268 @Override
269 public int hashCode() {
270 return (int) val;
271 }
272
273
274 /**
275 * ModLong absolute value.
276 * @return the absolute value of this.
277 * @see edu.jas.structure.RingElem#abs()
278 */
279 public ModLong abs() {
280 return new ModLong(ring, (val < 0 ? -val : val));
281 }
282
283
284 /**
285 * ModLong negative.
286 * @see edu.jas.structure.RingElem#negate()
287 * @return -this.
288 */
289 public ModLong negate() {
290 return new ModLong(ring, -val);
291 }
292
293
294 /**
295 * ModLong signum.
296 * @see edu.jas.structure.RingElem#signum()
297 * @return signum(this).
298 */
299 public int signum() {
300 if (val > 0L) {
301 return 1;
302 }
303 return (val < 0L ? -1 : 0);
304 }
305
306
307 /**
308 * ModLong subtraction.
309 * @param S ModLong.
310 * @return this-S.
311 */
312 public ModLong subtract(ModLong S) {
313 return new ModLong(ring, val - S.val);
314 }
315
316
317 /**
318 * ModLong divide.
319 * @param S ModLong.
320 * @return this/S.
321 */
322 public ModLong divide(ModLong S) {
323 try {
324 return multiply(S.inverse());
325 } catch (NotInvertibleException e) {
326 try {
327 if ((val % S.val) == 0L) {
328 return new ModLong(ring, val / S.val);
329 }
330 throw new NotInvertibleException(e.getCause());
331 } catch (ArithmeticException a) {
332 throw new NotInvertibleException(a.getCause());
333 }
334 }
335 }
336
337
338 /**
339 * ModLong inverse.
340 * @see edu.jas.structure.RingElem#inverse()
341 * @throws NotInvertibleException if the element is not invertible.
342 * @return S with S=1/this if defined.
343 */
344 public ModLong inverse() /*throws NotInvertibleException*/{
345 try {
346 return new ModLong(ring, modInverse(val, ring.modul));
347 } catch (ArithmeticException e) {
348 long g = gcd( val, ring.modul );
349 long f = ring.modul / g;
350 throw new ModularNotInvertibleException(e,new BigInteger(ring.modul),new BigInteger(g),new BigInteger(f));
351 }
352 }
353
354
355 /**
356 * ModLong remainder.
357 * @param S ModLong.
358 * @return remainder(this,S).
359 */
360 public ModLong remainder(ModLong S) {
361 if (S == null || S.isZERO()) {
362 throw new ArithmeticException(this.getClass().getName() + " division by zero");
363 }
364 if (S.isONE()) {
365 return ring.getZERO();
366 }
367 if (S.isUnit()) {
368 return ring.getZERO();
369 }
370 return new ModLong(ring, val % S.val);
371 }
372
373
374 /**
375 * ModLong multiply.
376 * @param S ModLong.
377 * @return this*S.
378 */
379 public ModLong multiply(ModLong S) {
380 return new ModLong(ring, val * S.val);
381 }
382
383
384 /**
385 * ModLong summation.
386 * @param S ModLong.
387 * @return this+S.
388 */
389 public ModLong sum(ModLong S) {
390 return new ModLong(ring, val + S.val);
391 }
392
393
394 /**
395 * ModInteger greatest common divisor.
396 * @param S ModInteger.
397 * @return [ gcd(this,S), a, b ] with a*this + b*S = gcd(this,S).
398 */
399 public ModLong gcd(ModLong S) {
400 if (S.isZERO()) {
401 return this;
402 }
403 if (isZERO()) {
404 return S;
405 }
406 if (isUnit() || S.isUnit()) {
407 return ring.getONE();
408 }
409 return new ModLong(ring, gcd(val, S.val));
410 }
411
412
413 /**
414 * ModInteger extended greatest common divisor.
415 * @param S ModInteger.
416 * @return [ gcd(this,S), a, b ] with a*this + b*S = gcd(this,S).
417 */
418 public ModLong[] egcd(ModLong S) {
419 ModLong[] ret = new ModLong[3];
420 ret[0] = null;
421 ret[1] = null;
422 ret[2] = null;
423 if (S == null || S.isZERO()) {
424 ret[0] = this;
425 return ret;
426 }
427 if (isZERO()) {
428 ret[0] = S;
429 return ret;
430 }
431 if (isUnit() || S.isUnit()) {
432 ret[0] = ring.getONE();
433 if (isUnit() && S.isUnit()) {
434 //ModLong half = (new ModLong(ring, 2L)).inverse();
435 //ret[1] = this.inverse().multiply(half);
436 //ret[2] = S.inverse().multiply(half);
437 // (1-1*this)/S
438 ret[1] = ring.getONE();
439 ModLong x = ret[0].subtract(ret[1].multiply(this));
440 ret[2] = x.divide(S);
441 return ret;
442 }
443 if (isUnit()) {
444 // oder inverse(S-1)?
445 ret[1] = this.inverse();
446 ret[2] = ring.getZERO();
447 return ret;
448 }
449 // if ( s.isUnit() ) {
450 // oder inverse(this-1)?
451 ret[1] = ring.getZERO();
452 ret[2] = S.inverse();
453 return ret;
454 //}
455 }
456 //System.out.println("this = " + this + ", S = " + S);
457 long q = this.val;
458 long r = S.val;
459 long c1 = 1L; // BigInteger.ONE.val;
460 long d1 = 0L; // BigInteger.ZERO.val;
461 long c2 = 0L; // BigInteger.ZERO.val;
462 long d2 = 1L; // BigInteger.ONE.val;
463 long x1;
464 long x2;
465 while (r != 0L) {
466 //qr = q.divideAndRemainder(r);
467 long a = q / r;
468 long b = q % r;
469 q = a;
470 x1 = c1 - q * d1;
471 x2 = c2 - q * d2;
472 c1 = d1;
473 c2 = d2;
474 d1 = x1;
475 d2 = x2;
476 q = r;
477 r = b;
478 }
479 System.out.println("q = " + q + "\n c1 = " + c1 + "\n c2 = " + c2);
480 ret[0] = new ModLong(ring, q);
481 ret[1] = new ModLong(ring, c1);
482 ret[2] = new ModLong(ring, c2);
483 return ret;
484 }
485
486
487 /**
488 * Long greatest common divisor.
489 * @param T long.
490 * @param S long.
491 * @return gcd(T,S).
492 */
493 public long gcd(long T, long S) {
494 if (S == 0L) {
495 return T;
496 }
497 if (T == 0L) {
498 return S;
499 }
500 long a = T;
501 long b = S;
502 while (b != 0L) {
503 long r = a % b;
504 a = b;
505 b = r;
506 }
507 return a;
508 }
509
510
511 /**
512 * Long half extended greatest common divisor.
513 * @param T long.
514 * @param S long.
515 * @return [ gcd(T,S), a ] with a*T + b*S = gcd(T,S).
516 */
517 public long[] hegcd(long T, long S) {
518 long[] ret = new long[2];
519 if (S == 0L) {
520 ret[0] = T;
521 ret[1] = 1L;
522 return ret;
523 }
524 if (T == 0L) {
525 ret[0] = S;
526 ret[1] = 0L;
527 return ret;
528 }
529 //System.out.println("hegcd, T = " + T + ", S = " + S);
530 long a = T;
531 long b = S;
532 long a1 = 1L;
533 long b1 = 0L;
534 while (b != 0L) {
535 long q = a / b;
536 long r = a % b;
537 a = b;
538 b = r;
539 long r1 = a1 - q * b1;
540 a1 = b1;
541 b1 = r1;
542 }
543 if (a1 < 0L) {
544 a1 += S;
545 }
546 ret[0] = a;
547 ret[1] = a1;
548 return ret;
549 }
550
551
552 /**
553 * Long modular inverse.
554 * @param T long.
555 * @param m long.
556 * @return a with with a*T = 1 mod m.
557 */
558 public long modInverse(long T, long m) {
559 if (T == 0L) {
560 throw new NotInvertibleException("zero is not invertible");
561 }
562 long[] hegcd = hegcd(T, m);
563 long a = hegcd[0];
564 if (!(a == 1L || a == -1L)) { // gcd != 1
565 throw new ModularNotInvertibleException("element not invertible, gcd != 1",
566 new BigInteger(m),new BigInteger(a),new BigInteger(m/a));
567 }
568 long b = hegcd[1];
569 if (b == 0L) { // when m divides this, e.g. m.isUnit()
570 throw new NotInvertibleException("element not invertible, divisible by modul");
571 }
572 if (b < 0L) {
573 b += m;
574 }
575 return b;
576 }
577
578 }