# Do we need an unsigned multiplyHigh?

Mon Sep 25 17:21:55 UTC 2017

```I agree that an unsigned multiplyHigh would be useful for crypto
purposes, and we should consider adding it. Of course, I would much
rather have multiply operations that return both 64-bit parts of the
result, but that is going to be hard to do well without value types. So
it would be nice to have something like this in the meantime.

If we are going to add this operation, it should probably be added along
with an intrinsic. I think the Java code can simply factor out the else
branch from the existing multiplyHigh code. This way,
unsignedMultiplyHigh will be at least as fast as multiplyHigh, whether
the intrinsic implementation is available or not.

If possible, the implementation of this operation should not branch on
either operand. This would make it more widely useful for constant-time
crypto implementations. Though this property would need to go into the
spec in order for constant-time crypto code to use this method, and I
don't know how reasonable it is to put something like this in the spec.

Side note: at the moment, I am using signed arithmetic in prototypes for
Poly1305, X25519, and EdDSA, partially due to lack of support for
unsigned operations like this one. I don't think having
unsignedMultiplyHigh would, on its own, convince me to use an unsigned
representation, but the forces are different for each
algorithm/implementation.

On 9/25/2017 10:50 AM, Andrew Haley wrote:
> We now have a multiplyHigh intrinsic, but it is signed.  Unsigned
> multiplyHigh is in general a more useful primitive for crypto than
> signed, and I wonder if we need an intrinsic for that as well.  I've
> looked at cooking up an unsigned multiplyHigh in Java, and I think the
> fastest way is this:
>
>      private static final long unsignedMultiplyHigh(long a, long b) {
>          long result = Math.multiplyHigh(a, b);
>          if (a < 0)  result += b;
>          if (b < 0)  result += a;
>          // Can also be written as:
>          // result += (a >> 63) & b;
>          // result += (b >> 63) & a;
>          return result;
>      }
>
> It's still about 50% slower than the signed multiplyHigh, though.
> Thoughts?
>

```