1 /* 2 * Copyright (c) 2018, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package sun.security.util.math.intpoly; 27 28 import sun.security.util.math.*; 29 30 import java.math.BigInteger; 31 import java.nio.ByteBuffer; 32 import java.nio.ByteOrder; 33 import java.util.Arrays; 34 35 /** 36 * A large number polynomial representation using sparse limbs of signed 37 * long (64-bit) values. Limb values will always fit within a long, so inputs 38 * to multiplication must be less than 32 bits. All IntegerPolynomial 39 * implementations allow at most one addition before multiplication. Additions 40 * after that will result in an ArithmeticException. 41 * 42 * The following element operations are branch-free for all subclasses: 43 * 44 * fixed 45 * mutable 46 * add 47 * additiveInverse 48 * multiply 49 * square 50 * subtract 51 * conditionalSwapWith 52 * setValue (may branch on high-order byte parameter only) 53 * setSum 54 * setDifference 55 * setProduct 56 * setSquare 57 * addModPowerTwo 58 * asByteArray 59 * 60 * All other operations may branch in some subclasses. 61 * 62 */ 63 64 public abstract class IntegerPolynomial implements IntegerFieldModuloP { 65 66 protected static final BigInteger TWO = BigInteger.valueOf(2); 67 68 protected final int numLimbs; 69 private final BigInteger modulus; 70 protected final int bitsPerLimb; 71 private final long[] posModLimbs; 72 private final int maxAdds; 73 74 /** 75 * Reduce an IntegerPolynomial representation (a) and store the result 76 * in a. Requires that a.length == numLimbs. 77 */ reduce(long[] a)78 protected abstract void reduce(long[] a); 79 80 /** 81 * Multiply an IntegerPolynomial representation (a) with a long (b) and 82 * store the result in an IntegerPolynomial representation in a. Requires 83 * that a.length == numLimbs. 84 */ multByInt(long[] a, long b)85 protected void multByInt(long[] a, long b) { 86 for (int i = 0; i < a.length; i++) { 87 a[i] *= b; 88 } 89 reduce(a); 90 } 91 92 /** 93 * Multiply two IntegerPolynomial representations (a and b) and store the 94 * result in an IntegerPolynomial representation (r). Requires that 95 * a.length == b.length == r.length == numLimbs. It is allowed for a and r 96 * to be the same array. 97 */ mult(long[] a, long[] b, long[] r)98 protected abstract void mult(long[] a, long[] b, long[] r); 99 100 /** 101 * Multiply an IntegerPolynomial representation (a) with itself and store 102 * the result in an IntegerPolynomialRepresentation (r). Requires that 103 * a.length == r.length == numLimbs. It is allowed for a and r 104 * to be the same array. 105 */ square(long[] a, long[] r)106 protected abstract void square(long[] a, long[] r); 107 IntegerPolynomial(int bitsPerLimb, int numLimbs, int maxAdds, BigInteger modulus)108 IntegerPolynomial(int bitsPerLimb, 109 int numLimbs, 110 int maxAdds, 111 BigInteger modulus) { 112 113 114 this.numLimbs = numLimbs; 115 this.modulus = modulus; 116 this.bitsPerLimb = bitsPerLimb; 117 this.maxAdds = maxAdds; 118 119 posModLimbs = setPosModLimbs(); 120 } 121 setPosModLimbs()122 private long[] setPosModLimbs() { 123 long[] result = new long[numLimbs]; 124 setLimbsValuePositive(modulus, result); 125 return result; 126 } 127 getNumLimbs()128 protected int getNumLimbs() { 129 return numLimbs; 130 } 131 getMaxAdds()132 public int getMaxAdds() { 133 return maxAdds; 134 } 135 136 @Override getSize()137 public BigInteger getSize() { 138 return modulus; 139 } 140 141 @Override get0()142 public ImmutableElement get0() { 143 return new ImmutableElement(false); 144 } 145 146 @Override get1()147 public ImmutableElement get1() { 148 return new ImmutableElement(true); 149 } 150 151 @Override getElement(BigInteger v)152 public ImmutableElement getElement(BigInteger v) { 153 return new ImmutableElement(v); 154 } 155 156 @Override getSmallValue(int value)157 public SmallValue getSmallValue(int value) { 158 int maxMag = 1 << (bitsPerLimb - 1); 159 if (Math.abs(value) >= maxMag) { 160 throw new IllegalArgumentException( 161 "max magnitude is " + maxMag); 162 } 163 return new Limb(value); 164 } 165 166 /** 167 * This version of encode takes a ByteBuffer that is properly ordered, and 168 * may extract larger values (e.g. long) from the ByteBuffer for better 169 * performance. The implementation below only extracts bytes from the 170 * buffer, but this method may be overridden in field-specific 171 * implementations. 172 */ encode(ByteBuffer buf, int length, byte highByte, long[] result)173 protected void encode(ByteBuffer buf, int length, byte highByte, 174 long[] result) { 175 176 int numHighBits = 32 - Integer.numberOfLeadingZeros(highByte); 177 int numBits = 8 * length + numHighBits; 178 int requiredLimbs = (numBits + bitsPerLimb - 1) / bitsPerLimb; 179 if (requiredLimbs > numLimbs) { 180 long[] temp = new long[requiredLimbs]; 181 encodeSmall(buf, length, highByte, temp); 182 // encode does a full carry/reduce 183 System.arraycopy(temp, 0, result, 0, result.length); 184 } else { 185 encodeSmall(buf, length, highByte, result); 186 } 187 } 188 encodeSmall(ByteBuffer buf, int length, byte highByte, long[] result)189 protected void encodeSmall(ByteBuffer buf, int length, byte highByte, 190 long[] result) { 191 192 int limbIndex = 0; 193 long curLimbValue = 0; 194 int bitPos = 0; 195 for (int i = 0; i < length; i++) { 196 long curV = buf.get() & 0xFF; 197 198 if (bitPos + 8 >= bitsPerLimb) { 199 int bitsThisLimb = bitsPerLimb - bitPos; 200 curLimbValue += (curV & (0xFF >> (8 - bitsThisLimb))) << bitPos; 201 result[limbIndex++] = curLimbValue; 202 curLimbValue = curV >> bitsThisLimb; 203 bitPos = 8 - bitsThisLimb; 204 } 205 else { 206 curLimbValue += curV << bitPos; 207 bitPos += 8; 208 } 209 } 210 211 // one more for the high byte 212 if (highByte != 0) { 213 long curV = highByte & 0xFF; 214 if (bitPos + 8 >= bitsPerLimb) { 215 int bitsThisLimb = bitsPerLimb - bitPos; 216 curLimbValue += (curV & (0xFF >> (8 - bitsThisLimb))) << bitPos; 217 result[limbIndex++] = curLimbValue; 218 curLimbValue = curV >> bitsThisLimb; 219 } 220 else { 221 curLimbValue += curV << bitPos; 222 } 223 } 224 225 if (limbIndex < result.length) { 226 result[limbIndex++] = curLimbValue; 227 } 228 Arrays.fill(result, limbIndex, result.length, 0); 229 230 postEncodeCarry(result); 231 } 232 encode(byte[] v, int offset, int length, byte highByte, long[] result)233 protected void encode(byte[] v, int offset, int length, byte highByte, 234 long[] result) { 235 236 ByteBuffer buf = ByteBuffer.wrap(v, offset, length); 237 buf.order(ByteOrder.LITTLE_ENDIAN); 238 encode(buf, length, highByte, result); 239 } 240 241 // Encode does not produce compressed limbs. A simplified carry/reduce 242 // operation can be used to compress the limbs. postEncodeCarry(long[] v)243 protected void postEncodeCarry(long[] v) { 244 reduce(v); 245 } 246 getElement(byte[] v, int offset, int length, byte highByte)247 public ImmutableElement getElement(byte[] v, int offset, int length, 248 byte highByte) { 249 250 long[] result = new long[numLimbs]; 251 252 encode(v, offset, length, highByte, result); 253 254 return new ImmutableElement(result, 0); 255 } 256 evaluate(long[] limbs)257 protected BigInteger evaluate(long[] limbs) { 258 BigInteger result = BigInteger.ZERO; 259 for (int i = limbs.length - 1; i >= 0; i--) { 260 result = result.shiftLeft(bitsPerLimb) 261 .add(BigInteger.valueOf(limbs[i])); 262 } 263 return result.mod(modulus); 264 } 265 carryValue(long x)266 protected long carryValue(long x) { 267 // compressing carry operation 268 // if large positive number, carry one more to make it negative 269 // if large negative number (closer to zero), carry one fewer 270 return (x + (1 << (bitsPerLimb - 1))) >> bitsPerLimb; 271 } 272 carry(long[] limbs, int start, int end)273 protected void carry(long[] limbs, int start, int end) { 274 275 for (int i = start; i < end; i++) { 276 277 long carry = carryOut(limbs, i); 278 limbs[i + 1] += carry; 279 } 280 } 281 carry(long[] limbs)282 protected void carry(long[] limbs) { 283 284 carry(limbs, 0, limbs.length - 1); 285 } 286 287 /** 288 * Carry out of the specified position and return the carry value. 289 */ carryOut(long[] limbs, int index)290 protected long carryOut(long[] limbs, int index) { 291 long carry = carryValue(limbs[index]); 292 limbs[index] -= (carry << bitsPerLimb); 293 return carry; 294 } 295 setLimbsValue(BigInteger v, long[] limbs)296 private void setLimbsValue(BigInteger v, long[] limbs) { 297 // set all limbs positive, and then carry 298 setLimbsValuePositive(v, limbs); 299 carry(limbs); 300 } 301 setLimbsValuePositive(BigInteger v, long[] limbs)302 protected void setLimbsValuePositive(BigInteger v, long[] limbs) { 303 BigInteger mod = BigInteger.valueOf(1 << bitsPerLimb); 304 for (int i = 0; i < limbs.length; i++) { 305 limbs[i] = v.mod(mod).longValue(); 306 v = v.shiftRight(bitsPerLimb); 307 } 308 } 309 310 /** 311 * Carry out of the last limb and reduce back in. This method will be 312 * called as part of the "finalReduce" operation that puts the 313 * representation into a fully-reduced form. It is representation- 314 * specific, because representations have different amounts of empty 315 * space in the high-order limb. Requires that limbs.length=numLimbs. 316 */ finalCarryReduceLast(long[] limbs)317 protected abstract void finalCarryReduceLast(long[] limbs); 318 319 /** 320 * Convert reduced limbs into a number between 0 and MODULUS-1. 321 * Requires that limbs.length == numLimbs. This method only works if the 322 * modulus has at most three terms. 323 */ finalReduce(long[] limbs)324 protected void finalReduce(long[] limbs) { 325 326 // This method works by doing several full carry/reduce operations. 327 // Some representations have extra high bits, so the carry/reduce out 328 // of the high position is implementation-specific. The "unsigned" 329 // carry operation always carries some (negative) value out of a 330 // position occupied by a negative value. So after a number of 331 // passes, all negative values are removed. 332 333 // The first pass may leave a negative value in the high position, but 334 // this only happens if something was carried out of the previous 335 // position. So the previous position must have a "small" value. The 336 // next full carry is guaranteed not to carry out of that position. 337 338 for (int pass = 0; pass < 2; pass++) { 339 // unsigned carry out of last position and reduce in to 340 // first position 341 finalCarryReduceLast(limbs); 342 343 // unsigned carry on all positions 344 long carry = 0; 345 for (int i = 0; i < numLimbs - 1; i++) { 346 limbs[i] += carry; 347 carry = limbs[i] >> bitsPerLimb; 348 limbs[i] -= carry << bitsPerLimb; 349 } 350 limbs[numLimbs - 1] += carry; 351 } 352 353 // Limbs are positive and all less than 2^bitsPerLimb, and the 354 // high-order limb may be even smaller due to the representation- 355 // specific carry/reduce out of the high position. 356 // The value may still be greater than the modulus. 357 // Subtract the max limb values only if all limbs end up non-negative 358 // This only works if there is at most one position where posModLimbs 359 // is less than 2^bitsPerLimb - 1 (not counting the high-order limb, 360 // if it has extra bits that are cleared by finalCarryReduceLast). 361 int smallerNonNegative = 1; 362 long[] smaller = new long[numLimbs]; 363 for (int i = numLimbs - 1; i >= 0; i--) { 364 smaller[i] = limbs[i] - posModLimbs[i]; 365 // expression on right is 1 if smaller[i] is nonnegative, 366 // 0 otherwise 367 smallerNonNegative *= (int) (smaller[i] >> 63) + 1; 368 } 369 conditionalSwap(smallerNonNegative, limbs, smaller); 370 371 } 372 373 /** 374 * Decode the value in v and store it in dst. Requires that v is final 375 * reduced. I.e. all limbs in [0, 2^bitsPerLimb) and value in [0, modulus). 376 */ decode(long[] v, byte[] dst, int offset, int length)377 protected void decode(long[] v, byte[] dst, int offset, int length) { 378 379 int nextLimbIndex = 0; 380 long curLimbValue = v[nextLimbIndex++]; 381 int bitPos = 0; 382 for (int i = 0; i < length; i++) { 383 384 int dstIndex = i + offset; 385 if (bitPos + 8 >= bitsPerLimb) { 386 dst[dstIndex] = (byte) curLimbValue; 387 curLimbValue = 0; 388 if (nextLimbIndex < v.length) { 389 curLimbValue = v[nextLimbIndex++]; 390 } 391 int bitsAdded = bitsPerLimb - bitPos; 392 int bitsLeft = 8 - bitsAdded; 393 394 dst[dstIndex] += (curLimbValue & (0xFF >> bitsAdded)) 395 << bitsAdded; 396 curLimbValue >>= bitsLeft; 397 bitPos = bitsLeft; 398 } else { 399 dst[dstIndex] = (byte) curLimbValue; 400 curLimbValue >>= 8; 401 bitPos += 8; 402 } 403 } 404 } 405 406 /** 407 * Add two IntegerPolynomial representations (a and b) and store the result 408 * in an IntegerPolynomialRepresentation (dst). Requires that 409 * a.length == b.length == dst.length. It is allowed for a and 410 * dst to be the same array. 411 */ addLimbs(long[] a, long[] b, long[] dst)412 protected void addLimbs(long[] a, long[] b, long[] dst) { 413 for (int i = 0; i < dst.length; i++) { 414 dst[i] = a[i] + b[i]; 415 } 416 } 417 418 /** 419 * Branch-free conditional assignment of b to a. Requires that set is 0 or 420 * 1, and that a.length == b.length. If set==0, then the values of a and b 421 * will be unchanged. If set==1, then the values of b will be assigned to a. 422 * The behavior is undefined if swap has any value other than 0 or 1. 423 */ conditionalAssign(int set, long[] a, long[] b)424 protected static void conditionalAssign(int set, long[] a, long[] b) { 425 int maskValue = 0 - set; 426 for (int i = 0; i < a.length; i++) { 427 long dummyLimbs = maskValue & (a[i] ^ b[i]); 428 a[i] = dummyLimbs ^ a[i]; 429 } 430 } 431 432 /** 433 * Branch-free conditional swap of a and b. Requires that swap is 0 or 1, 434 * and that a.length == b.length. If swap==0, then the values of a and b 435 * will be unchanged. If swap==1, then the values of a and b will be 436 * swapped. The behavior is undefined if swap has any value other than 437 * 0 or 1. 438 */ conditionalSwap(int swap, long[] a, long[] b)439 protected static void conditionalSwap(int swap, long[] a, long[] b) { 440 int maskValue = 0 - swap; 441 for (int i = 0; i < a.length; i++) { 442 long dummyLimbs = maskValue & (a[i] ^ b[i]); 443 a[i] = dummyLimbs ^ a[i]; 444 b[i] = dummyLimbs ^ b[i]; 445 } 446 } 447 448 /** 449 * Stores the reduced, little-endian value of limbs in result. 450 */ limbsToByteArray(long[] limbs, byte[] result)451 protected void limbsToByteArray(long[] limbs, byte[] result) { 452 453 long[] reducedLimbs = limbs.clone(); 454 finalReduce(reducedLimbs); 455 456 decode(reducedLimbs, result, 0, result.length); 457 } 458 459 /** 460 * Add the reduced number corresponding to limbs and other, and store 461 * the low-order bytes of the sum in result. Requires that 462 * limbs.length==other.length. The result array may have any length. 463 */ addLimbsModPowerTwo(long[] limbs, long[] other, byte[] result)464 protected void addLimbsModPowerTwo(long[] limbs, long[] other, 465 byte[] result) { 466 467 long[] reducedOther = other.clone(); 468 long[] reducedLimbs = limbs.clone(); 469 finalReduce(reducedOther); 470 finalReduce(reducedLimbs); 471 472 addLimbs(reducedLimbs, reducedOther, reducedLimbs); 473 474 // may carry out a value which can be ignored 475 long carry = 0; 476 for (int i = 0; i < numLimbs; i++) { 477 reducedLimbs[i] += carry; 478 carry = reducedLimbs[i] >> bitsPerLimb; 479 reducedLimbs[i] -= carry << bitsPerLimb; 480 } 481 482 decode(reducedLimbs, result, 0, result.length); 483 } 484 485 private abstract class Element implements IntegerModuloP { 486 487 protected long[] limbs; 488 protected int numAdds; 489 Element(BigInteger v)490 public Element(BigInteger v) { 491 limbs = new long[numLimbs]; 492 setValue(v); 493 } 494 Element(boolean v)495 public Element(boolean v) { 496 this.limbs = new long[numLimbs]; 497 this.limbs[0] = v ? 1l : 0l; 498 this.numAdds = 0; 499 } 500 Element(long[] limbs, int numAdds)501 private Element(long[] limbs, int numAdds) { 502 this.limbs = limbs; 503 this.numAdds = numAdds; 504 } 505 setValue(BigInteger v)506 private void setValue(BigInteger v) { 507 setLimbsValue(v, limbs); 508 this.numAdds = 0; 509 } 510 511 @Override getField()512 public IntegerFieldModuloP getField() { 513 return IntegerPolynomial.this; 514 } 515 516 @Override asBigInteger()517 public BigInteger asBigInteger() { 518 return evaluate(limbs); 519 } 520 521 @Override mutable()522 public MutableElement mutable() { 523 return new MutableElement(limbs.clone(), numAdds); 524 } 525 isSummand()526 protected boolean isSummand() { 527 return numAdds < maxAdds; 528 } 529 530 @Override add(IntegerModuloP genB)531 public ImmutableElement add(IntegerModuloP genB) { 532 533 Element b = (Element) genB; 534 if (!(isSummand() && b.isSummand())) { 535 throw new ArithmeticException("Not a valid summand"); 536 } 537 538 long[] newLimbs = new long[limbs.length]; 539 for (int i = 0; i < limbs.length; i++) { 540 newLimbs[i] = limbs[i] + b.limbs[i]; 541 } 542 543 int newNumAdds = Math.max(numAdds, b.numAdds) + 1; 544 return new ImmutableElement(newLimbs, newNumAdds); 545 } 546 547 @Override additiveInverse()548 public ImmutableElement additiveInverse() { 549 550 long[] newLimbs = new long[limbs.length]; 551 for (int i = 0; i < limbs.length; i++) { 552 newLimbs[i] = -limbs[i]; 553 } 554 555 ImmutableElement result = new ImmutableElement(newLimbs, numAdds); 556 return result; 557 } 558 cloneLow(long[] limbs)559 protected long[] cloneLow(long[] limbs) { 560 long[] newLimbs = new long[numLimbs]; 561 copyLow(limbs, newLimbs); 562 return newLimbs; 563 } copyLow(long[] limbs, long[] out)564 protected void copyLow(long[] limbs, long[] out) { 565 System.arraycopy(limbs, 0, out, 0, out.length); 566 } 567 568 @Override multiply(IntegerModuloP genB)569 public ImmutableElement multiply(IntegerModuloP genB) { 570 571 Element b = (Element) genB; 572 573 long[] newLimbs = new long[limbs.length]; 574 mult(limbs, b.limbs, newLimbs); 575 return new ImmutableElement(newLimbs, 0); 576 } 577 578 @Override square()579 public ImmutableElement square() { 580 long[] newLimbs = new long[limbs.length]; 581 IntegerPolynomial.this.square(limbs, newLimbs); 582 return new ImmutableElement(newLimbs, 0); 583 } 584 addModPowerTwo(IntegerModuloP arg, byte[] result)585 public void addModPowerTwo(IntegerModuloP arg, byte[] result) { 586 587 Element other = (Element) arg; 588 if (!(isSummand() && other.isSummand())) { 589 throw new ArithmeticException("Not a valid summand"); 590 } 591 addLimbsModPowerTwo(limbs, other.limbs, result); 592 } 593 asByteArray(byte[] result)594 public void asByteArray(byte[] result) { 595 if (!isSummand()) { 596 throw new ArithmeticException("Not a valid summand"); 597 } 598 limbsToByteArray(limbs, result); 599 } 600 } 601 602 protected class MutableElement extends Element 603 implements MutableIntegerModuloP { 604 MutableElement(long[] limbs, int numAdds)605 protected MutableElement(long[] limbs, int numAdds) { 606 super(limbs, numAdds); 607 } 608 609 @Override fixed()610 public ImmutableElement fixed() { 611 return new ImmutableElement(limbs.clone(), numAdds); 612 } 613 614 @Override conditionalSet(IntegerModuloP b, int set)615 public void conditionalSet(IntegerModuloP b, int set) { 616 617 Element other = (Element) b; 618 619 conditionalAssign(set, limbs, other.limbs); 620 numAdds = other.numAdds; 621 } 622 623 @Override conditionalSwapWith(MutableIntegerModuloP b, int swap)624 public void conditionalSwapWith(MutableIntegerModuloP b, int swap) { 625 626 MutableElement other = (MutableElement) b; 627 628 conditionalSwap(swap, limbs, other.limbs); 629 int numAddsTemp = numAdds; 630 numAdds = other.numAdds; 631 other.numAdds = numAddsTemp; 632 } 633 634 635 @Override setValue(IntegerModuloP v)636 public MutableElement setValue(IntegerModuloP v) { 637 Element other = (Element) v; 638 639 System.arraycopy(other.limbs, 0, limbs, 0, other.limbs.length); 640 numAdds = other.numAdds; 641 return this; 642 } 643 644 @Override setValue(byte[] arr, int offset, int length, byte highByte)645 public MutableElement setValue(byte[] arr, int offset, 646 int length, byte highByte) { 647 648 encode(arr, offset, length, highByte, limbs); 649 this.numAdds = 0; 650 651 return this; 652 } 653 654 @Override setValue(ByteBuffer buf, int length, byte highByte)655 public MutableElement setValue(ByteBuffer buf, int length, 656 byte highByte) { 657 658 encode(buf, length, highByte, limbs); 659 numAdds = 0; 660 661 return this; 662 } 663 664 @Override setProduct(IntegerModuloP genB)665 public MutableElement setProduct(IntegerModuloP genB) { 666 Element b = (Element) genB; 667 mult(limbs, b.limbs, limbs); 668 numAdds = 0; 669 return this; 670 } 671 672 @Override setProduct(SmallValue v)673 public MutableElement setProduct(SmallValue v) { 674 int value = ((Limb) v).value; 675 multByInt(limbs, value); 676 numAdds = 0; 677 return this; 678 } 679 680 @Override setSum(IntegerModuloP genB)681 public MutableElement setSum(IntegerModuloP genB) { 682 683 Element b = (Element) genB; 684 if (!(isSummand() && b.isSummand())) { 685 throw new ArithmeticException("Not a valid summand"); 686 } 687 688 for (int i = 0; i < limbs.length; i++) { 689 limbs[i] = limbs[i] + b.limbs[i]; 690 } 691 692 numAdds = Math.max(numAdds, b.numAdds) + 1; 693 return this; 694 } 695 696 @Override setDifference(IntegerModuloP genB)697 public MutableElement setDifference(IntegerModuloP genB) { 698 699 Element b = (Element) genB; 700 if (!(isSummand() && b.isSummand())) { 701 throw new ArithmeticException("Not a valid summand"); 702 } 703 704 for (int i = 0; i < limbs.length; i++) { 705 limbs[i] = limbs[i] - b.limbs[i]; 706 } 707 708 numAdds = Math.max(numAdds, b.numAdds) + 1; 709 return this; 710 } 711 712 @Override setSquare()713 public MutableElement setSquare() { 714 IntegerPolynomial.this.square(limbs, limbs); 715 numAdds = 0; 716 return this; 717 } 718 719 @Override setAdditiveInverse()720 public MutableElement setAdditiveInverse() { 721 722 for (int i = 0; i < limbs.length; i++) { 723 limbs[i] = -limbs[i]; 724 } 725 return this; 726 } 727 728 @Override setReduced()729 public MutableElement setReduced() { 730 731 reduce(limbs); 732 numAdds = 0; 733 return this; 734 } 735 } 736 737 class ImmutableElement extends Element implements ImmutableIntegerModuloP { 738 ImmutableElement(BigInteger v)739 protected ImmutableElement(BigInteger v) { 740 super(v); 741 } 742 ImmutableElement(boolean v)743 protected ImmutableElement(boolean v) { 744 super(v); 745 } 746 ImmutableElement(long[] limbs, int numAdds)747 protected ImmutableElement(long[] limbs, int numAdds) { 748 super(limbs, numAdds); 749 } 750 751 @Override fixed()752 public ImmutableElement fixed() { 753 return this; 754 } 755 756 } 757 758 class Limb implements SmallValue { 759 int value; 760 Limb(int value)761 Limb(int value) { 762 this.value = value; 763 } 764 } 765 766 767 } 768