64 bit multiplication (RSA key generation)
Author Message 64 bit multiplication (RSA key generation)

Hi,

I'm currently doing a university assignment and I need to be able to
implement 64 bit multiplication.  As such I need to hold a 128 bit
number.  I know that I need to use long long to store the 64 bit
numbers, but as a newbie to this I am not sure how to do the
multiplication.  Can anyone help me with this either pointing me to a
tutorial, or just some general help?

Jim

Sun, 18 Sep 2005 21:06:07 GMT  64 bit multiplication (RSA key generation)

Quote:
>I'm currently doing a university assignment and I need to be able to
>implement 64 bit multiplication.  As such I need to hold a 128 bit
>number.  I know that I need to use long long to store the 64 bit
>numbers, but as a newbie to this I am not sure how to do the
>multiplication.  Can anyone help me with this either pointing me to a
>tutorial, or just some general help?

Assuming that (ULONG_MAX+1) ** 2 == (ULLONG_MAX+1), a *naive* analysis
of the problem goes like this:

a = ah * (ULONG_MAX+1) + al
b = bh * (ULONG_MAX+1) + bl
a * b = ah * bh * (ULONG_MAX+1)**2 + (ah * bl + al * bh) * (ULONG_MAX+1) +
+ al * bl

This means that the lower part of the result consists of al * bl + the
lower half of (ah * bl + al * bh) multiplied by (ULONG_MAX+1).

The higher half of the result consists from ah * bh +
the upper half of (ah * bl + al * bh) + the carry generated when
computing the lower half of the result.

A C program that implements this "algorithm" looks like this.  For
simplicity reasons, an unsigned long long is assumed to be a 64-bit type.

fangorn:~/tmp 312> cat test.c
#include <stdio.h>
#include <limits.h>

int main()
{
unsigned long long a = ULLONG_MAX, b = ULLONG_MAX;
unsigned long long ah = a >> 32, al = a & 0xffffffff;
unsigned long long bh = b >> 32, bl = b & 0xffffffff;
unsigned long long rl, rh;
unsigned long long ahbh, ahbl, albh, albl;
unsigned long long ahbl_upper, ahbl_lower, albh_upper, albh_lower;
unsigned long long carry = 0;

ahbh = ah * bh;
ahbl = ah * bl;
albh = al * bh;
albl = al * bl;

ahbl_lower = ahbl << 32;
ahbl_upper = ahbl >> 32;
albh_lower = albh << 32;
albh_upper = albh >> 32;

rl = albl;
if ((rl += ahbl_lower) < ahbl_lower) carry++;
if ((rl += albh_lower) < albh_lower) carry++;
rh = ahbh + ahbl_upper + albh_upper + carry;

printf ("%016llx%016llx %llx\n", rh, rl, (1ull*ULONG_MAX)*ULONG_MAX);
return 0;
}
fangorn:~/tmp 313> gcc -std=c99 test.c
fangorn:~/tmp 314> ./a.out
fffffffffffffffe0000000000000001 fffffffe00000001

For comparison, the program also displays the result of
ULONG_MAX * ULONG_MAX computed using unsigned long long arithmetic.

The purists can add the following macros to eliminate most of the "magic"
constants used in the code:

#define OFFSET ((sizeof(long long) * CHAR_BIT) / 2)
#define MASK   ((1ull << OFFSET) - 1)

The remaining assumption is that unsigned long long has an even number
of value bits and no padding bits.

Dan
--
Dan Pop
DESY Zeuthen, RZ group

Mon, 19 Sep 2005 00:18:50 GMT  64 bit multiplication (RSA key generation)
Thanks very much !!! :D
Quote:

> >I'm currently doing a university assignment and I need to be able to
> >implement 64 bit multiplication.  As such I need to hold a 128 bit
> >number.  I know that I need to use long long to store the 64 bit
> >numbers, but as a newbie to this I am not sure how to do the
> >multiplication.  Can anyone help me with this either pointing me to a
> >tutorial, or just some general help?

