next up previous
Next: Signature of a derivative Up: Open problems with signatures Previous: Signature of

Signature of $\Gamma (k)$

The signature of $\Gamma (k)$ or at least the signature of k!are very expensive, O(k) operations, to compute. This is not good, as for an unknown x, $\Gamma(x)$ would require the computation of Sn(x)! which is O(n). This question in itself is very interesting. Is it possible to compute $k! \bmod n$ in time less than O(k)? This question is open, and very doubtful. If it would be possible, we could do integer factorization in the same time. Non-trivial factors of n can be computed from by $\gcd ( k! \bmod n, n )$. Is it possible to fake the signature of $\Gamma (k)$? The only relations between $\Gamma(n)$ and $\Gamma(m)$ are when n-m is an integer and the expression is of size O(|n-m|). Additional care has to be taken with the half argument relations,

\begin{displaymath}\Gamma(2n) = \frac{\Gamma(n) \Gamma(n+1/2)}{2 \sqrt{\pi}} \end{displaymath}

its extensions and with the reflection formula.

\begin{displaymath}\Gamma(z) \Gamma(1-z) = \frac{\pi}{\sin ( \pi z)} \end{displaymath}


next up previous
Next: Signature of a derivative Up: Open problems with signatures Previous: Signature of
Gaston Gonnet
1999-07-04