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 special-case 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 non-zero elements of GF(256), take log on the lot
| (gotta love mapcar!), add them, run a while-loop subtraction of 255
| until you get something in the range 0-254 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 16-bit *1's*-complement sum) on 2's-complement machines...
Accumulate 16-bit elements into a 32-bit sum (which accumulates
into the upper half all of the "end-around-carries" that would
have occured with a 16-bit 1's-complement 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 carry-normalization can at *most* loop twice.

[Warning: Only works for packets < 128 KB in length (but all IP pkts are).]

-----
Rob Warnock, 8L-855		rpw3@sgi.com
Applied Networking		http://reality.sgi.com/rpw3/
Silicon Graphics, Inc.		Phone: 650-933-1673
2011 N. Shoreline Blvd.		FAX: 650-964-0811
Mountain View, CA  94043	PP-ASEL-IA