Re: pmult

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Fri, Nov 12, 2021 at 03:29:45PM +0100, Philippe de Rochambeau wrote:
> Hello,
> I’m trying to translate the below Cryptol (cf. https://cryptol.net/files/ProgrammingCryptol.pdf, p. 51) example to PariGP 
> 
> Multiplication in GF(2n) follows the usual polynomial multiplication algorithm, where we multiply the
> first polynomial with each term of the second, and add all the partial sums (i.e., compute their exclusive-or). While
> this operation can be programmed explicitly, Cryptol does provide the primitive pmult for this purpose:
> Cryptol> pmult <| x^^3 + x^^2 + x + 1 |> <| x^^2 + x + 1 |>
> 45
> Cryptol> <| x^^5 + x^^3 + x^^2 + 1 |>
> 45
> 
> ? lift(Mod(2^8,  (x^3 + x^2 + x + 1) * (x^2 + x + 1)))
> %94 = 256
> 
> ? lift(Mod(2^5,  (x^3 + x^2 + x + 1) * (x^2 + x + 1)))
> %95 = 32
> 
> 
> How do you « add the partial sums by computing their exclusive-or » in PariGP, if such an operation is possible?

There are various ways...
The cryptol text is mathematicaly confusing (elements of GF(2^8) are not polynomials).
To define polynomials over GF(2), do
P = (x^3 + x^2 + x + 1)*Mod(1,2)
Q = (x^2 + x + 1)*Mod(1,2)
P*Q
%3 = Mod(1,2)*x^5+Mod(1,2)*x^3+Mod(1,2)*x^2+Mod(1,2)

Now, if you want to convert this to an integer, by evaluating at 2:
subst(lift(P*Q),x,2)
%4 = 45

But if you want to compute in GF(2^8), then you can you can define GF(2^8)
properly in GP (using capital X to avoid confusion with the polynomial
variable x).

X=ffgen((x^8 + x^4 + x^3 + x + 1)*Mod(1,2),'X)
P2 = X^3 + X^2 + X + 1
Q2 = X^2 + X + 1
subst((P2*Q2).pol,'X,2)
%9 = 45

... Now, if you really want to compute exclusive-or, you can use bitxor
on the integers:
Pa = subst(lift(P),x,2)
Qa = subst(lift(Q),x,2)
R=P+Q;
Ra = subst(lift(R),x,2)
%7 = 8
bitxor(Pa,Qa)
%8 = 8

Cheers,
Bill