Singular :: View topic - large exponent of minpoly? (use bigint?)

Author:

gorzel [ Fri Apr 09, 2010 3:27 pm ]

Post subject:

Re: large exponent of minpoly? (use bigint?)

gepo wrote:

This is what i want to compute:

ring r=(2,a),x,dp;
minpoly=a^5+a^3+1; //here is a min polynomial definition
a^12345678987654321;

can I make such a computation? since the exponent is so large, I tried to use bigint:
bigint(a)^12345678987654321;
but failed.
Gepo

No this is not possible in this way.
bigint is only available for the coefficients
(more precisely it is the type number),
but not for the exponents.

Code:

 
6.1 Limitations says

 * the maximal allowed exponent of a ring variable depends on
    the ordering of the ring and is at least 32767. 

First at all, it make not really sense, that you define such a
big exponent for an algebraic extension of degree 5.

Calculation with numbers in GF(25) means that all coefficients
are considered as polynomials reduced by the minimal polynomial
of degree 5.

Hence all coefficients will be polynomial expressions in a with
coefficients 0 or 1 and a degree less or equal to 4.

So suppose you want compute a^23.

Then consider polynomial division in char 2
of X^23 by X^5+X^3+1; where the latter is your minpoly.

Code:

> ring r2 =2,x,dp;
> division(x23, x5+x3+1);
[1]:
   _[1,1]=x18+x16+x14+x13+x12+x10+x9+x5+x4+x3+x2+x
[2]:
   _[1]=x3+x2+x
[3]:
   _[1,1]=1

The remainder is x3+x2+x and this will be the result in
your ring defined at the beginning.

Code:

> setring r;
> basering;
//   characteristic : 2
//   1 parameter    : a 
//   minpoly        : (a5+a3+1)
//   number of vars : 1
//        block   1 : ordering dp
//                  : names    x
//        block   2 : ordering C

> a^23;
(a3+a2+a)

Well done !

But what you can do, that is that you use for exponentiation.
the following proc Exp
(An extended and improved version of proc exp from realrad.)

// Your example again

Code:

> setring r;
> Exp(a,12345678987654321);
(a4+a3+a2+a+1)

Here is the code:

Code:

proc Exp(def b, bigint N)
"USAGE: Exp(b,N); a number / bigint /int ; N int / bigint
 RETURN: number resp. bigint b^N,
NOTE: the return type is 
       number, if b is of type number but not a transcendantal parameter 
       bigint, if b is of type bigint
       int,    if b is of type int, and b^N is less or eqaual to MAXINT = 2^31-1,
               resp. bigint otherwise
"
{
   
   string b_type = typeof(b);
   if (b_type != "int" and b_type != "bigint" and b_type != "number")
   {
    ERROR("// -- proc Exp: basis must be of type int, bigint or number");
   }
   if (N < 0) 
   {
    ERROR("// -- proc Exp: only non-negative exponent allowed");
   }
   if (b_type=="number")
   {   
    number Res = 1;
    number B = b;
   }
   
   if (b_type=="int" or b_type=="bigint" )
   {
    bigint Res = 1;
    bigint B = b;
   }

   while (N > 0)
   {
      if (N mod 2 == 1)
      {
        Res = Res * B;
        N = N-1;
       Res;
       }
      B = B * B;
      N = N div 2;
   }
  
   if (b_type=="int" and Res<=2147483647)   // MAXINT,  
   {
      return(int(Res));             // convert result to int
   }
   else
   {
     return(Res);
   }
}

Checks

Code:

> Exp(2,80);
1208925819614629174706176
> typeof(_);
bigint
> Exp(2,8);
256
> typeof(_);
int

> ring r=0,x,dp;
> number q = 2;
> Exp(q,8);
> typeof(_);
number
> Exp(q,80);
1208925819614629174706176
> typeof(_);
number

Author:	gepo [ Fri Apr 09, 2010 12:30 am ]
Post subject:	large exponent of minpoly? (use bigint?)
This is what i want to compute: ring r=(2,a),x,dp; minpoly=a^5+a^3+1; //here is a min polynomial definition a^12345678987654321; can I make such a computation? since the exponent is so large, I tried to use bigint: bigint(a)^12345678987654321; but failed. Any ideas? Thanks Gepo

Singular https://www.singular.uni-kl.de/forum/

large exponent of minpoly? (use bigint?) https://www.singular.uni-kl.de/forum/viewtopic.php?f=10&t=1824	Page 1 of 1

Page 1 of 1	All times are UTC + 1 hour [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/