//  ----------------------------------------------------------------------
// 
//  Sample ln3 Program
//  
//  Module:          interp.cc
//  Description:     User supplies, prime P, m, f(1), ... , f(n),
//                   where f is a polynomial of degree m over Zp
//                   For each user-supplied subset S of {1, ..., n},
//                   (|S| > m), program produces f assuming values
//                   of f(i), i in S, are correct.
//  Date:            2001
//  Contributed by:  Rene Peralta
//  
//  ----------------------------------------------------------------------


#include <lnv3/lnv3.h>
#include <nttl/inverse.h> 

#define max_shares 100
ln a[max_shares];
long S[max_shares];
int
main( int argc, char *argv[ ] )
{
    ln p;
    long m,n;

    cout << "enter P, polynomial degree m, number of shares n" << endl;
    if( ! ( cin >> p )  ) return 0;
    if( ! ( cin >> m )  ) return 0;
    if( ! ( cin >> n )  ) return 0;
    
    cout << "now enter f(i)'s" << endl;
    for (long i = 1; i <= n; i++)  
    {
      cout << "f(" << i << ") : " ;
      if( ! ( cin >> a[i] )  ) return 0;
    }

    while (1)
    {
      cout << "now enter S " << endl;
      // enter S
      char c;
      for (long x = 1; x <= n; x++) 
      {
        cout << x << " in S? (answer y or n) " ;
        if( ! ( cin >> c )  ) return 0;
	if ( c == 'y') S[x] = 1; else S[x] = 0;
      }
      
      // interpolate
      ln k = 0;
      ln summand = 0;
      for (long j =1; j <= n ; j++)
      if (S[j])
      {
	ln prod = 1;
	for (long u = 1; u <= n; u++)
	  if (S[u] && (u != j))
	    prod = (prod * (p-u)*Inverse(j + p -u, p)) % p;
        summand = summand + a[j]*prod;
      }
      cout << "f(0) is " << summand % p<< endl;
  }
}