Post new topic Reply to topic  [ 3 posts ] 
Author Message
 Post subject: solving multivariate equations over finite field
PostPosted: Sat Jul 30, 2011 2:10 pm 

Joined: Wed Jul 27, 2011 3:49 pm
Posts: 1
Location: Hungary
As part of my master's thesis I started to write a solver for systems of multivariate polynomial equations over finite fields.

I am curious if there is any work in progress in this field or in finding roots of univariate polynomials with coefficients in GF(p^n)?


Report this post
Top
 Profile  
Reply with quote  
 Post subject: Re: solving multivariate equations over finite field
PostPosted: Mon Aug 01, 2011 3:20 pm 

Joined: Wed Mar 03, 2010 5:08 pm
Posts: 108
Location: Germany, Münster
See the discussion in the forum:

Solving systems of polynomials over GF(2)
viewtopic.php?f=10&t=1908

combined with

...declaration of ring or galois field
viewtopic.php?f=10&t=1823


Report this post
Top
 Profile  
Reply with quote  
 Post subject: Re: solving multivariate equations over finite field
PostPosted: Mon Aug 01, 2011 3:41 pm 

Joined: Wed Mar 03, 2010 5:08 pm
Posts: 108
Location: Germany, Münster
http://www.singular.uni-kl.de/Manual/la ... htm#SEC766

Edit: see the Note

http://www.singular.uni-kl.de/Manual/la ... htm#SEC256

Singular can (at the moment) not factorize over GF(p^n) for baserings
defined as ring r =(p^n,a),....

So you have to choose the fir st form by setting the minpoly yourself.
Code:
> ring ra5 = (25,a),(x,y,z),dp;
> poly f = (x+y)*(z-x);
> factorize(f);
   ? not implemented
   ? error occurred in or before STDIN line 9: `factorize(f);`
> basering;
//   # ground field : 25
//   primitive element : a
//   minpoly        : 1*a^2+4*a^1+2*a^0
//   number of vars : 3
//        block   1 : ordering dp
//                  : names    x y z
//        block   2 : ordering C
> ring ra25 = (5,a),(x,y,z),lp;
> minpoly = 1*a^2+4*a^1+2*a^0;
> poly f = (x+y)*(z-x);
> factorize(f);
[1]:
   _[1]=1
   _[2]=x+y
   _[3]=-x+z
[2]:
   1,1,1


Code:
> LIB "general.lib";
> cyclic(3);
_[1]=x+y+z
_[2]=xy+xz+yz
_[3]=xyz-1
> ideal I = _;
> option(redSB);
> facstd(I);
[1]:
   _[1]=z+(-2a-1)
   _[2]=y+(2a+2)
   _[3]=x-1
[2]:
   _[1]=z-1
   _[2]=y+(-2a-1)
   _[3]=x+(2a+2)
[3]:
   _[1]=z+(2a+2)
   _[2]=y-1
   _[3]=x+(-2a-1)
[4]:
   _[1]=z-1
   _[2]=y+(2a+2)
   _[3]=x+(-2a-1)
[5]:
   _[1]=z+(2a+2)
   _[2]=y+(-2a-1)
   _[3]=x-1
[6]:
   _[1]=z+(-2a-1)
   _[2]=y-1
   _[3]=x+(2a+2)

Then check also
triang.lib
http://www.singular.uni-kl.de/Manual/la ... tm#SEC1556

Code:
> triangLfak(std(I));
[1]:
   _[1]=z-1
   _[2]=y+(-2a-1)
   _[3]=x+(2a+2)
[2]:
   _[1]=z-1
   _[2]=y+(2a+2)
   _[3]=x+(-2a-1)
[3]:
   _[1]=z+(-2a-1)
   _[2]=y-1
   _[3]=x+(2a+2)
[4]:
   _[1]=z+(-2a-1)
   _[2]=y+(2a+2)
   _[3]=x-1
[5]:
   _[1]=z+(2a+2)
   _[2]=y+(-2a-1)
   _[3]=x-1
[6]:
   _[1]=z+(2a+2)
   _[2]=y-1
   _[3]=x+(-2a-1)


Report this post
Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 3 posts ] 

You can post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

It is currently Fri May 13, 2022 11:05 am
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group