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?

Thanks very much in advance,

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.

                  * Home Page: <http://www.math.su.se/~haberg/>
                  * 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?

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



Sun, 02 Oct 2005 08:25:41 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. 64 bit multiplication (RSA key generation)

2. 64 Bit * 64 Bit = 128 Bit

3. CMap with 64-bit key

4. Help: porting 32-bit app to 64-bit Dec Alpha

5. 64-bit integer on a 32-bit machine

6. Calling 64 bit lib. from 32 bit program

7. emulating a 64 bit divide with 2 32 bit registers in ansi c

8. converting signed 64 bit - 32 bit

9. 64 bit operation on 32 bit PC

10. 64-bit chips, 32-bit compatibility?

11. REQUEST: 64-bit integer math on 32-bit processor

12. Accessing 32-bit com componet from 64-bit application

 

 
Powered by phpBB® Forum Software