> Assuming that (ULONG_MAX+1) ** 2 == (ULLONG_MAX+1), a *naive* analysis
> of the problem goes like this:

> a = ah * (ULONG_MAX+1) + al
> b = bh * (ULONG_MAX+1) + bl
> a * b = ah * bh * (ULONG_MAX+1)**2 + (ah * bl + al * bh) * (ULONG_MAX+1) +
>       + al * bl

> This means that the lower part of the result consists of al * bl + the
> lower half of (ah * bl + al * bh) multiplied by (ULONG_MAX+1).

> The higher half of the result consists from ah * bh +
> the upper half of (ah * bl + al * bh) + the carry generated when
> computing the lower half of the result.

> A C program that implements this "algorithm" looks like this.  For
> simplicity reasons, an unsigned long long is assumed to be a 64-bit type.

>     fangorn:~/tmp 312> cat test.c
>     #include <stdio.h>
>     #include <limits.h>

>     int main()
>     {
>         unsigned long long a = ULLONG_MAX, b = ULLONG_MAX;
>         unsigned long long ah = a >> 32, al = a & 0xffffffff;
>         unsigned long long bh = b >> 32, bl = b & 0xffffffff;
>         unsigned long long rl, rh;
>         unsigned long long ahbh, ahbl, albh, albl;
>         unsigned long long ahbl_upper, ahbl_lower, albh_upper, albh_lower;
>         unsigned long long carry = 0;

>         ahbh = ah * bh;
>         ahbl = ah * bl;
>         albh = al * bh;
>         albl = al * bl;

>         ahbl_lower = ahbl << 32;
>         ahbl_upper = ahbl >> 32;
>         albh_lower = albh << 32;
>         albh_upper = albh >> 32;

>         rl = albl;
>         if ((rl += ahbl_lower) < ahbl_lower) carry++;
>         if ((rl += albh_lower) < albh_lower) carry++;
>         rh = ahbh + ahbl_upper + albh_upper + carry;

>         printf ("%016llx%016llx %llx\n", rh, rl, (1ull*ULONG_MAX)*ULONG_MAX);
>         return 0;
>     }
>     fangorn:~/tmp 313> gcc -std=c99 test.c
>     fangorn:~/tmp 314> ./a.out
>     fffffffffffffffe0000000000000001 fffffffe00000001

> For comparison, the program also displays the result of
> ULONG_MAX * ULONG_MAX computed using unsigned long long arithmetic.

> The purists can add the following macros to eliminate most of the "magic"
> constants used in the code:

>     #define OFFSET ((sizeof(long long) * CHAR_BIT) / 2)
>     #define MASK   ((1ull << OFFSET) - 1)

> The remaining assumption is that unsigned long long has an even number
> of value bits and no padding bits.

> Dan

Mon, 19 Sep 2005 20:45:23 GMT  64 bit multiplication (RSA key generation)

Quote:

> Thanks very much !!! :D

> > >I'm currently doing a university assignment and I need to be able to
> > >implement 64 bit multiplication.  As such I need to hold a 128 bit
> > >number.  I know that I need to use long long to store the 64 bit
> > >numbers, but as a newbie to this I am not sure how to do the
> > >multiplication.  Can anyone help me with this either pointing me to a
> > >tutorial, or just some general help?

> > Assuming that (ULONG_MAX+1) ** 2 == (ULLONG_MAX+1), a *naive* analysis
> > of the problem goes like this:

> > a = ah * (ULONG_MAX+1) + al
> > b = bh * (ULONG_MAX+1) + bl
> > a * b = ah * bh * (ULONG_MAX+1)**2 + (ah * bl + al * bh) * (ULONG_MAX+1) +
> >       + al * bl

> > This means that the lower part of the result consists of al * bl + the
> > lower half of (ah * bl + al * bh) multiplied by (ULONG_MAX+1).

> > The higher half of the result consists from ah * bh +
> > the upper half of (ah * bl + al * bh) + the carry generated when
> > computing the lower half of the result.

