Singular

D.15.14.6 sparseInterpolation

Usage:

sparseInterpolation(Br, La, lpr, n[, m]); Br poly, La list, lpr list, n int, m int

Return:

a polynomial B in the polynomial ring Q[var(n+1),...,var(n+size(lpr))] satisfying the relation La[i] = B(lpr[1]^i,...,lpr[size(lpr)]^i).

Note:

The polynomial Br in Q[var(n)] is the minimal polynomial obtained by applying the SINGULAR command BerlekampMassey to the sequence (La[j]), 1<=j<=size(La). By default the exponent i starts from 1. However, if the optional parameter m>=0 is provided, then it starts from m.
The list lpr must be a list of distinct primes.

LIB "ffmodstd.lib";
ring rr=0,(x,y),dp;
list lpr = 2,3; // assign 2 for x and 3 for y
list La = 150,3204,79272,2245968,70411680, 2352815424, 81496927872;
// La[i] = number(subst(f,y,lpr[1]^i,z,lpr[2]^i)); for f = x2y2+2x2y+5xy2 and i=1,...,7
poly Br = BerlekampMassey(La,1)[1];
Br;
==> x3-66x2+1296x-7776
sparseInterpolation(Br,La,lpr,0); // reconstruct f default
==> x2y2+2x2y+5xy2
La = 97,275,793,2315,6817;
// La[i] = number(subst(g,y,lpr[1]^i,z,lpr[2]^i)); for g = x+y and i=4,...,8
Br = BerlekampMassey(La,1)[1];
Br;
==> x2-5x+6
sparseInterpolation(Br,La,lpr,0,4);
==> x+y