[PING] [9] RFR of 5100935: No way to access the 64-bit integer multiplication of 64-bit CPUs efficiently

[Brian Burkhalter]

Hello Andrew,

Thank you for your comments. I went ahead and integrated the existing code as reviewed but created a new issue https://bugs.openjdk.java.net/browse/JDK-8157485 to track the possible improvement you suggested. Thanks for citing the appropriate reference material as well.

Cheers,

Brian

On May 19, 2016, at 2:44 AM, Andrew Haley <aph at redhat.com> wrote:

> This is described as being to help RSA, etc., but it will be very hard
> to use for that purpose without an add with carry.  There are many ways
> to do the product, but a simple version of the core is like this:
> 
>   for i=0 to s-1
>       C := 0
>       for j=0 to s-1
>           (C,S) := t[i+j] + a[j] * b[i] + C
>           t[i+j] := S
>       t[i+s] := C
> 
>   for i=0 to s-1
>       C := 0
>       m := t i *n' 0 mod W
>       for j=0 to s-1
>           (C,S) := t[i+j] + m*n[j] + C
>           t[i+j] := S
>       ADD(t[i+s],C)
> 
> ... the result is in the carry flag and t .  The logic in the x86
> version of SharedRuntime::montgomery_multiply uses a primitive which
> multiplies two longs and accumulates the result into a triple-length
> sum.  x86 can do this in four instructions.  I guess a primitive like
> this will fit nicely with value types, but I'm not sure how it's
> possible to do this with Java today.
> 
> (My apologies: I'm sure you know this already, but I didn't think it
> was wise not to say anything.)
> 
> Andrew.
> 
> [Algorithm from http://koclab.cs.ucsb.edu/docs/koc/j37.pdf]