On Fri, 23 Sep 2022 07:39:07 GMT, Xue-Lei Andrew Fan <xue...@openjdk.org> wrote:
> Limb values will always fit within a long, so inputs to multiplication must
> be less than 32 bits. *All IntegerPolynomial implementations allow at most
> one addition before multiplication*. Additions after that will result in an
> ArithmeticException.
The highlighted part of the comment is incorrect; IntegerPolynomial allows at
most 2^maxAdds-1 additions, and maxAdds in your patch is 2:
static FieldParams P256 = new FieldParams(
"IntegerPolynomialP256", 29, 9, 2 /*maxAdds*/, 256,
see the implementation of add (removed the irrelevant stuff):
protected boolean isSummand() {
return numAdds < maxAdds;
}
public ImmutableElement add(IntegerModuloP genB) {
if (!(isSummand() && b.isSummand())) {
throw new ArithmeticException("Not a valid summand");
}
int newNumAdds = Math.max(numAdds, b.numAdds) + 1;
}
if you change maxAdds to 1, you'll start getting exceptions:
java.lang.ArithmeticException: Not a valid summand
at
java.base/sun.security.util.math.intpoly.IntegerPolynomial$MutableElement.setDifference(IntegerPolynomial.java:731)
at
java.base/sun.security.util.math.intpoly.IntegerPolynomial$MutableElement.setDifference(IntegerPolynomial.java:630)
at
jdk.crypto.ec/sun.security.ec.ECOperations.setSum(ECOperations.java:375)
at
jdk.crypto.ec/sun.security.ec.ECOperations.multiply(ECOperations.java:261)
which means that we perform at least 2 additions without doing a reduce (see
[ECOperations.java:375](https://github.com/openjdk/jdk/blob/a5e0f7758ca1cdf28e221126fd9a543570bfcb7d/src/jdk.crypto.ec/share/classes/sun/security/ec/ECOperations.java#L375)).
So, we can multiply 29+2 = 31 bit limbs. Then in multiplication you have:
protected void mult(long[] a, long[] b, long[] r) {
long c8 = (a[0] * b[8]) + (a[1] * b[7]) + (a[2] * b[6]) + (a[3] * b[5])
+ (a[4] * b[4]) + (a[5] * b[3]) + (a[6] * b[2]) + (a[7] * b[1]) + (a[8] * b[0]);
addition of 9 multiplication results; 31+31+lg 9 > 64.
-------------
PR: https://git.openjdk.org/jdk/pull/10398
