Magma function for modulo irreducible polynomial
$begingroup$
So, I am trying to make a program in Magma which returns the value table of a given function F over a field $GF(2^n)$. To do so I need a irreducible polyomial. For example, I've considered $GF(2^3)$ and the irreducible polynomial $p(x)=x^3+x+1$.
My program started like this:
F<a>:=GF(2^3);
for i in F do
i mod a^3+a+1;
end for;
The 'mod' apperantly only works with integers, is there a polynomial version for this?
finite-fields irreducible-polynomials cryptography magma-cas magma
asked Dec 20 '18 at 12:40
zermelovaczermelovac
504212
$endgroup$
add a comment |
$begingroup$
So, I am trying to make a program in Magma which returns the value table of a given function F over a field $GF(2^n)$. To do so I need a irreducible polyomial. For example, I've considered $GF(2^3)$ and the irreducible polynomial $p(x)=x^3+x+1$.
My program started like this:
F<a>:=GF(2^3);
for i in F do
i mod a^3+a+1;
end for;
The 'mod' apperantly only works with integers, is there a polynomial version for this?
finite-fields irreducible-polynomials cryptography magma-cas magma
asked Dec 20 '18 at 12:40
zermelovaczermelovac
504212
$endgroup$
add a comment |
$begingroup$
So, I am trying to make a program in Magma which returns the value table of a given function F over a field $GF(2^n)$. To do so I need a irreducible polyomial. For example, I've considered $GF(2^3)$ and the irreducible polynomial $p(x)=x^3+x+1$.
My program started like this:
F<a>:=GF(2^3);
for i in F do
i mod a^3+a+1;
end for;
The 'mod' apperantly only works with integers, is there a polynomial version for this?
finite-fields irreducible-polynomials cryptography magma-cas magma
asked Dec 20 '18 at 12:40
zermelovaczermelovac
504212
$endgroup$
So, I am trying to make a program in Magma which returns the value table of a given function F over a field $GF(2^n)$. To do so I need a irreducible polyomial. For example, I've considered $GF(2^3)$ and the irreducible polynomial $p(x)=x^3+x+1$.
My program started like this:
F<a>:=GF(2^3);
for i in F do
i mod a^3+a+1;
end for;
The 'mod' apperantly only works with integers, is there a polynomial version for this?
finite-fields irreducible-polynomials cryptography magma-cas magma
finite-fields irreducible-polynomials cryptography magma-cas magma
asked Dec 20 '18 at 12:40
zermelovaczermelovac
504212
asked Dec 20 '18 at 12:40
zermelovaczermelovac
504212
asked Dec 20 '18 at 12:40
zermelovaczermelovac
504212
asked Dec 20 '18 at 12:40
zermelovaczermelovac
504212
asked Dec 20 '18 at 12:40
zermelovaczermelovac
504212
504212
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
The mod function works for polynomials, provided they are recognized by Magma as being elements in a polynomial ring. For example, put F := GF(2); and P<a> := PolynomialRing(F); and you will get the results you want if you ask for a^i mod a^3+a+1;.
Alternately, specific for your finite field example, you can put F<a> := GF(2^3); which you can verify is constructed with $x^3+x+1$ as the minimal polynomial for a (ask for DefiningPolynomial(F);). By default, Magma will print elements of F as powers of a, but if you put in the command SetPowerPrinting(F,false); it will give you a reduced polynomial in a instead. So then you can just type a^i; and it will return this field element as the remainder when divided by $a^3+a+1$.
(Note that if you type both F<a> := GF(2^3); and P<a> := PolynomialRing(F); then you have introduced some confusion as to whether a is a finite field element, or an indeterminate in your polynomial ring. You should really avoid doing this.)
answered Jan 7 at 22:07
Morgan RodgersMorgan Rodgers
9,71021439
$endgroup$
add a comment |
$begingroup$
I managed to make the program.
F<a>:=GF(2^3);
P<a>:=PolynomialRing(F);
function f(x)
return x^5;
end function;
A:=;
for i in [1..6] do
Append(~A, (a^i mod (a^3+a+1)));
end for;
A:=Reverse(A);
A:=Append(A,1);
A:=Append(A,0);
A:=Reverse(A);
F:=;
for i in [1..6] do
Append(~F,((f(a))^i mod (a^3+a+1)));
end for;
F:=Reverse(F);
F:=Append(F,1);
F:=Append(F,0);
F:=Reverse(F);
BinA:=;
for i in A do
for j in [a^2,a,1] do
if j in Terms(i) then
Append(~BinA,1);
else
Append(~BinA,0);
end if;
end for;
end for;
BinA:=Matrix(3,BinA);
BinF:=;
for i in F do
for j in [a^2,a,1] do
if j in Terms(i) then
Append(~BinF,1);
else
Append(~BinF,0);
end if;
end for;
end for;
print BinF;
answered Dec 20 '18 at 18:54
zermelovaczermelovac
504212
$endgroup$
$begingroup$
You could just doSetPowerPrinting(F,false);and then typing ina^iwill automatically give you the reduced form modulo the defining polynomial of the field (which is coincidentally $x^{3}+x+1$).
$endgroup$
– Morgan Rodgers
Dec 21 '18 at 6:52
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3047486%2fmagma-function-for-modulo-irreducible-polynomial%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The mod function works for polynomials, provided they are recognized by Magma as being elements in a polynomial ring. For example, put F := GF(2); and P<a> := PolynomialRing(F); and you will get the results you want if you ask for a^i mod a^3+a+1;.
Alternately, specific for your finite field example, you can put F<a> := GF(2^3); which you can verify is constructed with $x^3+x+1$ as the minimal polynomial for a (ask for DefiningPolynomial(F);). By default, Magma will print elements of F as powers of a, but if you put in the command SetPowerPrinting(F,false); it will give you a reduced polynomial in a instead. So then you can just type a^i; and it will return this field element as the remainder when divided by $a^3+a+1$.
(Note that if you type both F<a> := GF(2^3); and P<a> := PolynomialRing(F); then you have introduced some confusion as to whether a is a finite field element, or an indeterminate in your polynomial ring. You should really avoid doing this.)
answered Jan 7 at 22:07
Morgan RodgersMorgan Rodgers
9,71021439
$endgroup$
add a comment |
$begingroup$
The mod function works for polynomials, provided they are recognized by Magma as being elements in a polynomial ring. For example, put F := GF(2); and P<a> := PolynomialRing(F); and you will get the results you want if you ask for a^i mod a^3+a+1;.
Alternately, specific for your finite field example, you can put F<a> := GF(2^3); which you can verify is constructed with $x^3+x+1$ as the minimal polynomial for a (ask for DefiningPolynomial(F);). By default, Magma will print elements of F as powers of a, but if you put in the command SetPowerPrinting(F,false); it will give you a reduced polynomial in a instead. So then you can just type a^i; and it will return this field element as the remainder when divided by $a^3+a+1$.
(Note that if you type both F<a> := GF(2^3); and P<a> := PolynomialRing(F); then you have introduced some confusion as to whether a is a finite field element, or an indeterminate in your polynomial ring. You should really avoid doing this.)
answered Jan 7 at 22:07
Morgan RodgersMorgan Rodgers
9,71021439
$endgroup$
add a comment |
$begingroup$
The mod function works for polynomials, provided they are recognized by Magma as being elements in a polynomial ring. For example, put F := GF(2); and P<a> := PolynomialRing(F); and you will get the results you want if you ask for a^i mod a^3+a+1;.
Alternately, specific for your finite field example, you can put F<a> := GF(2^3); which you can verify is constructed with $x^3+x+1$ as the minimal polynomial for a (ask for DefiningPolynomial(F);). By default, Magma will print elements of F as powers of a, but if you put in the command SetPowerPrinting(F,false); it will give you a reduced polynomial in a instead. So then you can just type a^i; and it will return this field element as the remainder when divided by $a^3+a+1$.
(Note that if you type both F<a> := GF(2^3); and P<a> := PolynomialRing(F); then you have introduced some confusion as to whether a is a finite field element, or an indeterminate in your polynomial ring. You should really avoid doing this.)
answered Jan 7 at 22:07
Morgan RodgersMorgan Rodgers
9,71021439
$endgroup$
The mod function works for polynomials, provided they are recognized by Magma as being elements in a polynomial ring. For example, put F := GF(2); and P<a> := PolynomialRing(F); and you will get the results you want if you ask for a^i mod a^3+a+1;.
Alternately, specific for your finite field example, you can put F<a> := GF(2^3); which you can verify is constructed with $x^3+x+1$ as the minimal polynomial for a (ask for DefiningPolynomial(F);). By default, Magma will print elements of F as powers of a, but if you put in the command SetPowerPrinting(F,false); it will give you a reduced polynomial in a instead. So then you can just type a^i; and it will return this field element as the remainder when divided by $a^3+a+1$.
(Note that if you type both F<a> := GF(2^3); and P<a> := PolynomialRing(F); then you have introduced some confusion as to whether a is a finite field element, or an indeterminate in your polynomial ring. You should really avoid doing this.)
answered Jan 7 at 22:07
Morgan RodgersMorgan Rodgers
9,71021439
answered Jan 7 at 22:07
Morgan RodgersMorgan Rodgers
9,71021439
answered Jan 7 at 22:07
Morgan RodgersMorgan Rodgers
9,71021439
answered Jan 7 at 22:07
Morgan RodgersMorgan Rodgers
9,71021439
9,71021439
add a comment |
add a comment |
$begingroup$
I managed to make the program.
F<a>:=GF(2^3);
P<a>:=PolynomialRing(F);
function f(x)
return x^5;
end function;
A:=;
for i in [1..6] do
Append(~A, (a^i mod (a^3+a+1)));
end for;
A:=Reverse(A);
A:=Append(A,1);
A:=Append(A,0);
A:=Reverse(A);
F:=;
for i in [1..6] do
Append(~F,((f(a))^i mod (a^3+a+1)));
end for;
F:=Reverse(F);
F:=Append(F,1);
F:=Append(F,0);
F:=Reverse(F);
BinA:=;
for i in A do
for j in [a^2,a,1] do
if j in Terms(i) then
Append(~BinA,1);
else
Append(~BinA,0);
end if;
end for;
end for;
BinA:=Matrix(3,BinA);
BinF:=;
for i in F do
for j in [a^2,a,1] do
if j in Terms(i) then
Append(~BinF,1);
else
Append(~BinF,0);
end if;
end for;
end for;
print BinF;
answered Dec 20 '18 at 18:54
zermelovaczermelovac
504212
$endgroup$
$begingroup$
You could just doSetPowerPrinting(F,false);and then typing ina^iwill automatically give you the reduced form modulo the defining polynomial of the field (which is coincidentally $x^{3}+x+1$).
$endgroup$
– Morgan Rodgers
Dec 21 '18 at 6:52
add a comment |
$begingroup$
I managed to make the program.
F<a>:=GF(2^3);
P<a>:=PolynomialRing(F);
function f(x)
return x^5;
end function;
A:=;
for i in [1..6] do
Append(~A, (a^i mod (a^3+a+1)));
end for;
A:=Reverse(A);
A:=Append(A,1);
A:=Append(A,0);
A:=Reverse(A);
F:=;
for i in [1..6] do
Append(~F,((f(a))^i mod (a^3+a+1)));
end for;
F:=Reverse(F);
F:=Append(F,1);
F:=Append(F,0);
F:=Reverse(F);
BinA:=;
for i in A do
for j in [a^2,a,1] do
if j in Terms(i) then
Append(~BinA,1);
else
Append(~BinA,0);
end if;
end for;
end for;
BinA:=Matrix(3,BinA);
BinF:=;
for i in F do
for j in [a^2,a,1] do
if j in Terms(i) then
Append(~BinF,1);
else
Append(~BinF,0);
end if;
end for;
end for;
print BinF;
answered Dec 20 '18 at 18:54
zermelovaczermelovac
504212
$endgroup$
$begingroup$
You could just doSetPowerPrinting(F,false);and then typing ina^iwill automatically give you the reduced form modulo the defining polynomial of the field (which is coincidentally $x^{3}+x+1$).
$endgroup$
– Morgan Rodgers
Dec 21 '18 at 6:52
add a comment |
$begingroup$
I managed to make the program.
F<a>:=GF(2^3);
P<a>:=PolynomialRing(F);
function f(x)
return x^5;
end function;
A:=;
for i in [1..6] do
Append(~A, (a^i mod (a^3+a+1)));
end for;
A:=Reverse(A);
A:=Append(A,1);
A:=Append(A,0);
A:=Reverse(A);
F:=;
for i in [1..6] do
Append(~F,((f(a))^i mod (a^3+a+1)));
end for;
F:=Reverse(F);
F:=Append(F,1);
F:=Append(F,0);
F:=Reverse(F);
BinA:=;
for i in A do
for j in [a^2,a,1] do
if j in Terms(i) then
Append(~BinA,1);
else
Append(~BinA,0);
end if;
end for;
end for;
BinA:=Matrix(3,BinA);
BinF:=;
for i in F do
for j in [a^2,a,1] do
if j in Terms(i) then
Append(~BinF,1);
else
Append(~BinF,0);
end if;
end for;
end for;
print BinF;
answered Dec 20 '18 at 18:54
zermelovaczermelovac
504212
$endgroup$
I managed to make the program.
F<a>:=GF(2^3);
P<a>:=PolynomialRing(F);
function f(x)
return x^5;
end function;
A:=;
for i in [1..6] do
Append(~A, (a^i mod (a^3+a+1)));
end for;
A:=Reverse(A);
A:=Append(A,1);
A:=Append(A,0);
A:=Reverse(A);
F:=;
for i in [1..6] do
Append(~F,((f(a))^i mod (a^3+a+1)));
end for;
F:=Reverse(F);
F:=Append(F,1);
F:=Append(F,0);
F:=Reverse(F);
BinA:=;
for i in A do
for j in [a^2,a,1] do
if j in Terms(i) then
Append(~BinA,1);
else
Append(~BinA,0);
end if;
end for;
end for;
BinA:=Matrix(3,BinA);
BinF:=;
for i in F do
for j in [a^2,a,1] do
if j in Terms(i) then
Append(~BinF,1);
else
Append(~BinF,0);
end if;
end for;
end for;
print BinF;
answered Dec 20 '18 at 18:54
zermelovaczermelovac
504212
answered Dec 20 '18 at 18:54
zermelovaczermelovac
504212
answered Dec 20 '18 at 18:54
zermelovaczermelovac
504212
answered Dec 20 '18 at 18:54
zermelovaczermelovac
504212
504212
$begingroup$
You could just doSetPowerPrinting(F,false);and then typing ina^iwill automatically give you the reduced form modulo the defining polynomial of the field (which is coincidentally $x^{3}+x+1$).
$endgroup$
– Morgan Rodgers
Dec 21 '18 at 6:52
add a comment |
$begingroup$
You could just doSetPowerPrinting(F,false);and then typing ina^iwill automatically give you the reduced form modulo the defining polynomial of the field (which is coincidentally $x^{3}+x+1$).
$endgroup$
– Morgan Rodgers
Dec 21 '18 at 6:52
$begingroup$
You could just do
SetPowerPrinting(F,false); and then typing in a^i will automatically give you the reduced form modulo the defining polynomial of the field (which is coincidentally $x^{3}+x+1$).$endgroup$
– Morgan Rodgers
Dec 21 '18 at 6:52
$begingroup$
You could just do
SetPowerPrinting(F,false); and then typing in a^i will automatically give you the reduced form modulo the defining polynomial of the field (which is coincidentally $x^{3}+x+1$).$endgroup$
– Morgan Rodgers
Dec 21 '18 at 6:52
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3047486%2fmagma-function-for-modulo-irreducible-polynomial%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
