Difference between revisions of "ApCoCoA-1:CharP.MXLSolve"

From ApCoCoAWiki
(New page: <command> <title>CharP.GBasisF2</title> <short_description>Computing the unique <tt>F_2-</tt>rational zero of a given polynomial system over <tt>F_2</tt>.</short_description> <synt...)
 
m (insert version info)
 
(9 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
{{Version|1}}
 
<command>
 
<command>
−
     <title>CharP.GBasisF2</title>
+
     <title>CharP.MXLSolve</title>
−
     <short_description>Computing the unique <tt>F_2-</tt>rational zero of a given polynomial system over <tt>F_2</tt>.</short_description>
+
     <short_description>Computes the unique <tt>F_2-</tt>rational zero of a given polynomial system over <tt>F_2</tt>.</short_description>
 
<syntax>
 
<syntax>
−
CharP.XLSolve(F:LIST):LIST
+
CharP.MXLSolve(F:LIST):LIST
 
</syntax>
 
</syntax>
 
     <description>
 
     <description>
 +
<em>Please note:</em> The function(s) explained on this page is/are using the <em>ApCoCoAServer</em>. You will have to start the ApCoCoAServer in order to use it/them.
 +
 
<par/>
 
<par/>
−
This function computes the unique zero in <tt>F_2^n</tt> of a polynomial system over <tt>F_2 </tt>. It uses XL-Algorithm to find the unique zero. The XL-Algorithm is impelemented only to find a unique solution. If the given polynomial system has more than one zeros in <tt>F_2^n </tt> then this function does not find any zero. In this case a massage for non-uniqueness will be displayed to the screen after reaching the maximum degree bound.
+
This function computes the unique zero in <tt>F_2^n</tt> of a polynomial system over <tt>F_2 </tt>. It uses Mutant XL-Algorithm to find the unique zero. The idea is to linearize the polynomial system by considering terms as indeterminates and then apply gaussian elimination to find a univariate polynomial. If no univariate polynomial is found then the system is extended by generating more polynomials in the ideal and gaussian elimination is applied again. In this way by applying gaussian elimination repeatedly we find the zero of the system. In fact Mutant XL-Algorithm is the XL-Algorithm with mutant strategy. The Mutant XL-Algorithm is implemented only to find the unique zero. If the given polynomial system has more than one zeros in <tt>F_2^n </tt> then this function does not find any zero. In this case a massage for non-uniqueness will be displayed to the screen after reaching the maximum degree bound.  
−
 
 
−
<em>Please note:</em> The function(s) explained on this page is/are using the <em>ApCoCoAServer</em>. You will have to start the ApCoCoAServer in order to use it/them.
 
  
  
 
<itemize>
 
<itemize>
−
<item>@param <em>F</em> A system of polynomial over <tt>F_2</tt> having a unique zero in <tt>F_2^n</tt>. </item>
+
<item>@param <em>F:</em> List of polynomials of given system.</item>
 
<item>@return The unique solution of the given system in <tt>F_2^n</tt>. </item>
 
<item>@return The unique solution of the given system in <tt>F_2^n</tt>. </item>
 
</itemize>
 
</itemize>
  
 
<example>
 
<example>
−
Use R::=QQ[x,y,z];
+
Use Z/(2)[x[1..4]];
−
I:=Ideal(x-y^2,x^2+xy,y^3);
+
F:=[
−
GBasis(I);
+
    x[1]x[2] + x[2]x[3] + x[2]x[4] + x[3]x[4] + x[1] + x[3] + 1,  
−
[x^2 + xy, -y^2 + x, -xy]
+
    x[1]x[2] + x[1]x[3] + x[1]x[4] + x[3]x[4] + x[2] + x[3] + 1,  
 +
    x[1]x[2] + x[1]x[3] + x[2]x[3] + x[3]x[4] + x[1] + x[4] + 1,
 +
    x[1]x[3] + x[2]x[3] + x[1]x[4] + x[2]x[4] + 1
 +
    ];
 +
 
 +
-- Then we compute the solution with
 +
CharP.MXLSolve(F);
 +
 
 +
-- And we achieve the following information on the screen together with the solution at the end.
 +
----------------------------------------
 +
The size of Matrix is:
 +
No. of Rows=4
 +
No. of Columns=11
 +
Appling Gaussian Elimination...
 +
-- CoCoAServer: computing Cpu Time = 0
 +
-------------------------------
 +
Gaussian Elimination Completed.
 +
The size of Matrix is:
 +
No. of Rows=4
 +
No. of Columns=11
 +
Appling Gaussian Elimination...
 +
-- CoCoAServer: computing Cpu Time = 0
 +
-------------------------------
 +
Gaussian Elimination Completed.
 +
The variables found till now, if any are:
 +
[x[1], x[2], x[3], x[4]]
 +
The No. of Mutants found = 0
 +
The size of Matrix is:
 +
No. of Rows=8
 +
No. of Columns=11
 +
Appling Gaussian Elimination...
 +
-- CoCoAServer: computing Cpu Time = 0
 +
-------------------------------
 +
Gaussian Elimination Completed.
 +
The variables found till now, if any are:
 +
[x[1], x[2], x[3], x[4]]
 +
The No. of Mutants found = 1
 +
The size of Matrix is:
 +
No. of Rows=11
 +
No. of Columns=11
 +
Appling Gaussian Elimination...
 +
-- CoCoAServer: computing Cpu Time = 0
 
-------------------------------
 
-------------------------------
−
Use Z::=ZZ[x,y,z];
+
Gaussian Elimination Completed.
−
-- WARNING: Coeffs are not in a field
+
The variables found till now, if any are:
−
-- GBasis-related computations could fail to terminate or be wrong
+
[0, 1, 0, 1]
 +
[0, 1, 0, 1]
 +
 
 +
</example>
 +
 
 +
 
 +
<example>
 +
Use Z/(2)[x[1..4]];
 +
F:=[  
 +
    x[2]x[3] + x[1]x[4] + x[2]x[4] + x[3]x[4] + x[1] + x[2] + x[3] + x[4],  
 +
    x[2]x[3] + x[2]x[4] + x[3]x[4] + x[2] + x[3] + x[4], 
 +
    x[1]x[2] + x[2]x[3] + x[2]x[4] + x[3]x[4] + x[1] + x[2],
 +
    x[1]x[2] + x[2]x[3] + x[2]x[4] + x[3]x[4] + x[1] + x[2]
 +
  ];
 +
 
 +
-- Solution is not unique i.e. [0, 1, 1, 1], [0, 0, 0, 0], and [1, 1, 1, 1] are solutions
 +
 
 +
-- Then we compute the solution with
 +
CharP.MXLSolve(F);
  
 +
-- And we achieve the following information on the screen.
 +
----------------------------------------
 +
The size of Matrix is:
 +
No. of Rows=4
 +
No. of Columns=9
 +
Appling Gaussian Elimination...
 +
-- CoCoAServer: computing Cpu Time = 0
 +
-------------------------------
 +
Gaussian Elimination Completed.
 +
The size of Matrix is:
 +
No. of Rows=3
 +
No. of Columns=9
 +
Appling Gaussian Elimination...
 +
-- CoCoAServer: computing Cpu Time = 0
 +
-------------------------------
 +
Gaussian Elimination Completed.
 +
The variables found till now, if any are:
 +
[x[1], x[2], x[3], x[4]]
 +
The No. of Mutants found = 0
 +
The size of Matrix is:
 +
No. of Rows=14
 +
No. of Columns=14
 +
Appling Gaussian Elimination...
 +
-- CoCoAServer: computing Cpu Time = 0
 +
-------------------------------
 +
Gaussian Elimination Completed.
 +
The variables found till now, if any are:
 +
[x[1], x[2], x[3], x[4]]
 +
The No. of Mutants found = 4
 +
The size of Matrix is:
 +
No. of Rows=27
 +
No. of Columns=14
 +
Appling Gaussian Elimination...
 +
-- CoCoAServer: computing Cpu Time = 0
 +
-------------------------------
 +
Gaussian Elimination Completed.
 +
The variables found till now, if any are:
 +
[x[1], x[2], x[3], x[4]]
 +
The No. of Mutants found = 0
 +
The size of Matrix is:
 +
No. of Rows=12
 +
No. of Columns=14
 +
Appling Gaussian Elimination...
 +
-- CoCoAServer: computing Cpu Time = 0
 
-------------------------------
 
-------------------------------
−
I:=Ideal(x-y^2,x^2+xy,y^3);
+
Gaussian Elimination Completed.
−
CharP.GBasisF2(I);
+
The variables found till now, if any are:
−
-- WARNING: Coeffs are not in a field
+
[x[1], x[2], x[3], x[4]]
−
-- GBasis-related computations could fail to terminate or be wrong
+
The No. of Mutants found = 0
 +
The size of Matrix is:
 +
No. of Rows=19
 +
No. of Columns=15
 +
Appling Gaussian Elimination...
 
-- CoCoAServer: computing Cpu Time = 0
 
-- CoCoAServer: computing Cpu Time = 0
 
-------------------------------
 
-------------------------------
−
[y^2 + x, x^2, xy]
+
Gaussian Elimination Completed.
 +
The variables found till now, if any are:
 +
[x[1], x[2], x[3], x[4]]
 +
The No. of Mutants found = 0
 +
The size of Matrix is:
 +
No. of Rows=14
 +
No. of Columns=15
 +
Appling Gaussian Elimination...
 +
-- CoCoAServer: computing Cpu Time = 0
 
-------------------------------
 
-------------------------------
 +
Gaussian Elimination Completed.
 +
The variables found till now, if any are:
 +
[x[1], x[2], x[3], x[4]]
 +
Please Check the uniqueness of solution.
 +
The Given system of polynomials does not
 +
seem to have a unique solution.
 +
 
</example>
 
</example>
 +
  
 
     </description>
 
     </description>
 
     <seealso>
 
     <seealso>
−
       <see>GBasis</see>
+
       <see>ApCoCoA-1:CharP.XLSolve|CharP.XLSolve</see>
−
     <see>Introduction to CoCoAServer</see>
+
     <see>ApCoCoA-1:Introduction to CoCoAServer|Introduction to CoCoAServer</see>
−
     <see>Introduction to Groebner Basis in CoCoA</see>
+
     <see>ApCoCoA-1:Introduction to Groebner Basis in CoCoA|Introduction to Groebner Basis in CoCoA</see>
−
     <see>CharP.GBasisF4</see>
+
     <see>ApCoCoA-1:CharP.IMNLASolve|CharP.IMNLASolve</see>
−
     <see>CharP.GBasisF8</see>
+
     <see>ApCoCoA-1:CharP.MNLASolve|CharP.MNLASolve</see>
−
     <see>CharP.GBasisF16</see>
+
     <see>ApCoCoA-1:CharP.NLASolve|CharP.NLASolve</see>
−
     <see>CharP.GBasisF32</see>
+
     <see>ApCoCoA-1:CharP.IMXLSolve|CharP.IMXLSolve</see>
−
   
 
 
   </seealso>
 
   </seealso>
  
 
     <types>
 
     <types>
 
       <type>apcocoaserver</type>
 
       <type>apcocoaserver</type>
−
       <type>ideal</type>
+
       <type>poly_system</type>
−
      <type>groebner</type>
 
 
     </types>
 
     </types>
  
−
     <key>charP.GBasisF2</key>
+
     <key>charP.mxlsolve</key>
−
     <key>GBasisF2</key>
+
     <key>mxlsolve</key>
 
     <key>finite field</key>
 
     <key>finite field</key>
−
     <wiki-category>Package_charP</wiki-category>
+
     <wiki-category>ApCoCoA-1:Package_charP</wiki-category>
 
   </command>
 
   </command>

Latest revision as of 09:56, 7 October 2020

This article is about a function from ApCoCoA-1.

CharP.MXLSolve

Computes the unique F_2-rational zero of a given polynomial system over F_2.

Syntax

CharP.MXLSolve(F:LIST):LIST

Description

Please note: The function(s) explained on this page is/are using the ApCoCoAServer. You will have to start the ApCoCoAServer in order to use it/them.


This function computes the unique zero in F_2^n of a polynomial system over F_2 . It uses Mutant XL-Algorithm to find the unique zero. The idea is to linearize the polynomial system by considering terms as indeterminates and then apply gaussian elimination to find a univariate polynomial. If no univariate polynomial is found then the system is extended by generating more polynomials in the ideal and gaussian elimination is applied again. In this way by applying gaussian elimination repeatedly we find the zero of the system. In fact Mutant XL-Algorithm is the XL-Algorithm with mutant strategy. The Mutant XL-Algorithm is implemented only to find the unique zero. If the given polynomial system has more than one zeros in F_2^n then this function does not find any zero. In this case a massage for non-uniqueness will be displayed to the screen after reaching the maximum degree bound.


  • @param F: List of polynomials of given system.

  • @return The unique solution of the given system in F_2^n.

Example

Use Z/(2)[x[1..4]];
F:=[
    x[1]x[2] + x[2]x[3] + x[2]x[4] + x[3]x[4] + x[1] + x[3] + 1, 
    x[1]x[2] + x[1]x[3] + x[1]x[4] + x[3]x[4] + x[2] + x[3] + 1, 
    x[1]x[2] + x[1]x[3] + x[2]x[3] + x[3]x[4] + x[1] + x[4] + 1, 
    x[1]x[3] + x[2]x[3] + x[1]x[4] + x[2]x[4] + 1
    ];

-- Then we compute the solution with
CharP.MXLSolve(F);

-- And we achieve the following information on the screen together with the solution at the end.
----------------------------------------
The size of Matrix is:
		No. of Rows=4
		No. of Columns=11
Appling Gaussian Elimination...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The size of Matrix is:
		No. of Rows=4
		No. of Columns=11
Appling Gaussian Elimination...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The variables found till now, if any are:
	[x[1], x[2], x[3], x[4]]
	The No. of Mutants found = 0
	The size of Matrix is:
		No. of Rows=8
		No. of Columns=11
Appling Gaussian Elimination...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The variables found till now, if any are:
	[x[1], x[2], x[3], x[4]]
	The No. of Mutants found = 1
	The size of Matrix is:
		No. of Rows=11
		No. of Columns=11
Appling Gaussian Elimination...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The variables found till now, if any are:
	[0, 1, 0, 1]
[0, 1, 0, 1]


Example

Use Z/(2)[x[1..4]];
F:=[ 
    x[2]x[3] + x[1]x[4] + x[2]x[4] + x[3]x[4] + x[1] + x[2] + x[3] + x[4], 
    x[2]x[3] + x[2]x[4] + x[3]x[4] + x[2] + x[3] + x[4],  
    x[1]x[2] + x[2]x[3] + x[2]x[4] + x[3]x[4] + x[1] + x[2],  
    x[1]x[2] + x[2]x[3] + x[2]x[4] + x[3]x[4] + x[1] + x[2]
   ];

-- Solution is not unique i.e. [0, 1, 1, 1], [0, 0, 0, 0], and [1, 1, 1, 1] are solutions 

-- Then we compute the solution with
CharP.MXLSolve(F);

-- And we achieve the following information on the screen.
----------------------------------------
The size of Matrix is:
		No. of Rows=4
		No. of Columns=9
Appling Gaussian Elimination...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The size of Matrix is:
		No. of Rows=3
		No. of Columns=9
Appling Gaussian Elimination...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The variables found till now, if any are:
	[x[1], x[2], x[3], x[4]]
	The No. of Mutants found = 0
	The size of Matrix is:
		No. of Rows=14
		No. of Columns=14
Appling Gaussian Elimination...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The variables found till now, if any are:
	[x[1], x[2], x[3], x[4]]
	The No. of Mutants found = 4
	The size of Matrix is:
		No. of Rows=27
		No. of Columns=14
Appling Gaussian Elimination...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The variables found till now, if any are:
	[x[1], x[2], x[3], x[4]]
	The No. of Mutants found = 0
	The size of Matrix is:
		No. of Rows=12
		No. of Columns=14
Appling Gaussian Elimination...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The variables found till now, if any are:
	[x[1], x[2], x[3], x[4]]
	The No. of Mutants found = 0
	The size of Matrix is:
		No. of Rows=19
		No. of Columns=15
Appling Gaussian Elimination...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The variables found till now, if any are:
	[x[1], x[2], x[3], x[4]]
	The No. of Mutants found = 0
	The size of Matrix is:
		No. of Rows=14
		No. of Columns=15
Appling Gaussian Elimination...
-- CoCoAServer: computing Cpu Time = 0
-------------------------------
Gaussian Elimination Completed.
	The variables found till now, if any are:
	[x[1], x[2], x[3], x[4]]
	Please Check the uniqueness of solution.
	The Given system of polynomials does not
	seem to have a unique solution.


See also

CharP.XLSolve

Introduction to CoCoAServer

Introduction to Groebner Basis in CoCoA

CharP.IMNLASolve

CharP.MNLASolve

CharP.NLASolve

CharP.IMXLSolve





Retrieved from "http://apcocoa.uni-passau.de/wiki/index.php?title=ApCoCoA-1:CharP.MXLSolve&oldid=15443"