Revision history [back]
 | 1 | initial version |
Random nonzero elements in a finite field
Idea
Let $q = p^n$ for some prime $p$ and some integer $n \ge 1$, and let $F_q$ be the field with $q$ elements, and $F_p$ the field with $p$ elements.
Recall that $F_q$ is a vector space over the prime field $F_p$, and that for any generator $z$ of $F_q$ as a field extension of $F_p$, the family $(1, z, ..., z^{n-1})$ is a basis of $F_q$ as a vector space over $F_p$.
One way to build a list of random nonzero elements in $F_q$ is to pick coefficients $a_0$, ..., $a_{n-1}$ at random, all between $0$ and $p-1$, but not all zero, and to take the element $\sum a_k z^k$ in $F_q$.
One way to pick such a collection of coefficients is to pick an integer at random between $1$ and $q-1$ and to let $a_k$ be its $k$-th digit in base $p$.
Implementation
Choose $p$ and $n$, define $q = p^n$, and let $F$ be the finite field with $q$ elements.
sage: p = 5
sage: n = 3
sage: q = p^n
sage: F = GF(q)
Choose $m$, the number of random elements to pick.
sage: m = 10
Produce a list of length $m$ of random nonzero elements in $F$.
sage: L = [F(ZZ.random_element(1, q).digits(base=p)) for _ in range(m)]
Explanation
r = ZZ.random_element(1, q)picks a random integer between $1$ and $q - 1$d = r.digits(base=p)gives the list of its digits in base $p$u = F(d)turns this list into a field element, seen a polynomial in $z$ (where $z$ is the generator of $F_q$ as a field extension of $F_p$) with coefficients given by the list.
| | 2 | No.2 Revision |
Random nonzero elements in a finite field
Idea
Let $q = p^n$ for some prime $p$ and some integer $n \ge 1$, and let $F_q$ be the field with $q$ elements, and $F_p$ the field with $p$ elements.
Recall that $F_q$ is a vector space over the prime field $F_p$, and that for any generator $z$ of $F_q$ as a field extension of $F_p$, the family $(1, z, ..., z^{n-1})$ is a basis of $F_q$ as a vector space over $F_p$.
One way to build a list of random nonzero elements in $F_q$ is to pick coefficients $a_0$, ..., $a_{n-1}$ at random, all between $0$ and $p-1$, but not all zero, and to take the element $\sum a_k z^k$ in $F_q$.
One way to pick such a collection of coefficients is to pick an integer at random between $1$ and $q-1$ and to let $a_k$ be its $k$-th digit in base $p$.
Implementation
Choose $p$ and $n$, define $q = p^n$, and let $F$ be the finite field with $q$ elements.
sage: p = 5
sage: n = 3
sage: q = p^n
sage: F = GF(q)
Choose $m$, the number of random elements to pick.
sage: m = 10
Produce a list of length $m$ of random nonzero elements in $F$.
sage: L = [F(ZZ.random_element(1, q).digits(base=p)) for _ in range(m)]
Explanation
r = ZZ.random_element(1, q)picks a random integer between $1$ and $q - 1$d = r.digits(base=p)gives the list of its digits in base $p$u = F(d)turns this list into a field element, seen a polynomial in $z$ (where $z$ is the generator of $F_q$ as a field extension of $F_p$) with coefficients given by the list.
Note on speed
Defining the finite field takes on the order of 0.1 ms.
It is probably worth defining $F$ once and for all, and then picking random
elements in $F$, rather than calling GF(25) inside the loop, which spends
time initializing the finite field at each iteration of the loop.
Of course if you're looping only ten times it doesn't matter much.
