Re: pmult

Le 12 nov. 2021 à 16:12, Bill Allombert <Bill.Allombert@math.u-bordeaux.fr> a écrit :

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