Math Again, Almost
So, I really need to get around to responding to the talk about Shamir’s Secret Sharing. Unfortunately, I’ve been pretty busy with a slew of other things, so I don’t think I’ll be able to do that quite yet. It’s been nice to get some comments from people who know math, and it was pretty neat to be part of the 20th Carnival of Mathematics.
I did get the time to look over The BWAIN’s review of the SSS stuff, which seems to make sense. I hadn’t quite realized how important the mod-p bits were to the algorithm. In fact, Adi Shamir himself did respond, and said more or less the same thing (with fewer words). So it looks like that’s pretty important. I haven’t gotten the time to actually look through the code, but I don’t seem to recall any of the open-source SSS implementations actually computing mod-p. (SSSS comes to mind, but I haven’t done much more than glance through it.)
At any rate, I’ve been too busy to look through much of the math with more than half-concentration for the past few days, so I’ll certainly try to take a look at everyone’s comments as soon as possible. I just finished applying to two colleges, and most of the other applications are also 90-98% done.
Andy Schmitz
Hi. Just so you know, SSSS (like most “real” SSS implementations) doesn’t work in GF(p) (think integers modulo a prime), but in GF(2^b) for some b, because that’s more convenient for computers. (An element of GF(2^b) can be represented using a b-bit binary number. Note that this is not a “binary number”, exactly, but it’s an efficient representation. The distinction is important.)
Near the top of ssss.c (I just looked at 0.5) is a data structure called “irred_coeff”, which is for constructing GF(2^b) for various values of b.
I’m going to do a blog post on Galois fields soonish on The BWAIN. I’ll try to explain things in such a way that SSSS is more understandable, okay?
Comment by Pseudonym — 11/6/2007 @ 11:17 pm