EE 480F

Program Assignment

Arbitrary precision arithmetic

This is an open-ended assignment, the goal of which is to give you some idea of how public-key algorithms work, and also develop some useful tools for future homework.
The goal: write code to implement arbitrary precision integer arithmetic.

Specifically, you want to be able to take numbers of hundreds or thousands of digits, and perform arithmetic with them. This will include:

Addition and subtraction
Multiplication
Division with remainder (computing X mod N)

This is part I of the assignment. After you have these functions, you can use them as building blocks to perform other functions:

The Euclidean Algorithm, to compute inverses of numbers (mod N)
Exponentiation, to raise integers to powers (mod N)

That is part II of the assignment. Once you have these functions, we can perform the RSA algorithm given a message and encryption key.

How to do it

If you write in C or C++, you can create a datatype to hold arbitrarily big integers. For convenience, you can just use character strings. For instance, you can represent the hexadecimal number 123eef5 as the string "5fee321". I put that in reverse order because you'll find it's more convenient to do so. We will use hexadecimal because it is much easier.

For further convenience, you can use the typedef keyword to define a number datatype like so:


typedef char * number;



number N, M, p;    /* these need to be initialized later */

Then, you'll need to define individual functions to handle these numbers: creating them by allocating space, filling them with data, and performing arithmetic. For example you could have:

number new_number( int size );             /* allocates space for new number */
                                           /* (used by the next 3 functions) */
number string_to_number( char * string  )  /*  creates a new number */
number sum( number x, number y );          /* new number = x+y */
number product( number x, number y );      /* new number = xy */

void add_to( number x, number y );         /* x=x+y (no new number created ) */
void print_number( number x );             /* prints number */
void dispose_of_number( number x );        /* de-allocates number */

Then you could have code in your main function like so:


number N, M, P, Q;



N = string_to_number( "12a3567" );

M = string_to_number( "fffff" );



P = sum( N, M );

Q = product( N, M );



print_number( Q );

dispose_of_number( N ); dispose_of_number( M );

dispose_of_number( P ); dispose_of_number( Q );

The main function is unimportant. The important part is implementing the individual functions. They must be implemented as separate functions, because you will be using them as building blocks. For example, your multiply function can use your add function. Later, your exponent function will use your multiply function.

In the process, you may find yourself creating a few more functions for convenience sake.

Note: how are you going to represent negative numbers, and subtraction? That's up to you.