// ----------------------------------------------------------------------
// 
//  Module:          smooth.cc
//  Description:     generate smooth modular squares.
//  Contributed by:  Rene Peralta
//  Date:            Dec. 2002
//  
// ----------------------------------------------------------------------
#include <lnv3/lnv3.h>
#include "small_primes.h"
#include <nttl/sqrt.h>

#define B 7
#define max_factors 100
#define B_SIZE 4

int test_smoothness( void );
ln   getN( void );

ln modulus;
ln X;
ln Y;

int main()
{
    using ::modulus;
    int num_smooths = 0;
    
    modulus = getN( );
    X = Sqrt(modulus);
    while (num_smooths < B_SIZE + 6) 
    {
	   X++;
           if (test_smoothness()) num_smooths++;
    }
}

int 
test_smoothness( )
{
    using ::modulus;
    int primefactor[100];

    int index = 1;
    int fn; 
    
    Y = X*X % modulus;
    for(int i = 0; i < max_factors; i++) primefactor[i] = 0;
    fn = 0;
    while (Y > 1) 
    {
      while ((Y % Prime[index]) == 0)
      { 
        primefactor[fn] = Prime[index];
        fn++;
	Y = Y/Prime[index];
      }
      
      index++;
      if (Prime[index] > B) break;
    }

    if (Y == 1) 
    {
      fn = 0;
      while (primefactor[fn] > 0) 
      {
        cout << primefactor[fn] << " ";
	fn++;
      }
      
      cout << " = " << X << " squared mod " << modulus << endl;
      return(1);
    }
    return(0);

}


ln
getN( void )
{
    ln n;
        
    cout << "input a positive integer (0 to exit)" << endl;
    cin >> n ;
    cout << endl << endl;
 
    if (n == 0) 
    {
        cout << "bye " << endl;
        exit( 0 );
    }
        
    if( n.IsNegative( ) )
    { 
        cout << -1 << endl;
        n = -n;
    }

    return n;
}