2

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.

2

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_add(t1, t1, prod[i]);
  }

  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_add(t2, t2, res[i]);
  }

  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_add(res[i], res[i], t2);
     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]);
        mpz_add(prod[k], t1, prod[k-1]);
        for (i = k-1; i >= 1; i--) {
           mpz_mul(t2, prod[i], t1);
           mpz_mod(t2, t2,N);

           mpz_add(prod[i], t2, prod[i-1]);
        }
        mpz_mul(prod[0], prod[0], t1);
        mpz_mod(prod[0], prod[0],N);

     }
  }
}

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

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 Jun 8 '15 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 Jun 8 '15 at 22:59
  • I think it does not support polynomial ring. – user13676 Jun 9 '15 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.