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
--

Mon, 19 Sep 2005 09:49:58 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?

You might take down a multiprecision library, such as the GNU GMP (at
gnu.org something).

Hans Aberg      * Anti-spam: remove "remove." from email address.

* AMS member listing: <http://www.ams.org/cml/>
--

Tue, 20 Sep 2005 13:10:25 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.

If your C implementation supports type "long long" then this is
easy indeed.

Quote:
> As such I need to hold a 128 bit number.

Why?

Quote:
> 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.

Use the * operator.

I think your *real* question was how to implement 64x64->127.
This is known as multiple-precision arithmetic and is well
covered in Knuth vol. 1.
--

Wed, 21 Sep 2005 15:23:57 GMT  64-bit multiplication (RSA key generation)

Quote:

> 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.

Recommend a struct. Should be able to find mention of them in your
text book. Send me JPY 1000 for the tip, and don't tell you teacher
where you found out about them.

Quote:
> 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.

Shift and add. Do you want to do it with bits, or do you want to do it
with, say, long, or long long?

Quote:
> Can anyone help me with this either pointing me to a
> tutorial, or just some general help?

looking at the way you multiply by hand:

93
x       24
-----------

and

38502479
x 11111111
-----------

If you understand what you did to multiply those out by hand, and if
you consider that the fundamental algorithm is independent of the
number system base (decimal, binary, base seven, octal, hexadecimal,
base sixty, base two hundred fifty-six, whatever), then you are all

Shoot, since I'm feeling generous, I'll give you a special tip:

abcdefgh
. ijklmnop
-----------

(Using period as a substitute multiply symbol, since using x with
variable names in each digit could prove confusing.)
--

Sun, 02 Oct 2005 08:25:41 GMT

 Page 1 of 1 [ 4 post ]

Relevant Pages