[ut.theory] THEORY NET: Truncated hypergeometric ...

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