10.5 Functions for Finite fields

10.5.1 setmod_ff

setmod_ff([p|defpoly2])

setmod_ff([defpolyp,p])

setmod_ff([p,n])

:: Sets/Gets the current base fields.

return

number or polynomial

p

prime

defpoly2

univariate polynomial irreducible over GF(2)

defpolyp

univariate polynomial irreducible over GF(p)

n

the extension degree

• If the argument is a non-negative integer p, GF(p) is set as the current base field.
• If the argument is a polynomial defpoly2, GF(2^deg(defpoly2 mod 2)) = GF(2)[t]/(defpoly2(t) mod2) is set as the current base field.
• If the arguments are a polynomial defpolyp and a prime p, GF(p^deg(defpolyp)) = GF(p)[t]/(defpolyp(t)) is set as the current base field.
• If the arguments are a prime p and an extension degree n, GF(p^n) is set as the current base field. p^n must be less than 2^29 and if p is greater than or equal to 2^14, then n must be equal to 1.
• If no argument is specified, the modulus indicating the current base field is returned. If the current base field is GF(p), p is returned. If it is GF(2^n), the defining polynomial is returned. If it is GF(p^n) defined by setmod_ff(defpoly,p), [defpolyp,p] is returned. If it is GF(p^n) defined by setmod_ff(p,n), [p,defpoly,prim_elem] is returned. Here, defpoly is the defining polynomial of the n-th extension, and prim_elem is the generator of the multiplicative group of GF(p^n).
• Any irreducible univariate polynomial over GF(2) is available to set GF(2^n). However the use of defpoly_mod2() is recommended for efficiency.

[174] defpoly_mod2(100);
x^100+x^15+1
[175] setmod_ff(@@);
x^100+x^15+1
[176] setmod_ff();
x^100+x^15+1
[177] setmod_ff(x^4+x+1,547);
[1*x^4+1*x+1,547]
[178] setmod_ff(2,5);
[2,x^5+x^2+1,x]

References

defpoly_mod2

10.5.2 field_type_ff

field_type_ff()

:: Type of the current base field.

return

integer

• Returns the type of the current base field.
• If no field is set, 0 is returned. If GF(p) is set, 1 is returned. If GF(2^n) is set, 2 is returned.

[0] field_type_ff();
0
[1] setmod_ff(3);
3
[2] field_type_ff();
1
[3] setmod_ff(x^2+x+1);
x^2+x+1
[4] field_type_ff();
2

References

setmod_ff

10.5.3 field_order_ff

field_order_ff()

:: Order of the current base field.

return

integer

• Returns the order of the current base field.
• q is returned if the current base field is GF(q).

[0] field_order_ff();
field_order_ff : current_ff is not set
return to toplevel
[0] setmod_ff(3);
3
[1] field_order_ff();
3
[2] setmod_ff(x^2+x+1);
x^2+x+1
[3] field_order_ff();
4

References

setmod_ff

10.5.4 characteristic_ff

characteristic_ff()

:: Characteristic of the current base field.

return

integer

• Returns the characteristic of the current base field.
• p is returned if GF(p), where p is a prime, is set. 2 is returned if GF(2^n) is set.

[0] characteristic_ff();
characteristic_ff : current_ff is not set
return to toplevel
[0] setmod_ff(3);
3
[1] characteristic_ff();
3
[2] setmod_ff(x^2+x+1);
x^2+x+1
[3] characteristic_ff();
2

References

setmod_ff

10.5.5 extdeg_ff

extdeg_ff()

:: Extension degree of the current base field over the prime field.

return

integer

• Returns the extension degree of the current base field over the prime field.
• 1 is returned if GF(p), where p is a prime, is set. n is returned if GF(2^n) is set.

[0] extdeg_ff();
extdeg_ff : current_ff is not set
return to toplevel
[0] setmod_ff(3);
3
[1] extdeg_ff();
1
[2] setmod_ff(x^2+x+1);
x^2+x+1
[3] extdeg_ff();
2

References

setmod_ff

10.5.6 simp_ff

simp_ff(obj)

