486 ARITHMETIC 4.6.4 For example, suppose that we (Web design)
486 ARITHMETIC 4.6.4 For example, suppose that we want to estimate $! from the values of O!, l!, 2!, and 3!, using a cubic polynomial. The divided differences are X Y Y Y Y f 0 1 1 1 0 1 2 2 3 6 so dOI(x) = uqx) = 1, &l(x) = 4x(x -1) + 1, [31(X) = &x(x -1)(x -2) + ax(a:-l)+l. Setting x = 4 in the latter polynomial gives -& + 3 + 1 = 1.25; presumably the correct value is I($ + 1) = $fi z 1.33. An important and somewhat surprising application of polynomial interpola- tion was discovered by Adi Shamir [CACM 22 (1979), 612-6131, who observed that polynomials mod p can be used to share a secret. This means that we can design a system of secret keys or passwords such that the knowledge of any n + 1 of the keys enables efficient calculation of a magic number N that un- locks a door (say), but the knowledge of any n of the keys gives no information whatsoever about N. Shamir s amazingly simple solution to this problem is to choose a random polynomial U(X) = u,xn +. . . + uix + uc, where 0 5 ui < p and p is a large prime number. Each part of the secret is an integer z in the range 0 < x < p, together with the value of u(x)modp; and the supersecret number N is the constant term uc. Given n + 1 values u(xi), we can deduce N by interpolation. But if only n values of u(x~) are given, there is a unique polynomial U(X) having a given constant term but the same values at xl, . . . , x,; thus the n values do not make one particular N more likely than any other. It is instructive to note that evaluation of the interpolation polynomial is just a special case of the Chinese remainder algorithm of Section 4.3.2 and exercise 4.6.2-3, since we know the values of u[ l(x) modulo the relatively prime polynomialsa:-xc, . . . . x-xz,. (As we have seen in Section 4.6.2, f(x) mod (x-xc) = 1(x0).) Under th is interpretation, Newton s formula (42) is precisely the mixed-radix representation of Eq. 4.3.2-24; and 4.3.2-23 yields another way to compute ~0, . . . , cy, using the same number of operations as (44). By applying fast Fourier transforms, it is possible to reduce the running time for interpolation to O(n (logn)2), and a similar reduction can also be made for related algorithms such as the solution to the Chinese remainder problem and the evaluation of an nth degree polynomial at n different points. [See E. Horowitz, Inf. Proc. Letters 1 (1972), 157-163; R. Moenck and A. Borodin, J. Comp. Syst. Sci. 8 (1974), 336-385; and A. Borodin, Complexity of Sequential and Parallel Numerical Algorithms, ed. by J. F. Traub (New York: Academic Press, 1973), 149-180.1 However, this must be regarded as a purely theoretical possibility at present, since the known algorithms have a rather large overhead factor that makes them unattractive unless n is quite large.