arvind@utcsri.UUCP (09/08/87)
Date: Wed, 2 Sep 87 20:32:09 PDT
From: pmontgom@rdcf.sm.unisys.com (Peter Montgomery)
Subject: Truncated hypergeometric summations modulo a prime
Fix alpha, beta, gamma (gamma <> 0, -1, -2, ...).
The hypergeometric function has the power series
infinity j
F(x) = F(alpha, beta; gamma; x) = sum a[j] x
j = 0
where
a[j+1] (j + alpha) (j + beta)
a[0] = 1 ------ = ---------------------- .
a[j] (j + gamma) (j + 1)
It satisfies the differential equation
(x^2 - x)F''(x) + [(alpha+beta+1)x - gamma]F'(x) + (alpha*beta)F(x) = 0.
What are the values of such summations when computed modulo a
prime p = 2h+1 and truncated where the terms first vanish mod p? The
problem arose when trying to find a fast algorithm for computing the order
of an elliptic curve. Following Joseph H. Silverman, on p. 141 of his "The
arithmetic of elliptic curves", Springer-Verlag, I can show that the
elliptic curve
y^2 == x(x + a)(x + b) mod p
(a,b distinct and nonzero) has order congruent to 1 - H (a, b) mod p, where
p
2 2
h (h) j h-j h (2j) j h-j
H (a,b) = sum ( ) a b == sum ( ) (a/16) b mod p
p j=0 (j) j=0 ( j)
This summation matches the series for b^h F(1/2, 1/2; 1; a/b) (complete
elliptic integral) mod p, except that the summation is truncated after h+1
terms (the terms for h < j <= 2h are all zero modulo p).
6 5 4 2 3 3 2 4 5 6
Example: H (a, b) == a - 3a b + 4a b - 3a b + 4a b - 3ab + b
13
2 2 2 2 2 2
== 11(2a +ab+2b )(3a -ab+b )(a -ab+3b ) mod 13.
I have shown that Hp satisfies the following:
. Hp(a, b) == Hp(a-b, -b) == Hp(-a, b-a)
== Hp(b, a) == Hp(-b, a-b) == Hp(b-a, -a) .
2 2 2 2
. Hp(a , b ) == Hp(4ab, (a+b) ) == Hp(ab, (a+b) /4).
. As formal power series, Hp (x,1) == F(1/2, 1/2; 1; x)^(1-p).
This formula is not directly useful for computation,
because F has infinitely many nonzero terms, but might be
useful if we can get an analytic expression for F(x) mod p.
. The polynomial has no repeated roots.
2 2
. Hp(a, b) is divisible by a - ab + b if p == 5 mod 6.
. Hp(a, b) is divisible by (a+b)(2a-b)(a-2b) if p == 3 mod 4.
. If p <= 31, then Hp splits into linear and quadratic
factors over GF(p).
. For fixed a and b, Hp(a, b), when properly adjusted mod p,
is congruent to (p+1) mod 4 and has absolute value less
than 2*sqrt(p).
Other parameterizations of elliptic curves lead to different
truncated hypergeometric summations. For example, the Weierstrass equation
2 3
y = x + ax + b mod p, p == 1 mod 6
3 2
leads to the summation for F(1/12, 7/12; 2/3; -4a /27b ), truncated after
[(p-1)/12] + 1 terms (so the next term is zero). I could also use
F(alpha, beta; alpha+beta; x) for (alpha, beta) =
(1/4, 3/4), (1/12, 5/12), (1/6, 5/6), or (1/6, 1/2).
Peter Montgomery
Unisys
2525 Colorado Avenue
Santa Monica, CA 90406 USA
pmontgom@sdcrdcf.UUCP