:: Converts numbers or coefficients of polynomials into elements in finite fields.

return

number or polynomial

obj

number or polynomial

• Converts numbers or coefficients of polynomials into elements in finite fields.
• It is used to convert integers or intrgral polynomials int elements of finite fields or polynomials over finite fields.
• An element of a finite field may not have the reduced representation. In such case an application of simp_ff ensures that the output has the reduced representation. If a small finite field is set as a ground field, an integer is projected the finite prime field, then it is embedded into the ground field. ptosfp() can be used for direct projection to the ground field.

[0] simp_ff((x+1)^10);
x^10+10*x^9+45*x^8+120*x^7+210*x^6+252*x^5+210*x^4+120*x^3+45*x^2+10*x+1
[1] setmod_ff(3);
3
[2] simp_ff((x+1)^10); 
1*x^10+1*x^9+1*x+1
[3] ntype(coef(@@,10));
6
[4] setmod_ff(2,3);
[2,x^3+x+1,x]
[5] simp_ff(1);
@_0
[6] simp_ff(2);
0
[7] ptosfp(2);
@_1

References

setmod_ff, lmptop, gf2nton, ptosfp, sfptop

10.5.7 random_ff

random_ff()

:: Random generation of an element of a finite field.

return

element of a finite field

• Generates an element of the current base field randomly.
• The same random generator as in random(), lrandom() is used.

[0] random_ff();
random_ff : current_ff is not set
return to toplevel
[0] setmod_ff(pari(nextprime,2^40));
1099511627791
[1] random_ff();
561856154357
[2] random_ff();
45141628299

References

setmod_ff, random, lrandom

10.5.8 lmptop

lmptop(obj)

:: Converts the coefficients of a polynomial over GF(p) into integers.

return

integral polynomial

obj

polynomial over GF(p)

• Converts the coefficients of a polynomial over GF(p) into integers.
• An element of GF(p) is represented by a non-negative integer r less than p. Each coefficient of a polynomial is converted into an integer object whose value is r.

[0] setmod_ff(pari(nextprime,2^40));
1099511627791
[1] F=simp_ff((x-1)^10);
1*x^10+1099511627781*x^9+45*x^8+1099511627671*x^7+210*x^6
+1099511627539*x^5+210*x^4+1099511627671*x^3+45*x^2+1099511627781*x+1
[2] setmod_ff(547);                 
547
[3] F=simp_ff((x-1)^10);
1*x^10+537*x^9+45*x^8+427*x^7+210*x^6+295*x^5+210*x^4+427*x^3
+45*x^2+537*x+1
[4] lmptop(F);
x^10+537*x^9+45*x^8+427*x^7+210*x^6+295*x^5+210*x^4+427*x^3
+45*x^2+537*x+1
[5] lmptop(coef(F,1));
537
[6] ntype(@@);
0

References

simp_ff

10.5.9 ntogf2n

ntogf2n(m)

:: Converts a non-negative integer into an element of GF(2^n).

return

element of GF(2^n)

m

non-negative integer

• Let m be a non-negative integer. m has the binary representation m=m0+m1*2+...+mk*2^k. This function returns an element of GF(2^n) = GF(2)[t]/(g(t)), m0+m1*t+...+mk*t^k mod g(t).
• Apply simp_ff() to reduce the result.

[1] setmod_ff(x^30+x+1);
x^30+x+1
[2] N=ntogf2n(2^100);
(@^100)
[3] simp_ff(N);
(@^13+@^12+@^11+@^10)

References

gf2nton

10.5.10 gf2nton

gf2nton(m)

:: Converts an element of GF(2^n) into a non-negative integer.

return

non-negative integer

m

element of GF(2^n)

• The inverse of gf2nton.

[1] setmod_ff(x^30+x+1);
x^30+x+1
[2] N=gf2nton(2^100);
(@^100)
[3] simp_ff(N);
(@^13+@^12+@^11+@^10)
[4] gf2nton(N);
1267650600228229401496703205376
[5] gf2nton(simp_ff(N));
15360

References

gf2nton

10.5.11 ptogf2n

ptogf2n(poly)

