Re: arithmetic over finite fields

[Gerhard Niklasch <nikl@mathematik.tu-muenchen.de>]

In response to:
> Message-Id: <200004061647.LAA16974@orion.math.iastate.edu>
> Date: Thu, 6 Apr 2000 11:47:27 -0500
> From: Cliff Bergman <cbergman@iastate.edu>

> 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.

Your definition is fine (although it internally calls a function rather
more like powermod() !).

> 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]

Right;  or create the polynomial with integer coefficients first and
then multiply by Mod(1,p).

> This isn't so bad, except that the output format for a is in terms of the
> variable x.

So it is... but x _is_ the true variable here, and the coefficients
are elements of Z/pZ, and shown as such.  Apply lift() for readability,
and don't forget to `tensor' again with Mod(1,p) to get back into the
field when you have to.

> 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?

You could define your own myprint(), myprint1() functions.

Direct output  (arising as values of expressions entered at the gp
prompt)  will always reflect the internal structure though.

> 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.

Start with ec=ellinit([0,0,0,a,a]) for example...  and you'll have
elladd/ellsub(ec,P,Q), ellpow(ec,P,n), ellisoncurve(ec,P) etc at your
fingertips.

The addition formula will work over any field, so you should have no
problems adding points on the curve, or multiplying them by integers.

It won't be terribly efficient over non-prime finite fields, but class-
room scale examples should be quite doable.

Enjoy, Gerhard