Setting up the problem

To set up the problem, we want a prime p chosen such that p-1 is a product of small primes, a generator alpha of (Z_p)*, a randomly chosen a between 2 and p-1, and beta=alpha^a mod p.

For the example we use 541 since 540=2^2*3^3*5.

>	p := 541; isprime(p); ifactor(p-1);

Next we want a generator of  (Z_p)*.  To test if a number is a gererator, we try raising it to the (p-1)/q power for each prime q that divides (p-1).

>	testgen := x -> [Power(x,270) mod 541, Power(x, 180) mod 541,    Power(x, 54) mod 541]; testgen(2);

Since none of these powers is 1, our selected x is a generator.  Thus we choose alpha = 2.  

>	alpha := 2;

We now pick a at random.  (To make this worksheet repeatable we fix a as the value that is produced by the random function freshly reseeded.)  We set our lower bound at 10 since we would like alpha^a to be mode than p.

>	a := rand(10..540)(); a := 238;

Having alpha and a, we compute beta = alpha^a.

>	beta := Power(alpha, a) mod p;

Solving mod a prime to the first power

Now we are ready to try to solve the discrete logrithm problem.  (We know alpha and beta, but have forgotten a.)
To find a, it suffices to find a4, a27, and a5, the result of reducing a mod 4, 27, and 5.  We will start with a5 since 5 only appears to the first power in 540.

We note that 4*27 is congruent to 0, 0, and 3 mod 4, 27, and 5 respectively.  Since 3*2=1 mod 5 we know that 216 = 2*4*27 is congruent to 0, 0, and 1 mod 4, 27, and 5 respectively.  Thus 216*a=a5 mod 540.  We compute alpha5 = alpha^216 and beta5 = beta^216.  We note that beta5 = alpha5^a5.

>	beta5 := Power(beta, 216) mod p; alpha5 := Power(alpha, 216) mod p;

Now we compute the powers of alpha5 and find a5.

>	for i from 0 to 4 do print([i, Power(alpha5, i) mod p]) od:

By inspection beta5 = aplha5^3.  Thus a5 = 3.

>

a5 := 3;

Solving mod a prime to a higher power

We start a similar procedure for 27, the power of 3 in 540.  Since 4*5 = 20 mod 27 and 1/20=23 mod 27, we note that 460 = (0,1,0) mod (2, 27, 5).  Thus 460*a=a27 mod 540.

>	beta27 := Power(beta, 460) mod p; alpha27 := Power(alpha, 460) mod p;

We note that (alpha27)^27 = 1 mod p.

beta27 = alpha27^a = alpha27^a27.

Describe a27 in base 3.  a27 = 9 x2 + 3 x1 + x0.

We compute alpha27 ^ (9i) with i in Z_3.

>	for i from 0 to 2 do print([i, Power(alpha27, 9*i) mod p]) od:

Next we compute beta27 ^ 9 = alpha27 ^ (9 x0) and read off x0.

>	Power(beta27, 9) mod p;

Comparing with the list above, we see that x0=1.

>

x0 := 1;

Now we compute beta27a = alpha27 ^(3 x1 + 9 x2) and beta27a ^ 3 = alpha27 ^ 9 x1, letting us read off x1.

>	beta27a := beta27 * (Power(alpha27, 27-x0) mod p) mod p; Power(beta27a, 3) mod p;

>

x1 := 1;

Now we compute beta27b = alpha27 ^ (9 x2) and read off x2.  Compute a27.

>	beta27b := beta27a * (Power(alpha27, 27-x1*3) mod p) mod p;

>	x2 := 2; a27 := x2*9+x1*3+x0;

Solving for the third prime

Now we repeat for the process for the prime 2.

>	temp := 27*5 mod 4; temp2 := 1/temp mod 4; power2 := temp2*27*5;

>	beta4 := Power(beta, 405) mod p; alpha4 := Power(alpha, 405) mod p;

>	for i from 0 to 1 do print([i, Power(alpha4, 2*i) mod p]) od:

>	Power(beta4, 2) mod p;

>

x0 := 0;

>	beta4a := beta4 * (Power(alpha4, 4-x0) mod p) mod p;

>	x1 := 1; a4 := x0 + 2*x1;

Putting the parts together.

Now having a = (a4, a27, a5) mod (4, 27, 5).  We want to put them back together.  Since we already have 405, 460, and 216 equal to (1,0,0), (0,1,0), and (0,0,1) respectively mod (4,27,5), this is a simple matter of multiplication.

>	a := (a4*405 + a27*460 + a5*216) mod 540;

Exercise:

Choose a random number between 10 and 530 that is not a power of 2.  Use the method given above to find its discreet log mod 541 base 2.

>