:: Converts a univariate polynomial into an element of GF(2^n).

return

element of GF(2^n)

poly

univariate polynomial

• Generates an element of GF(2^n) represented by poly. The coefficients are reduced modulo 2. The output is equal to the result by substituting @ for the variable of poly.

[1] setmod_ff(x^30+x+1);
x^30+x+1
[2] ptogf2n(x^100);
(@^100)

References

gf2ntop

10.5.12 gf2ntop

gf2ntop(m[,v])

:: Converts an element of GF(2^n) into a polynomial.

return

univariate polynomial

m

an element of GF(2^n)

v

indeterminate

• Returns a polynomial representing m.
• If v is used as the variable of the output. If v is not specified, the variable of the argument of the latest ptogf2n() call. The default variable is x.

[1] setmod_ff(x^30+x+1);
x^30+x+1
[2] N=simp_ff(gf2ntop(2^100));
(@^13+@^12+@^11+@^10)
[5] gf2ntop(N);
[207] gf2ntop(N);
x^13+x^12+x^11+x^10
[208] gf2ntop(N,t);
t^13+t^12+t^11+t^10

References

ptogf2n

10.5.13 ptosfp, sfptop

ptosfp(p)

sfptop(p)

:: Transformation to/from a small finite field

return

polynomial

p

polynomial

• ptosfp() converts coefficients of a polynomial to elements in a small finite field GF(p^n) set as a ground field. If a coefficient is already an element of the field, no conversion is done. If a coefficient is a positive integer, then its residue modulo p^n is expanded as p-adic integer, then p is substituted by x, finally the polynomial is converted to its correspoding logarithmic representation with respect to the primitive element. For example, GF(3^5) is represented as F(3)[x]/(x^5+2*x+1), and each element of the field is represented as @_k by its exponent k with respect to the primitive element x. 23 = 2*3^2+3+2 is represented as 2*x^2+x+2 and it is equivalent to x^17 modulo x^5+2*x+1. Therefore an integer 23 is conterted to @_17.
• sfptop() is the inverse of ptosfp().

[196] setmod_ff(3,5);
[3,x^5+2*x+1,x]
[197] A = ptosfp(23);
@_17
[198] 9*2+3+2;
23
[199] x^17-(2*x^2+x+2); 
x^17-2*x^2-x-2
[200] sremm(@,x^5+2*x+1,3);
0
[201] sfptop(A);
23

References

setmod_ff, simp_ff

10.5.14 defpoly_mod2

defpoly_mod2(d)

:: Generates an irreducible univariate polynomial over GF(2).

return

univariate polynomial

d

positive integer

• Defined in ‘fff’.
• An irreducible univariate polynomial of degree d is returned.
• If an irreducible trinomial x^d+x^m+1 exists, then the one with the smallest m is returned. Otherwise, an irreducible pentanomial x^d+x^m1+x^m2+x^m3+1 (m1>m2>m3 is returned. m1, m2 and m3 are determined as follows: Fix m1 as small as possible. Then fix m2 as small as possible. Then fix m3 as small as possible.

References

setmod_ff

10.5.15 sffctr

sffctr(poly)

:: Irreducible factorization over a small finite field.

return

list

poly

polynomial over a finite field

• Factorize poly into irreducible factors over a small finite field currently set.
• The result is a list [[f1,m1],[f2,m2],...], where fi is a monic irreducible factor and mi is its multiplicity.

[0] setmod_ff(2,10);
[2,x^10+x^3+1,x]
[1] sffctr((z*y^3+z*y)*x^3+(y^5+y^3+z*y^2+z)*x^2+z^11*y*x+z^10*y^3+z^11);
[[@_0,1],[@_0*z*y*x+@_0*y^3+@_0*z,1],[(@_0*y+@_0)*x+@_0*z^5,2]]

References

setmod_ff, modfctr

10.5.16 fctr_ff

fctr_ff(poly)

:: Irreducible univariate factorization over a finite field.

return

list

poly

univariate polynomial over a finite field

• Defined in ‘fff’.
• Factorize poly into irreducible factors over the current base field.
• The result is a list [[f1,m1],[f2,m2],...], where fi is a monic irreducible factor and mi is its multiplicity.
• The leading coefficient of poly is abandoned.

[178] setmod_ff(2^64-95);
18446744073709551521
[179]  fctr_ff(x^5+x+1); 
[[1*x+14123390394564558010,1],[1*x+6782485570826905238,1],
[1*x+15987612182027639793,1],[1*x^2+1*x+1,1]]

References

setmod_ff

10.5.17 irredcheck_ff

irredcheck_ff(poly)

:: Primality check of a univariate polynomial over a finite field.

return

0|1

poly

univariate polynomial over a finite field

• Defined in ‘fff’.
• Returns 1 if poly is irreducible over the current base field. Returns 0 otherwise.

[178] setmod_ff(2^64-95);
18446744073709551521
[179] ] F=x^10+random_ff();
x^10+14687973587364016969
[180] irredcheck_ff(F);  
1

