D. J. Bernstein
Integer factorization
Math 436, Number Theory II, Spring 2000

# Course handouts

20000121: Homework due 20000202.

A nonnegative integer may be stored inside a computer as an array of digits:

```     #define PRECISION 1000
int x[PRECISION] = { 4, 1, 3 };
/* x is 4, x is 1, x is 3, x is 0, x is 0, etc. */
```
Conventionally x is the units digit, x 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.