[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

10.5 Functions for Finite fields


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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

[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


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

10.5.2 field_type_ff

field_type_ff()

:: Type of the current base field.

return

integer

[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


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

10.5.3 field_order_ff

field_order_ff()

:: Order of the current base field.

return

integer

[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


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

10.5.4 characteristic_ff

characteristic_ff()

:: Characteristic of the current base field.

return

integer

[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


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

10.5.5 extdeg_ff

extdeg_ff()

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

return

integer

[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


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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

[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


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

10.5.7 random_ff

random_ff()

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

return

element of a finite field

[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


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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)

[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


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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

[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


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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)

[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


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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

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

gf2ntop


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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

[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


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

10.5.13 ptosfp, sfptop

ptosfp(p)
sfptop(p)

:: Transformation to/from a small finite field

return

polynomial

p

polynomial

[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


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

10.5.14 defpoly_mod2

defpoly_mod2(d)

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

return

univariate polynomial

d

positive integer

References

setmod_ff


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

10.5.15 sffctr

sffctr(poly)

:: Irreducible factorization over a small finite field.

return

list

poly

polynomial over a finite field

[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


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

10.5.16 fctr_ff

fctr_ff(poly)

:: Irreducible univariate factorization over a finite field.

return

list

poly

univariate polynomial over a finite field

[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


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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

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

setmod_ff


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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

[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


[ << ] [ < ] [ Up ] [ > ] [ >> ]         [Top] [Contents] [Index] [ ? ]

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

[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


[ << ] [ < ] [ Up ] [ > ] [ >> ]

This document was generated on October 24, 2017 using texi2html 5.0.