## Appendix I

All results obtained using Mathematica 4.1 on a 850 mhz Pentium III

e = 3; m = 3: 0.83 Seconds
e = 5; m = 3: 2.59 Seconds
e = 7; m = 3: 10.38 Seconds
e = 9; m = 3: 31.03 Seconds
e = 17; m = 3: 672.57 Seconds

e = 3; m = 3: 0.83 Seconds
e = 3; m = 5: 2.75 Seconds
e = 3; m = 7: 11.37 Seconds
e = 3; m = 9: 57.45 Seconds
e = 3; m = 17: 973.88 Seconds

e = 3; m = 3: 0.83 Seconds
e = 4; m = 4: 3.3 Seconds
e = 5; m = 5: 21.2 Seconds
e = 6; m = 6: 106.33 Seconds
e = 7; m = 7: 510.64 Seconds
e = 8; m = 8: 2112.27 Seconds

[Sample variables for testing; P = padding, o=message to be encrypted, z=encrypted message, m=expansion factor]
p:=3011
q:=1889
n:=p*q
P:=11111111
o:=22
e:=3
z:=PowerMod[o + P, e, p * q]
m=3

[The code proper starts here]
f := (P + x)^e - z
d := e
dim := e*(m + 1)
R := Array[r, {dim, dim}]
crow := 0
For[v = 0, v <= m, For[u = 0, u <= d - 1, crow++;
For[ccol = 1, ccol <= dim, If[ccol > crow, r[crow, ccol] := 0];
If[(ccol - u - 1) < 0, r[crow, ccol] := 0];
If[ccol <= crow && (ccol - u - 1) >= 0,
r[crow, ccol] = (n^(m - v))*Coefficient[f^v, x, ccol - u - 1]];
ccol++];
u++];
v++]
Print["Initialization complete."]

Timing[LatticeReduce[R]]

Clear[x]
For[i = 1, i <= dim,
s = 0;
For[j = 1, j <= dim, s2 = s;
s = s2 + r[i, j]*x^(j - 1);
j++];
Print[Solve[{s == 0, Modulus == n}, x, Mode->Modular]];
i++]