# Construct Matrices from Coefficient of f[x] in Finite Fields?

I'm working on a problem at the moment using Mathematica and the Finite Fields package, and I've ran into some difficulty converting the problem to a Matrix, so I'm hoping somebody here would know how to help me in this matter.

Briefly, the problem is as follows:

I have:

1) I'm working over Finite Fields. I have a set, say S={a, b, c}, which are the non-zero and non-one elements of the finite field.

2) I have a function F that takes two non-equal elements in S and is of the form (it's not exactly this, but this captures the idea):

F[a_, b_]:= f[a] - f[b] + f[(a/b)*(a/b)]


where f isn't designated and what's in the brackets is the value in the Finite Field (it's only there because we want f[a] and f[b] to subtract only if a and b are the same, we don't want "a - b").

I Want and My Question:

1) I want to test every combination of values in the field. In the example this would be F(a, b), F(a, c), F(b, a), F(b, c), F(c, a), and F(c, b). I want to put that in a set, say G.

2) After testing all of the values, I'll get a new list (G) which looks something like:

G = { 2f[a] - f[b], f[a] - f[b] + f[c], -f[a] + 2f[b], f[c] }


3) My question, and what I'm having issues with and hoping somebody could help me with, is I want to convert every element in that into a vector, {v1, v2, v3}, where the vector lists the coefficients of f[a], f[b], and f[c] of every element in the list. To continue the example:

Original: G=  { 2f[a] - f[b], f[a] - f[b] + f[c], -f[a] + 2f[b], f[c] }

What I want: N(ew) = { {2, -1, 0}, {1, -1, 1}, {-1, 2, 0}, {0, 0, 1} }


i.e. in the first element I've 2 [f[a]]s, -1 [f[b]]s, 0 [f[c]]s, etc. How can I do this? How can I convert the first line into the second line?

My Progress So Far

1) I'm using the Finite Fields Package. I've successfully created a function which lists every element of any finite field and then disposes 0 and 1.

2) I've successfully defined the function F(a, b).

3) I've managed to find a way to let me get the set G for any field.

4) This is where I'm stuck. I've tried using coefficient array with variables as {g[a], g[b], g[c]} but it doesn't seem to do anything. It calls it a Sparse Array but when I check CoefficientLists it literally just gives me back the exact same set G. It seems like this should definitely be possible, but I think what's happening is Mathematica isn't recognising g[x] as a variable (understandably). I can't send g(x) to an element in the finite field, because then each of the terms in G will end up adding or subtracting and I'll be left with a single element in every term. For the same reason I can't send it to a vector because I don't want the terms inside multiplied by the coefficient. Once G can be sent to a list N I can construct a matrix out of it without much issue I'd think, but I don't know how to do that initial conversion.

One thing I've tried is setting g[a_] = x^a and then trying CoefficientList[G, x], but it seems that because a is an element of the finite field this is simply giving me:

{ {2x^[a] - x^[b]}, {x^[a] - x^[b] + x^[c]}, {-x^[a] + 2x^[b]}, {x^[c]} }


which obviously is not helping me here. since I want the coefficient for each a, b, c including zeroes.

My Question: It seems to me that it should be possible to do this somehow, but I'm not very experienced in Mathematica (I've literally learned it over the course of the last two days by reading "An Elementary Introduction to Mathematica" and despite having used Python and C++ before it's very different in its structure I find) and I don't really know how. I'm hoping somebody here would have some ideas? I would really appreciate any help or insight anybody may have. If any more information is needed, let me know and I can update this post.

I've asked it on StackOverflow but it has not yet been answered and was advised elsewhere to pose the problem here; I'm not too sure on whether these are distinct websites (I don't think they are?), so if this is a repost I apologise.

Any help would be highly appreciated.

EDIT: Resolved. See Solution.

• F(a, b) to wit? Commented Jun 18, 2017 at 13:17
• D[AllRR[5], g/@Field[5]]  isn't quite right. You need {braces} around the second argument: D[AllRR[5], {g/@Field[5]}]. HOWEVER, I'm not sure how it works with subscripts. Subscripts are the devil. Commented Jun 18, 2017 at 14:03
• Ahh apologies, I forgot to include this case in the edit. I've updated it to reflect that with both it ends up having some issues. Commented Jun 18, 2017 at 14:07
• I added an update to my answer. Commented Jun 18, 2017 at 14:12
• What is FullForm[Field[5]]? Commented Jun 18, 2017 at 15:12

(Related to my answer here,) I believe one thing that will accomplish what you're looking for is

D[{2 f[a] - f[b], f[a] - f[b] + f[c], -f[a] + 2 f[b], f[c]}, {{f[a], f[b], f[c]}}]


which yields

{{2,-1,0},{1,-1,1},{-1,2,0},{0,0,1}}


So, assuming

S={a,b,c}
G={ 2f[a] - f[b], f[a] - f[b] + f[c], -f[a] + 2f[b], f[c] }


you want

D[G,{f/@S}]


Edit: With a little more information in the question, let me assume variables are assigned as

S = {g[Subscript[{2}, 5]], g[Subscript[{4}, 5]], g[Subscript[{3}, 5]]}
RR = {3 g[Subscript[{2}, 5]] - 2 g[Subscript[{4}, 5]],
g[Subscript[{4}, 5]], -g[Subscript[{2}, 5]] + 2 g[Subscript[{3}, 5]],
g[Subscript[{2}, 5]] - 2 g[Subscript[{3}, 5]] + 2 g[Subscript[{4}, 5]],
g[Subscript[{4}, 5]], -g[Subscript[{2}, 5]] + 2 g[Subscript[{3}, 5]]}


then D[RR,S] gives the result.

• Hi! I want to thank you for this, as it definitely looks like this is along the correct track. I've encountered an issue with this however. ->If I implement it as D[xx,{f/@S}] I'm getting a list of zeroes back. -> If I implement it using D[xx, f/@S] I'm getting quite a substantial error message, which I'm uncertain if it depends on my own code, or if it is related to the function D[xx,{y}]. Would you have any suggestions? Please see the OP for further details. Commented Jun 18, 2017 at 14:03
• Without the braces won't work---when there's a single-depth list argument in the second slot, D expects it to be {var, n}, that is, you want the nth derivative with respect to var. Commented Jun 18, 2017 at 14:07
• Thank you once more. This is definitely the correct way to go about the problem I believe. Some oddness is definitely happening though. When I do it precisely as you've defined it, it's working correctly. When I try to use it with what I've defined, it's giving only the zero vector, even though both what I'm getting and what you're getting are identical. Please see the image for clarification. I'm not too sure how to resolve this. I suspect this is fundamentally related to it being 2 in the field F5 = {0,1,2,3,4} rather than just 2 in Z. Commented Jun 18, 2017 at 14:43
• Without the full notebook, the only thing I can suggest is to use FullForm to really deeply inspect the results of MyAR5. Commented Jun 18, 2017 at 14:57
• Sure thing! I have updated the OP to reflect the Full Form of MyAR5. Commented Jun 18, 2017 at 14:59

I figured I would clarify this for anybody who is looking for advice on the matter in the future. The solution, which is clumsy and certainly not an efficient algorithm but never the less works, is to integrate PowerListQ[F]=True into your algorithm for the fields you're working in.

From there, you need to define the function g[x] to be f[FieldInd[x]].

Having done this, apply D[xx,{s}] as Evanb has mentioned.

As the discrete log problem is not an easy problem, this is a very computationally expensive solution, but for small fields at least it should be acceptable.