[phobos] Issue6244, implementing 'powmod'

[Alex Jercaianu via phobos]

Hello,

I am trying to implement the 'powmod' functionality as described
here [1].

The issue that I am having is that the algorithm uses
multiplications which can cause overflow.
If the base is 32 bits, then I can use 64 bit variables to handle
the result of multiplications, however the problem arises if the
base is 64 bit.

The pseudocode would look the following:

while (exponent > 0)
{
if (exponent & 1)
{
result = mulmod(result, base, modulus);
}

base = mulmod(base, base, modulus);
exponent >>= 1;
}

return result;

The problem that I am facing is with the 'mulmod' function which
should do multiplication and modulo of the result without
overflow problems.

Do you think that it would be a good idea to limit the base to 32
bits?
Or does D have any facility similar to 'mulmod'?

Thanks,
Alex

[1] -
https://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method

[Alex Jercaianu via phobos]

Hello,

I am trying to implement the 'powmod' functionality as described
here [1].

The issue that I am having is that the algorithm uses
multiplications which can cause overflow.
If the base is 32 bits, then I can use 64 bit variables to handle
the result of multiplications, however the problem arises if the
base is 64 bit.

The pseudocode would look the following:

while (exponent > 0)
{
if (exponent & 1)
{
result = mulmod(result, base, modulus);
}

base = mulmod(base, base, modulus);
exponent >>= 1;
}

return result;

The problem that I am facing is with the 'mulmod' function which
should do multiplication and modulo of the result without
overflow problems.

Do you think that it would be a good idea to limit the base to 32
bits?
Or does D have any facility similar to 'mulmod'?

Thanks,
Alex

[1] -
https://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method

[Andrei Alexandrescu via phobos]

A possible solution is to implement mul128 using primitives for 32- and
64-bit numbers. A possible signature would be:

void mul128(ulong a, ulong b, out ulong lo, out ulong hi);

The technique is to do the multiplication "by hand" as if you had two
numbers having two digits each. You obtain a 4-digit number.

Consider the two-digit decimal numbers ab and cd, for example 43 and 65.
Then the multiplication "by hand" is:

(10a + b) * (10c + d) = 100ac + 10(ad + bc) + bd

Since a, b, c, d are single digits it follows we only need 1-digit
multiplication and addition with carry. Now of course our base is not 10
but 2^^32, so we multiply two numbers, each having two 32-bit "digits"
and we get 128 bits worth of result.

mul128() would be a generally useful function to put in druntime. I
think someone on the general forum has implemented it already, you may
want to ask.


Andrei

Post by Alex Jercaianu via phobos
Hello,
I am trying to implement the 'powmod' functionality as described here [1].
The issue that I am having is that the algorithm uses multiplications
which can cause overflow.
If the base is 32 bits, then I can use 64 bit variables to handle the
result of multiplications, however the problem arises if the base is 64
bit.
while (exponent > 0)
{
    if (exponent & 1)
    {
        result = mulmod(result, base, modulus);
    }
    base = mulmod(base, base, modulus);
    exponent >>= 1;
}
return result;
The problem that I am facing is with the 'mulmod' function which should
do multiplication and modulo of the result without overflow problems.
Do you think that it would be a good idea to limit the base to 32 bits?
Or does D have any facility similar to 'mulmod'?
Thanks,
Alex
[1] -
https://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method
_______________________________________________
phobos mailing list
http://lists.puremagic.com/mailman/listinfo/phobos

[Alex Jercaianu via phobos]

On Tuesday, 3 October 2017 at 01:42:44 UTC, Andrei Alexandrescu

Post by Andrei Alexandrescu via phobos
A possible solution is to implement mul128 using primitives for
void mul128(ulong a, ulong b, out ulong lo, out ulong hi);
The technique is to do the multiplication "by hand" as if you
had two numbers having two digits each. You obtain a 4-digit
number.
Consider the two-digit decimal numbers ab and cd, for example
(10a + b) * (10c + d) = 100ac + 10(ad + bc) + bd
Since a, b, c, d are single digits it follows we only need
1-digit multiplication and addition with carry. Now of course
our base is not 10 but 2^^32, so we multiply two numbers, each
having two 32-bit "digits" and we get 128 bits worth of result.
mul128() would be a generally useful function to put in
druntime. I think someone on the general forum has implemented
it already, you may want to ask.
Andrei

Thanks for the suggestion!
I think I have also found a way to implement 'mulmod' without'
mul128'.
Is overflow well defined for unsigned types in D?
For example, (MAX_UINT + 1) equals 0 for unsigned types?

I will also come back with a 'mul128' implementation, since there
is none available for the moment in the standard library.

Thanks,
Alex