Maple User Group Answers

[Anfang] [Hauptseite] [Suchen] [LDFM]

discrete logarithm of a value   (9.5.02)

David Rees

Using Maple V, Release 4.

Is there a method in the GF package, or in the GF mode in Domains, which gives the discrete logarithm of a value?

Currently I do this by constructing a table of powers of a primitive root, and then inverting the table to get the logarithms. But these tables rapidly outgrow Maple's capacity ("Object too large"), and I do not see a method of giving Maple more memory.

Strictly speaking, all I need to know is whether the logarithm is odd or even, but a general answer would also be useful.

David Joyner   (12.5.02)

You can load the package at

http://web.usna.navy.mil/~wdj/ffield0.htm

Nothing fancy, so it may be too slow for your purposes.

Mike May   (12.5.02)

I am not aware of a discrete log command, and would be surprised if one existed. There are several cryptographic systems that would crumble if there were an easy algorithm for that problem.

Finding the power of 2 (or any other specified prime) in the discrete log is a standard algorithm.

Suppose alpha^a = beta mod p. Express p-1 as k*2^n, and a as j*2^m. Then (alpha^k)^(2^m) = beta^k mod p.

a is odd if (Power(alpha, k) mod p) = (Power(beta, k) mod p)

[Using the power command reduces mod p, so that alpha, a, and p can be large. In my cryptography class we used 200 digit primes with El Gamal.]

Carl Devore   (12.5.02)

If someone can come up with an efficient algorithm for discrete log, I am sure some people at the NSA would be interested in talking to you :-) This is a very active area of research.

| Currently I do this by constructing a table of powers of ...

It may come as a surprise to you to learn that this technique is actually used in high-speed code for finite-field computations for fields of order up to about a million or so. Thus, the speed of multiplication and division is drastically improved (elements are stored as their logs) at the expense of slightly slower addition and subtraction (these now require inverse table lookup).

| Strictly speaking, all I need to know is whether ..

Deciding whether a particular number divides the logarithm is much easier than computing the logarithm itself. Here is a procedure for it. This is coded for Maple 6+, but it can be easily retrofitted to Maple 4. Someone else can do that... I am tired of writing code for pre-modules Maple.

Discrete Logarithms
Author: Carl Devore <devore@math.udel.edu>
13 May 2002

Input:
   x, b   elements of the finite field F
   p       a prime
   F       a finite field returned by the GF command.

Output:
   If log[b](x) exists in F, then this procedure returns the largest e such that
   p^e divides log[b](x) and p^e divides q:= ord(F)-1.
   If  p does not divide q, then the message "no unique answer" is returned,
   regardless of whether the logarithm exists.
   If p does divide q, but the logarithm does not exist,
   then the message "log doesn't exist" is returned.

This procedure will work for fields of very large order.  In particular,
it does not require a prime factorization of q.

> LogDiv:= proc(x, b, p, F)
>    option `Copyright (c) 2002, Carl James DeVore, Jr.  All rights reserved.`;
>    local o,n,q,X,B;
>    o:= F:-size()-1;
>    for n from 0 while irem(o,p,'q')=0 do o:= q od;
>    if n=0 then return "no unique answer" fi;
>    use `^`= F:-`^` in
>       B:= b^o;
>       for n from 0 while B <> F:-one do B:= B^p od;
>       X:= x^o;
>       for n from n by -1 to -1 while X <> F:-one do X:= X^p od
>    end use;
>    if n<0 then "log doesn't exist" else n fi
> end proc:

Test on a small field where we can actually compute the logarithms by brute force.

> F:= GF(3,4):
> x:= F:-random();
                                      2
                              x := 2 T
> b:= F:-random();
                                        2    3
                        b := 1 + 2 T + T  + T
> LogDiv(x,b,2,F);
                                  3

Thus 2^3 divides the log. Get the log by brute force to check.

> for n to 3^4-1 do
>    use `^`= F:-`^` in
>       if b^n = x then print(`Log = `||n); break fi
>    end use
> od:
                               Log = 24

Now do a really big field. It will take Maple a few seconds to find the irreducible polynomial.

> F:= GF(5,600):
> x:= F:-random():
> b:= F:-random():
> LogDiv(x,b,2,F);
                                  0

Thus the log exists, and is odd.

The above can be improved for some special cases. If you only want to know whether x has a p-th root in the field, and p divides q, this is equivalent to x^(q/p) = 1. Furthermore, if p = 2 and q+1 is prime, there is a very efficient algorithm for this known as the Law of Quadratic Reciprocity, which is available in Maple as numtheory[legendre].

(Note that I am using q to represent the order of the multiplicative group rather than the order of the field, which is more traditional.)

[Anfang] [Hauptseite] [Suchen] [LDFM]