# C++: Library to interpolate polynomial and find a polynomial roots

I need to know what library, compatible with C++, can be used to interpolate a polynomial. So given \$n\$ point-value pairs it can recover the polynomial. The library must support big integer (multi-precision) values as my polynomial is defined over a polynomial ring R[x] where R is a 1024 bit number.

Note: I have used NTL but it apparently does not support big integer.

I found the NTL interpolate useful, so below is NTL interpolate with minor modifications. Now it works with GMP mpz_t type big integer. It has been tested many times and works fine (as far as I observed).

Remark: N is moduli. The function below allows use to interpolate a polynomial \$f\$, given \$(a,b)\$ pairs (i.e. \$(a_0,b_0),...,(a_n,b_n)\$ ), where \$f(a_i)=b_i\$. The function returns coefficients of the polynomial \$f\$. Here, size is \$n\$.

``````#include<gmp.h>
#include <gmpxx.h>
typedef mpz_t bigint;

bigint* interpolate(int size, bigint* a, bigint* b,bigint N)
{
long m = size;
bigint* prod;
prod=(mpz_t*)malloc(size*sizeof(mpz_t));
prod = a;
bigint t1, t2;
mpz_init(t1);
mpz_init(t2);
int k, i;

bigint* res;
res=(mpz_t*)malloc(size*sizeof(mpz_t));
bigint aa;
for (k = 0; k < m; k++) {

mpz_init_set(aa ,a[k]);
mpz_init_set_str(t1,"1",10);
for (i = k-1; i >= 0; i--) {
mpz_mul(t1, t1, aa);
mpz_mod(t1, t1,N);
}

mpz_init_set_str(t2,"0",10);
for (i = k-1; i >= 0; i--) {
mpz_mul(t2, t2, aa);
mpz_mod(t2, t2,N);
}

mpz_invert(t1, t1,N);
mpz_sub(t2, b[k], t2);
mpz_mul(t1, t1, t2);

for (i = 0; i < k; i++) {
mpz_mul(t2, prod[i], t1);
mpz_mod(t2, t2,N);

mpz_mod(res[i], res[i],N);

}

mpz_init_set(res[k], t1);
mpz_mod(res[k], res[k],N);
if (k < m-1) {
if (k == 0)
mpz_neg(prod[0], prod[0]);
else {
mpz_neg(t1, a[k]);
for (i = k-1; i >= 1; i--) {
mpz_mul(t2, prod[i], t1);
mpz_mod(t2, t2,N);

}
mpz_mul(prod[0], prod[0], t1);
mpz_mod(prod[0], prod[0],N);

}
}
}

while (m > 0 && (res[m-1]==0)) m--;
return res;
}
``````

alglib.net seems to provide a c++ multiple precision library thats free, and seems to do what you require, you need to pay for multithreaded support though.

• Can I ask, if you have used it? It does not seem to be very promising.
– user13676
Commented Jun 8, 2015 at 21:22
• nope, I havent but it seems like its been ported to multiple languages and is well developed in terms of features nad documentation. whats not promising about it?
– MSEoris
Commented Jun 8, 2015 at 22:59
• I think it does not support polynomial ring.
– user13676
Commented Jun 9, 2015 at 19:19