References

setmod_ff

10.5.18 randpoly_ff

randpoly_ff(d,v)

:: Generation of a random univariate polynomial over a finite field.

return

polynomial

d

positive integer

v

indeterminate

• Defined in ‘fff’.
• Generates a polynomial of v such that the degree is less than d and the coefficients are in the current base field. The coefficients are generated by random_ff().

[178] setmod_ff(2^64-95);
18446744073709551521
[179] ] F=x^10+random_ff();
[180] randpoly_ff(3,x);
17135261454578964298*x^2+4766826699653615429*x+18317369440429479651
[181] randpoly_ff(3,x);
7565988813172050604*x^2+7430075767279665339*x+4699662986224873544
[182] randpoly_ff(3,x);
10247781277095450395*x^2+10243690944992524936*x+4063829049268845492

References

setmod_ff, random_ff

10.5.19 ecm_add_ff, ecm_sub_ff, ecm_chsgn_ff

ecm_add_ff(p1,p2,ec)

ecm_sub_ff(p1,p2,ec)

ecm_chsgn_ff(p1)

:: Addition, Subtraction and additive inverse for points on an elliptic curve.

return

vector or 0

p1 p2

vector of length 3 or 0

ec

vector of length 2

• Let p1, p2 be points on the elliptic curve represented by ec over the current base field. ecm_add_ff(p1,p2,ec), ecm_sub_ff(p1,p2,ec) and ecm_chsgn_ff(p1) returns p1+p2, p1-p2 and -p1 respectively.
• If the current base field is a prime field of odd order, then ec represents y^2=x^3+ec[0]x+ec[1]. If the characteristic of the current base field is 2, then ec represents y^2+xy=x^3+ec[0]x^2+ec[1].
• The point at infinity is represented by 0.
• If an argument denoting a point is a vector of length 3, then it is the projective coordinate. In such a case the third coordinate must not be 0.
• If the result is a vector of length 3, then the third coordinate is not equal to 0 but not necessarily 1. To get the result by the affine coordinate, the first and the second coordinates should be divided by the third coordinate.
• The check whether the arguments are on the curve is omitted.

[0] setmod_ff(1125899906842679)$
[1] EC=newvect(2,[ptolmp(1),ptolmp(1)])$
[2] Pt1=newvect(3,[1,-412127497938252,1])$
[3] Pt2=newvect(3,[6,-252647084363045,1])$
[4] Pt3=ecm_add_ff(Pt1,Pt2,EC);
[ 560137044461222 184453736165476 125 ]
[5] F=y^2-(x^3+EC[0]*x+EC[1])$
[6] subst(F,x,Pt3[0]/Pt3[2],y,Pt3[1]/Pt3[2]);
0
[7] ecm_add_ff(Pt3,ecm_chsgn_ff(Pt3),EC);
0
[8] D=ecm_sub_ff(Pt3,Pt2,EC);
[ 886545905133065 119584559149586 886545905133065 ]
[9] D[0]/D[2]==Pt1[0]/Pt1[2];
1
[10] D[1]/D[2]==Pt1[1]/Pt1[2];
1

References

setmod_ff

This document was generated on April 25, 2024 using texi2html 5.0.