> > A C program that implements this "algorithm" looks like this.  For
> > simplicity reasons, an unsigned long long is assumed to be a 64-bit type.

> >     fangorn:~/tmp 312> cat test.c
> >     #include <stdio.h>
> >     #include <limits.h>

> >     int main()
> >     {
> >         unsigned long long a = ULLONG_MAX, b = ULLONG_MAX;
> >         unsigned long long ah = a >> 32, al = a & 0xffffffff;
> >         unsigned long long bh = b >> 32, bl = b & 0xffffffff;
> >         unsigned long long rl, rh;
> >         unsigned long long ahbh, ahbl, albh, albl;
> >         unsigned long long ahbl_upper, ahbl_lower, albh_upper, albh_lower;
> >         unsigned long long carry = 0;

> >         ahbh = ah * bh;
> >         ahbl = ah * bl;
> >         albh = al * bh;
> >         albl = al * bl;

> >         ahbl_lower = ahbl << 32;
> >         ahbl_upper = ahbl >> 32;
> >         albh_lower = albh << 32;
> >         albh_upper = albh >> 32;

> >         rl = albl;
> >         if ((rl += ahbl_lower) < ahbl_lower) carry++;
> >         if ((rl += albh_lower) < albh_lower) carry++;
> >         rh = ahbh + ahbl_upper + albh_upper + carry;

> >         printf ("%016llx%016llx %llx\n", rh, rl, (1ull*ULONG_MAX)*ULONG_MAX);
> >         return 0;
> >     }
> >     fangorn:~/tmp 313> gcc -std=c99 test.c
> >     fangorn:~/tmp 314> ./a.out
> >     fffffffffffffffe0000000000000001 fffffffe00000001

> > For comparison, the program also displays the result of
> > ULONG_MAX * ULONG_MAX computed using unsigned long long arithmetic.

> > The purists can add the following macros to eliminate most of the "magic"
> > constants used in the code:

> >     #define OFFSET ((sizeof(long long) * CHAR_BIT) / 2)
> >     #define MASK   ((1ull << OFFSET) - 1)

> > The remaining assumption is that unsigned long long has an even number
> > of value bits and no padding bits.

> > Dan

Hi,

I'm writing a similar program for a university project, but I need to
take it one step further. I need to take the modulus of a 128-bit
number, in the following manner:

(128-bit number) mod (64-bit number)

How could this be achieved assuming a 128-bit number is stored as in
the above example? Any help would be much appreciated.

Thanks,
Wilger.

Sun, 16 Oct 2005 22:56:03 GMT  64 bit multiplication (RSA key generation)

Quote:
> Hi,

> I'm writing a similar program for a university project, but I need to
> take it one step further. I need to take the modulus of a 128-bit
> number, in the following manner:

> (128-bit number) mod (64-bit number)

> How could this be achieved assuming a 128-bit number is stored as in
> the above example? Any help would be much appreciated.

Look up a bignum library...

Oh gosh, I seem to be the author of one...

<cheap plug>
http://math.libtomcrypt.org

Can handle really huge numbers [memory provided of course] and is
*all* ISO C source code [no ASM or bullshit in there]

</cheap plug>

Tom

Mon, 17 Oct 2005 05:04:46 GMT  64 bit multiplication (RSA key generation)

Quote:
> ...

> Hi,

> I'm writing a similar program for a university project, but I need to
> take it one step further. I need to take the modulus of a 128-bit
> number, in the following manner:

> (128-bit number) mod (64-bit number)

> How could this be achieved assuming a 128-bit number is stored as in
> the above example? Any help would be much appreciated.

> Thanks,
> Wilger.

How about subtract and shift? You know, long division.

Doing it in binary is fairly straightforward, just takes a number of
times through the loop.

Joel

Mon, 17 Oct 2005 15:45:13 GMT

 Page 1 of 1 [ 6 post ]

Relevant Pages