Johan Kullstam <kullstam@ne.mediaone.net> wrote:
+
 rpw3@rigden.engr.sgi.com (Rob Warnock) writes:
 > to multiply, look up the "logs" of the numbers, > add them mod 256...

 the logtable is good. however, you need to mod by 255 since GF(256)
 without 0 under multiplication is isomorphic to Z_255 and not Z_256.
+
Oops! Yes, of course! (*blush*)
And you need to specialcase check if either of the args are zero, too,
since that log won't be in the (presumably finite) table. ;}
+
 fastest to take logs, add them, subtract 255 if the sum exceeds 254...
+
Yes, *lots* faster than "mod 255".
+
 for multiplying many nonzero elements of GF(256), take log on the lot
 (gotta love mapcar!), add them, run a whileloop subtraction of 255
 until you get something in the range 0254 then antilog.
+
And this will, of course, cost *at most* one subtraction per element
being multiplied (less one).
Rob
p.s. Which reminds me of the way people often do IP checksums
(which are a 16bit *1's*complement sum) on 2'scomplement machines...
Accumulate 16bit elements into a 32bit sum (which accumulates
into the upper half all of the "endaroundcarries" that would
have occured with a 16bit 1'scomplement adder), then:
(loop
while (> sum 65535)
do (setf sum (+ (ldb (byte 16 16) sum) (ldb (byte 16 0) sum))))
or in C [assuming "u_int32_t sum"]:
while (sum > 65535)
sum = (sum >> 16) + (sum & 0xFFFF);
This carrynormalization can at *most* loop twice.
[Warning: Only works for packets < 128 KB in length (but all IP pkts are).]

Rob Warnock, 8L855 rpw3@sgi.com
Applied Networking http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 6509331673
2011 N. Shoreline Blvd. FAX: 6509640811
Mountain View, CA 94043 PPASELIA