Cliff Bergman on Thu, 6 Apr 2000 11:47:27 -0500


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

arithmetic over finite fields


Hello.
I am teaching a course in cryptography, and have the students using
pari to do some of the computations.  So far it has been working well,
since we have been working mostly over Z_n.  However, we are now on to
finite fields, and I could use a few pointers about how best to use
pari/gp in this context.  A couple of questions:

1. (Well, this question is really about Z_n) In cryptography, one
frequently has to compute a^k%n where a, k, n are large integers.  I have
been using the definition
  powermod(a,k,n)=lift(Mod(a,n)^k)
This has worked nicely, but I wonder if there is a built-in function that
would do the same thing.

2. I assume the only way to represent an element of a finite field is as a
polmod.  Correct?  This means the coefficients have to be integermods. 
This is kind of a hassle to type all of the time.  My approach has been to
make the inderminate a "variablemod".  Thus I define:
  y=Mod(1,p)*x   [where p is a predefined prime]
  a=y^3+3*y^2+2  [to define a particular polynomial a over Z_p, for example]
This isn't so bad, except that the output format for a is in terms of the
variable x.
Then the elements of a finite field are of the form Mod(a,b), where a and
b are defined as above. Now the output format gets pretty hard to read,
since it has nested 'Mods'.  One can get a more manageable output by
asking for lift(lift(%)).  

Is there any way to get this output automatically?  Is there a better way to do the 
whole  thing that I am missing?

3. I haven't quite gotten to elliptic curves (over a finite field) yet. 
 I suppose questions similar to #2 will apply to those. I do realize that
there are lots of built-in commands for elliptic curves.  I suppose the
only complication will be in representing the components as elements of
the finite field.

Thanks for any advice that anybody has to offer.

cliff b.