Ask Your Question
0

Factorization sequence to enumerated sequence in Sage

asked 2017-11-20 12:22:19 -0600

whatever gravatar image

updated 2017-11-20 12:22:52 -0600

I have the following Magma code that I want to rewrite in Sage:

Eltseq(Random(FiniteField(2^8)));

This basically produces the following result: [ 0, 1, 0, 1, 1, 1, 0, 1 ]. The function Eltseqis defined as this in the documentation (https://magma.maths.usyd.edu.au/magma...):

Given a factorization sequence f, create the enumerated sequence containing the same pairs of primes and exponents.

Any ideas how can I rewrite this line in Sage?

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
1

answered 2017-11-20 19:42:33 -0600

dan_fulea gravatar image

Short answer: For an element f of a finite field F with 2^K elements, one can use for instance its integer representation, then take its binary digits, padded to K digits (at least). For instance, here are three random elements of F, written as sequences.

sage: for _ in range( 3 ):
....:     ZZ( GF(2**8).random_element().integer_representation() ).digits(base=2, padto=8)
....:     
[0, 1, 0, 1, 1, 0, 0, 1]
[0, 0, 0, 1, 0, 1, 1, 1]
[0, 0, 1, 0, 0, 0, 0, 1]

Longer answer. Let us try to reproduce the following output of magma:

Code (magma), executed at http://magma.maths.usyd.edu.au/calc/ :

F := FiniteField(2^8); F;

r := Random(F); r; Eltseq( r );
r := Random(F); r; Eltseq( r );
r := Random(F); r; Eltseq( r );
"\n---------------------------";

for k := 0 to 10 do 
    Eltseq( F.1^k ); 
end for;

Results:

Finite field of size 2^8
F.1^24
[ 1, 1, 1, 1, 0, 0, 0, 1 ]
F.1^192
[ 0, 1, 0, 0, 0, 0, 0, 1 ]
F.1^98
[ 1, 1, 0, 0, 0, 0, 1, 0 ]

---------------------------
[ 1, 0, 0, 0, 0, 0, 0, 0 ]
[ 0, 1, 0, 0, 0, 0, 0, 0 ]
[ 0, 0, 1, 0, 0, 0, 0, 0 ]
[ 0, 0, 0, 1, 0, 0, 0, 0 ]
[ 0, 0, 0, 0, 1, 0, 0, 0 ]
[ 0, 0, 0, 0, 0, 1, 0, 0 ]
[ 0, 0, 0, 0, 0, 0, 1, 0 ]
[ 0, 0, 0, 0, 0, 0, 0, 1 ]
[ 1, 0, 1, 1, 1, 0, 0, 0 ]
[ 0, 1, 0, 1, 1, 1, 0, 0 ]
[ 0, 0, 1, 0, 1, 1, 1, 0 ]

Let us try to reproduce the above in a dialog with the sage interpreter. Magma is a foreign language for me, but somehow i suppose that F.1 is the class of $x$ if we model the field with $2^8$ elements as $\mathbb F_2[x]$ modulo the polynomial that can be extracted from the line where we print F.1^8 . So let us first construct the field in sage.

sage: R.<X> = GF(2)[]
sage: R
Univariate Polynomial Ring in X over Finite Field of size 2 (using NTL)
sage: #magma -> F.1^8 is [ 1, 0, 1, 1, 1, 0, 0, 0 ]
sage: F.<a> = GF( 2**8 , modulus = 1 + X^2 + X^3 + X^4 + X^8 )

Now let us print the corresponding series for the powers $a^k$, where $k=24,192,98$:

sage: for k in ( 24, 192, 98 ):
....:     f = a^k
....:     print "%3d" % k, ZZ( f.integer_representation() ).digits(base=2, padto=8)
....:     
 24 [1, 1, 1, 1, 0, 0, 0, 1]
192 [0, 1, 0, 0, 0, 0, 0, 1]
 98 [1, 1, 0, 0, 0, 0, 1, 0]

Yes, as above. Same for the first powers of $a$:

sage: for k in [0..10]:
....:     f = a^k
....:     print "%3d" % k, ZZ( f.integer_representation() ).digits(base=2, padto=8)
....:     
  0 [1, 0, 0, 0, 0, 0, 0, 0]
  1 [0, 1, 0, 0, 0, 0, 0, 0]
  2 [0, 0, 1, 0, 0, 0, 0, 0]
  3 [0, 0, 0, 1, 0, 0, 0, 0]
  4 [0, 0, 0, 0, 1, 0, 0, 0]
  5 [0, 0, 0, 0, 0, 1, 0, 0]
  6 [0, 0, 0, 0, 0, 0, 1, 0]
  7 [0, 0, 0, 0, 0, 0, 0, 1]
  8 [1, 0, 1, 1, 1, 0, 0, 0]
  9 [0, 1, 0, 1, 1, 1, 0, 0]
 10 [0, 0, 1, 0, 1, 1, 1, 0]
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

1 follower

Stats

Asked: 2017-11-20 12:22:19 -0600

Seen: 32 times

Last updated: Nov 20