// ----------------------------------------------------------------------
//  
//  Module:          ss_gen.cc
//  Description:     Generates instances of combinatorial problem
//                   related to factorization using a Quadratic
//                   Residuosity Oracle.
//  Contributed by:  Rene Peralta
//  Date:            1999
//  
// ----------------------------------------------------------------------

#include "small_primes.h"

#include <lnv3/lnv3.h>
#include <lnv3/nttlTraits.h>
#include <stdio.h>

 
#include <nttl/isPrime.h> 
#include <nttl/gcd.h> 
#include <nttl/inverse.h> 
//#include <nttl/jacobi.h> 

#define SECRET 101
// this is the index of the first prime in the prime base.
#define OFFSET 6
#define PRIME_BASE_SIZE 10


ln mu(ln a, ln q, ln R);


int
main( int argc, char *argv[ ] )
{
    long  T[PRIME_BASE_SIZE];
    ln R = 1; 
    ln t;
    ln accum1 = 1;
    ln accum2 = 0;

    for( long i=0 ; i<PRIME_BASE_SIZE ; i++ ) 
    {
        R = R*Prime[i+OFFSET];
        //accum1 = accum1*(Prime[i+OFFSET]-1)/2;
    }

    //cout << "SECRET IS " << SECRET << endl;
    //cout << "expected value of minimum sum is ";
    //cout << R / accum1 << endl << endl;

    for (long i = 0; i < PRIME_BASE_SIZE; i++)
    {
        ln q = Prime[i+OFFSET];
        //cout << q << " list" << endl << endl;
        for (ln a = 1; a < q; a++) 
        {
            if( a.Jacobi(q) != q.Jacobi(SECRET) )
                continue;

            t = mu(a,q,R);
            cout << t ;
            //if (a ==  ((ln) SECRET)%q) cout << "  *" ;
            if (a ==  ((ln) SECRET)%q) 
                accum2 += t ;
            cout << endl;
        }
        cout << endl << endl << endl;
    }
    
    //cout << R << " list" << endl << endl;
    // note this is very pessimistic, this loop should
    // really cover a few multiples of R around 
    // -R*PRIME_BASE_SIZE/2
    for( long i=0 ; i<PRIME_BASE_SIZE ; i++ )
        cout << -(i+1)*R << endl;
    
    cout << endl << endl;
    //cout << "should be close to "  << accum2 << endl;

    return 0;
}

ln mu(ln a, ln q, ln R)
{
  ln t = R/q;
  return( (a*t*Inverse(t,q)) % R);
}