#include <lnv3/lnv3.h>
#include <nttl/isPrime.h> 
#include <nttl/gcd.h> 
#include "small_primes.h"

ln fast_exp(ln a, ln b, ln n);

int
main( int argc, char *argv[ ] )
{
    ln n = 1;
    ln p ;

    for (long i = 0; i < 15; i++) n = n * Prime[i];
    while(1)
      if (IsPrime(n + 1)) 
      {
        p = n + 1;
	break;
      }
      else n = 2*n;
   

   // now find a generator
   ln q = (p - 1)/2;
   ln g = 2;
   cout << p << endl;
   cout << q << endl;
   while (fast_exp(g,q,p) == 1) g++;
   cout << g << endl;
   cout << fast_exp(g,q,p) << endl;

   ln x = ln( ).Random(30) % p;
   cout << "the following is a discrete log problem" << endl;
   cout << "p : " << p << endl;
   cout << "g : " << g << endl;
   cout << "x : " << x << endl;
   cout << "g^x % p : " << fast_exp(g,x,p) << endl;
}


ln fast_exp(ln a, ln b, ln n)
{
  if ( a.IsZero() ) return (0);
  if ( b.IsZero() ) return(1);
  if ( b == 1 ) return(a%n);
  ln x = a*a % n;
  if (b.IsOdd()) return( a*fast_exp(x,b/2,n) % n );
  return(fast_exp(x,b/2,n));
}