[MUG] Galois Fields

[MUG] Re: Galois Fields
Author: Maple User Group    Posted: Wed, 15 May 2002 11:27:37 -0400
>> From: Maple User Group "maple_gr" | >> From: "David Rees" "davidhywel" | 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? -=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=- Date: Sun, 12 May 2002 09:06:59 -0400 From: David Joyner "wdj" To: "maple-list" Subject: Galois Fields 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. - David -- Prof David Joyner, Mathematics Department U. S. Naval Academy, Annapolis, MD 21402 phone: (410) 293-6738 -=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=- Date: Sun, 12 May 2002 13:29:47 -0500 From: "Mike May, S.J." "maymk" Subject: Galois Fields To: "maple-list" I am not aware of a discreet 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 discreet 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 iff (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.] Mike May, S.J. -=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=-=*=- Date: Sun, 12 May 2002 23:51:28 -0400 (EDT) From: Carl Devore "devore" To: "maple-list" "davidhywel" Subject: Galois Fields If 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 a primitive > root, and then inverting the table to get the logarithms. 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 the logarithm is odd or > even, but a general answer would also be useful. 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" 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.)

Previous by date: [MUG] eigenvect for real nonsymmetric matrix, 
Next by date: [MUG] Re: plot after assume, Maple User Group
Previous thread: [MUG] How to do matrix parallel computation, 
Next thread: [MUG] plot after assume, Matthias Kawski