A nonnegative integer may be stored inside a computer as an array of digits:
#define PRECISION 1000
int x[PRECISION] = { 4, 1, 3 };
/* x[0] is 4, x[1] is 1, x[2] is 3, x[3] is 0, x[4] is 0, etc. */
Conventionally
x[0] is the units digit,
x[1] is the tens digit, etc.,
so the example above is the integer 314.
Implement the following functions:
print(int x[PRECISION])
Print x for the user as a readable number.
Make sure to print {4,1,3} as 314, not 000000314;
but also make sure to print 0 as 0.
add(int z[PRECISION],int x[PRECISION],int y[PRECISION])
Set z to the sum of x and y.
To protect the user,
you should check whether the answer is larger than 10^PRECISION;
if it is, print a warning message and exit.
(Here m^n means m to the power n.)
iszero(int x[PRECISION])
Return 1 if x is zero, 0 if x is nonzero.
odd(int x[PRECISION])
Return x mod 2:
i.e., 0 if x is even, 1 if x is odd.
halve(int z[PRECISION],int x[PRECISION])
Set z to half of x, rounded down.
multiply(int z[PRECISION],int x[PRECISION],int y[PRECISION])
Set z to the product of x and y,
by the method explained in class.
Check your work by writing a program to compute factorials: e.g., 10!=3628800 and 50!=30414093201713378043612608166064768844377641568960512000000000000.
20000131: Homework due 20000209.
Implement the following functions:
isless(int x[PRECISION],int y[PRECISION])
Return 1 if x is smaller than y, 0 otherwise.
subtract(int z[PRECISION],int x[PRECISION],int y[PRECISION])
Set z to the difference x-y.
To protect the user,
print a warning message and exit if x is smaller than y.
addmod(int z[PRECISION],int x[PRECISION],int y[PRECISION],int n[PRECISION])
Set z to (x+y) mod n.
Assume that x and y are both smaller than n.
multiplymod(int z[PRECISION],int x[PRECISION],int y[PRECISION],int n[PRECISION])
Set z to xy mod n.
Assume that x is smaller than n.
expmod(int z[PRECISION],int x[PRECISION],int e[PRECISION],int n[PRECISION])
Set z to (x^e) mod n.
Assume that x is smaller than n.
Use these functions to compute 2^314158 mod 314159, 2^1000002 mod 1000003, 2^314159265358979322 mod 314159265358979323, and 2^314159265358979346 mod 314159265358979347.
20000211: Homework due 20000221. Book exercises 6.10, 9.1, 9.3, 9.12.
20000310: Homework.
Implement the following function:
gcod(int z[PRECISION],int x[PRECISION],int y[PRECISION])
Set z to the greatest common odd divisor of x and y,
by the method explained in class.
Implement Pollard's rho method using multiplymod and gcod. Use Pollard's rho method to find a factorization of 314159265358979323.
20000407: Homework. Book exercises 8.1, 8.2, 8.3, 10.15, 10.17.
20000417: Homework.
Implement the following function:
expfactmod(int z[PRECISION],int x[PRECISION],int L,int n[PRECISION])
Set z to x^(L!) mod n,
by starting from x,
squaring it mod n,
cubing the result mod n,
etc.
Assume that x is smaller than n.
Note that L is an int, not an array.
Implement Pollard's p-1 method using expfactmod and gcod: given an integer n to factor, and given an integer L, try computing gcod{2^(L!)-1,n}. Use Pollard's p-1 method to find a factorization of 1487100739193371513432776255397.