Re: Derivation in finite fields

[Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>]

On Sat, Jul 05, 2008 at 12:23:03PM +0200, Benedikt Berghammer wrote:
> Hi all,
> 
> I'm new in working with PARI and have the following problem. I'm working 
> on a script for computing the Weil-Pairing over finite fields after 
> Miller's algorithm.
> 
> In one step I need to get the line tangent to an Elliptic Curve E at a 
> point P. For computing the gradient of this tangent I need to compute 
> the derivation of the square root.
> 
> For example I have the Elliptic Curve E=x^3-48*x+1 in the field p=1009.
> When trying
> Mod(deriv(sqrt(x^3-48*x+1)),1009) I get the following error in PARI: 
> Mod: incorrect type in Rg_to_Fl.

The error is normal: Mod(a,p) only work if a is an integer.
What you want to do is to define your polynomial over F_1009
by doing (x^3-48*x+1)*Mod(1,1009), and then take the squareroot
and derive:

? deriv(sqrt((x^3-48*x+1)*Mod(1,1009)))
%1 = Mod(985, 1009) + Mod(433, 1009)*x + Mod(959, 1009)*x^2 + Mod(6, 1009)*x^3 + Mod(396, 1009)*x^4 + Mod(181, 1009)*x^5 + Mod(645, 1009)*x^6 + Mod(450, 1009)*x^7 + Mod(691, 1009)*x^8 + Mod(1005, 1009)*x^9 + Mod(688, 1009)*x^10 + Mod(142, 1009)*x^11 + Mod(885, 1009)*x^12 + Mod(400, 1009)*x^13 + Mod(192, 1009)*x^14 + O(x^15)

(You were using a maple-ish syntax).

Cheers,
Bill.