Ask Your Question
2

list of random non-zero elements

asked 2018-09-13 04:14:36 -0500

Parker gravatar image

updated 2018-09-13 11:27:34 -0500

I was wondering if there was a short way to generate lists of random non-zero elements of GF(q) ? What I have so far is:

  L=[];  
  for i in range(10):  
     a=GF(25).random_element();  
     while a==0:  
         a=GF(25).random_element();  
     L.append(a);
edit retag flag offensive close merge delete

Comments

You don't actually need the semicolons at the end of the lines, by the way.

John Palmieri gravatar imageJohn Palmieri ( 2018-09-13 11:28:13 -0500 )edit

2 answers

Sort by » oldest newest most voted
1

answered 2018-09-13 09:06:26 -0500

tmonteil gravatar image

updated 2018-09-14 02:44:53 -0500

If you really want something short, yo can do something along the lines:

sage: from itertools import ifilter, islice
sage: list(islice(ifilter(lambda x: x !=0 , (GF(25).random_element() for _ in ZZ)), 10))

Explanataion:

  • (GF(25).random_element() for _ in ZZ) creates an infinite iterator of random elements of GF(25)
  • ifilter(lambda x: x !=0 , (GF(25).random_element() for _ in ZZ)) creates an iterator that filters the nonzero elements
  • islice(ifilter(lambda x: x !=0 , (GF(25).random_element() for _ in ZZ)), 10) creates an iterator that produces only the first 10 elements of the previous iterator
  • list(islice(ifilter(lambda x: x !=0 , (GF(25).random_element() for _ in ZZ)), 10)) transforms the previous iterator into a list

As for the first line, itertools is a standard module with very nice tools for creating iterators.

That said, if you do:

sage: import this

You will see that Readability counts, so your code is probably the best since you will be able to understand and modify it later.

EDIIT, if you want to use it when Sage will use Python3, you just have to replace the imported ifilter with the builtin filter:

sage: from itertools import islice
sage: list(islice(filter(lambda x: x !=0 , (GF(25).random_element() for _ in ZZ)), 10))
edit flag offensive delete link more

Comments

not compatible with python3...

FrédéricC gravatar imageFrédéricC ( 2018-09-13 09:33:28 -0500 )edit

@FrédéricC - thanks for watching! This got me started on an alternative solution, see my answer.

slelievre gravatar imageslelievre ( 2018-09-13 18:57:30 -0500 )edit

I updated to provide a solution that works when Sage will use Python 3.

tmonteil gravatar imagetmonteil ( 2018-09-14 02:45:24 -0500 )edit
1

answered 2018-09-13 18:53:22 -0500

slelievre gravatar image

updated 2018-09-13 19:16:07 -0500

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.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2018-09-13 04:14:36 -0500

Seen: 46 times

Last updated: Sep 14