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?

Well, if you don't have access to Knuth (as mentioned already), try

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

set to write your algorithm, or maybe even your program.

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

--