//*****************************************************************************/
//                                                                            */
//  Software zum Buch "Kryptographie in C und C++"                            */
//  Autor: Michael Welschenbach                                               */
//                                                                            */
//  Quelldatei testroot.cpp Stand: 30.05.2001                                 */
//                                                                            */
//  Copyright (C) 1998-2001 by Michael Welschenbach                           */
//  Copyright (C) 2001 by Springer-Verlag Berlin, Heidelberg                  */
//                                                                            */
//  All Rights Reserved                                                       */
//                                                                            */
//  Die Software darf fuer nichtkommerzielle Zwecke frei verwendet und        */
//  veraendert werden, solange die folgenden Bedingungen anerkannt werden:    */
//                                                                            */
//  (1) Alle Aenderungen muessen als solche kenntlich gemacht werden, so dass */
//      nicht der Eindruck erweckt wird, es handle sich um die Original-      */
//      Software.                                                             */
//                                                                            */
//  (2) Die Copyright-Hinweise und die uebrigen Angaben in diesem Feld        */
//      duerfen weder entfernt noch veraendert werden.                        */
//                                                                            */
//  (3) Weder der Verlag noch der Autor uebernehmen irgendeine Haftung fuer   */
//      eventuelle Schaeden, die aus der Verwendung oder aus der Nicht-       */
//      verwendbarkeit der Software, gleich fuer welchen Zweck, entstehen     */
//      sollten, selbst dann nicht, wenn diese Schaeden durch Fehler verur-   */
//      sacht wurden, die in der Software enthalten sein sollten.             */
//                                                                            */
//*****************************************************************************/

#include <stdlib.h>
#include "flintpp.h"

#define PRIMERESTMOD4 3

#define MAXTESTLEN 64
#define CLINTRNDLN (1 + ulrand64_l() % MAXTESTLEN)


static int simple_tests (int);
static int general_tests (int);
static int general_large_tests (int);
static int test_iroot (int);

int main ()
{
  cout << "Testmodul " << __FILE__
       << " compiliert fuer FLINT/C-Library Version "
       << verstr_l () << endl;

  initrand64_lt ();
  initrandBBS_lt ();
  simple_tests (1000);
  general_tests (50);
  general_large_tests (5);
  test_iroot (1000);

  cout << "Alle Tests in " << __FILE__ << " fehlerfrei durchlaufen." << endl;
  return 0;
}


static int simple_tests (int no_of_tests)
{
  LINT a, p, q, r;
  int jp, jq;

  cout << "Testfunktion simple_tests() mit Konstanten ..." << endl;

  if (jacobi (0, 3) != 0)
    {
      cerr << "Fehler: jacobi(0, 3) != 0" << endl;
      exit (-1);
    }
  if (jacobi (3, 0) != 0)
    {
      cerr << "Fehler: jacobi(3, 0) != 0" << endl;
      exit (-1);
    }
  if (jacobi (8, 2) != 0)
    {
      cerr << "Fehler: jacobi(8, 2) != 0" << endl;
      exit (-1);
    }

  a = randl (CLINTRNDLN);
  r = root (a, 0);
  if (r.Get_Warning_Status() != E_LINT_ERR)
    {
      cerr << "Fehler: root (a, 0) != -1" << endl;
      exit (-1);
    }

  r = root (a, 2);
  if (r.Get_Warning_Status() != E_LINT_ERR)
    {
      cerr << "Fehler: root (a, 2) != -1" << endl;
      exit (-1);
    }

  r = a.root (0);
  if (r.Get_Warning_Status() != E_LINT_ERR)
    {
      cerr << "Fehler: a.root (0) != -1" << endl;
      exit (-1);
    }

  r = a.root (2);
  if (r.Get_Warning_Status() != E_LINT_ERR)
    {
      cerr << "Fehler: a.root (2) != -1" << endl;
      exit (-1);
    }

  cout << "Testfunktion simple_tests() mit kleinen Parametern ..." << endl;

  for (int i = 0; i < no_of_tests; i++)
    {
      p = findprime (MAXTESTLEN/2);
      do
        {
          q = findprime (MAXTESTLEN/2);
        }
      while (q % 4 == p % 4);

      // cout << "p = " << p << endl;
      // cout << "p mod 4 = " << p % 4 << endl;

      // cout << "q = " << q << endl;
      // cout << "q mod 4 = " << q % 4 << endl;

      do
        {
          a = randl (CLINTRNDLN);
          jp = a.jacobi (p);
          r = mexp (a, ( p - 1 ) / 2, p);
          if (jp < 0) r += -jp;
          if (jp > 0) r -= jp;
          if (r % p > 0)
            {
              cerr << "Fehler: a^(p-1)/2 = " << r << " != (a/p) mod p" << endl;
              exit (-1);
            }

          jq = a.jacobi (q);
          r = mexp (a, ( q - 1 ) / 2, q);
          if (jq < 0) r += -jq;
          if (jq > 0) r -= jq;
          if (r % q > 0)
            {
              cerr << "Fehler: a^(q-1)/2 = " << r << " != (a/q) mod q" << endl;
              exit (-1);
            }
        } while (( a > p * q ) || (( a.jacobi (p) < 1 ) || ( a.jacobi (q) < 1 )));

      // cout << "a = " << a << endl;
      // cout << "jacobi(a,p) = " << jacobi(a,p) << ", ";
      // cout << "jacobi(a,q) = " << jacobi(a,q) << endl;

      if (( r = root (a, p, q)) == 0U)
        {
          cerr << "Fehler bei jacobi: root = NULL " << endl;
          cerr << "a ist kein quadratischer Rest mod pq." << endl;
          cerr << "a = " << a << endl;
          cerr << "jacobi(a,p) = " << jacobi (a, p) << ", ";
          cerr << "jacobi(a,q) = " << jacobi (a, q) << endl;
          exit (-1);
        }

      // cout << "Wurzel von a mod pq = " << r << endl;
      if (a == ( r * r ) % ( p * q ))
        {
          // cout << "a ist quadratischer Rest mod pq." << endl;
        }
      else
        {
          cerr << "Fehler: a ist kein quadratischer Rest mod pq." << endl;
          cerr << "a = " << a << endl;
          cerr << "jacobi(a,p) = " << jacobi (a, p) << ", ";
          cerr << "jacobi(a,q) = " << jacobi (a, q) << endl;
          cerr << "r = " << r << endl;
          exit (-1);
        }
    }

  return 0;
}


#undef  MAXTESTLEN
#define MAXTESTLEN (CLINTMAXBIT >> 2)

static int general_tests (int no_of_tests)
{
  LINT a, p, q, r;
  int jp, jq;

  cout << "Testfunktion general_tests() ..." << endl;

  for (int i = 0; i < no_of_tests; i++)
    {
      p = findprime (MAXTESTLEN/2);
      do
        {
          q = findprime (MAXTESTLEN/2);
        } while (p % 4 == q % 4);

      // cout << "p = " << p << endl;
      // cout << "p mod 4 = " << p % 4 << endl;

      // cout << "q = " << q << endl;
      // cout << "q mod 4 = " << q % 4 << endl;

      do
        {
          a = randl (CLINTRNDLN);
          jp = a.jacobi (p);
          r = mexp (a, ( p - 1 ) / 2, p);
          if (jp < 0) r += -jp;
          if (jp > 0) r -= jp;
          if (r % p > 0)
            {
              cerr << "Fehler: a^(p-1)/2 = " << r << " != (a/p) mod p" << endl;
              exit (-1);
            }

          jq = a.jacobi (q);
          r = mexp (a, ( q - 1 ) / 2, q);
          if (jq < 0) r += -jq;
          if (jq > 0) r -= jq;
          if (r % q > 0)
            {
              cerr << "Fehler: a^(q-1)/2 = " << r << " != (a/q) mod q" << endl;
              exit (-1);
            }
        } while (( a > p * q ) || ( a.jacobi (p) < 1 ) || ( a.jacobi (q) < 1 ));

      // cout << "a = " << a << endl;
      // cout << "jacobi(a,p) = " << jacobi(a,p) << ", ";
      // cout << "jacobi(a,q) = " << jacobi(a,q) << endl;

      if (( r = a.root (p, q)) == 0U)
        {
          cerr << "Fehler bei jacobi: root = NULL " << endl;
          cerr << "a ist kein quadratischer Rest mod pq." << endl;
          cerr << "a = " << a << endl;
          cerr << "jacobi(a,p) = " << jacobi (a, p) << ", ";
          cerr << "jacobi(a,q) = " << jacobi (a, q) << endl;
          exit (-1);
        }

      // cout << "Wurzel von a mod pq = " << r << endl;
      if (a == ( r * r ) % ( p * q ))
        {
        // cout << "a ist quadratischer Rest mod pq." << endl;
        }
      else
        {
          cerr << "Fehler: a ist kein quadratischer Rest mod pq." << endl;
          cerr << "a = " << a << endl;
          cerr << "jacobi(a,p) = " << jacobi (a, p) << ", ";
          cerr << "jacobi(a,q) = " << jacobi (a, q) << endl;
          cerr << "r = " << r << endl;
          exit (-1);
        }
    }

  return 0;
}


#undef  MAXTESTLEN
#define MAXTESTLEN (CLINTMAXBIT >> 1)

static int general_large_tests (int no_of_tests)
{
  LINT a, p, q, r;
  int jp, jq;

  cout << "Testfunktion general_large_tests() ..." << endl;

  for (int i = 0; i < no_of_tests; i++)
    {
      p = findprime (MAXTESTLEN/2);
      do
        {
          q = findprime (MAXTESTLEN/2);
        } while (p % 4 == q % 4);

      // cout << "p = " << p << endl;
      // cout << "p mod 4 = " << p % 4 << endl;

      // cout << "q = " << q << endl;
      // cout << "q mod 4 = " << q % 4 << endl;

      do
        {
          a = randl (CLINTRNDLN);
          jp = a.jacobi (p);
          r = mexp (a, ( p - 1 ) / 2, p);
          if (jp < 0) r += -jp;
          if (jp > 0) r -= jp;
          if (r % p > 0)
            {
              cerr << "Fehler: a^(p-1)/2 = " << r << " != (a/p) mod p" << endl;
              exit (-1);
            }

          jq = a.jacobi (q);
          r = mexp (a, ( q - 1 ) / 2, q);
          if (jq < 0) r += -jq;
          if (jq > 0) r -= jq;
          if (r % q > 0)
            {
              cerr << "Fehler: a^(q-1)/2 = " << r << " != (a/q) mod q" << endl;
              exit (-1);
            }
        } while (( a > p * q ) || ( a.jacobi (p) < 1 ) || ( a.jacobi (q) < 1 ));

      // cout << "a = " << a << endl;
      // cout << "jacobi(a,p) = " << jacobi(a,p) << ", ";
      // cout << "jacobi(a,q) = " << jacobi(a,q) << endl;

      if (( r = a.root (p, q)) == 0U)
        {
          cerr << "Fehler bei jacobi: root = NULL " << endl;
          cerr << "a ist kein quadratischer Rest mod pq." << endl;
          cerr << "a = " << a << endl;
          cerr << "jacobi(a,p) = " << jacobi (a, p) << ", ";
          cerr << "jacobi(a,q) = " << jacobi (a, q) << endl;
          exit (-1);
        }

      // cout << "Wurzel von a mod pq = " << r << endl;
      if (a == r.msqr (p * q))
        {
        // cout << "a ist quadratischer Rest mod pq." << endl;
        }
      else
        {
          cerr << "Fehler: a ist kein quadratischer Rest mod pq." << endl;
          cerr << "a = " << a << endl;
          cerr << "jacobi(a,p) = " << jacobi (a, p) << ", ";
          cerr << "jacobi(a,q) = " << jacobi (a, q) << endl;
          cerr << "r = " << r << endl;
          exit (-1);
        }
    }

  return 0;
}


#undef  MAXTESTLEN
#define MAXTESTLEN CLINTMAXBIT

static int test_iroot (int nooftests)
{
  LINT n, r, q;
  int i;

  cout << "Test der Funktionen issqr() zur Erkennung von Quadraten" << endl;
  cout << "und root() zur Berechnung ganzzahliger Quadratwurzeln..." << endl;

  n = LINT(0);
  q = n * n;
  r = q.issqr();

  if (r != n)
    {
      cerr << "Fehler: Wurzel falsch in Test " << 0 << " bei Zeile " << __LINE__ << endl;
      cerr << "n = " << n << endl << "r = " << r << endl;
      exit (-1);
    }

  if (q.root() != n)
    {
      cerr << "Fehler: Wurzel falsch in Test " << 0 << " bei Zeile " << __LINE__ << endl;
      cerr << "n = " << n << endl << "r = " << r << endl;
      exit (-1);
    }

  for (i = 1; i <= nooftests; i++)
    {
      n = randl (CLINTRNDLN/2);
      q = n * n;
      r = q.issqr();

      if ((n > 0) && (0 == r))
        {
          cerr << "Fehler: Quadrat nicht erkannt in Test " << i << " bei Zeile " << __LINE__ << endl;
          cerr << "n = " << n << endl << "r = " << r << endl;
          exit (-1);
        }

      if (r != n)
        {
          cerr << "Fehler: Wurzel falsch in Test " << i << " bei Zeile " << __LINE__ << endl;
          cerr << "n = " << n << endl << "r = " << r << endl;
          exit (-1);
        }

      if (q.root() != n)
        {
          cerr << "Fehler: Wurzel falsch in Test " << i << " bei Zeile " << __LINE__ << endl;
          cerr << "n = " << n << endl << "r = " << r << endl;
          exit (-1);
        }
    }


  n = LINT(0);
  q = n * n;
  r = issqr(q);

  if (r != n)
    {
      cerr << "Fehler: Wurzel falsch in Test " << 0 << " bei Zeile " << __LINE__ << endl;
      cerr << "n = " << n << endl << "r = " << r << endl;
      exit (-1);
    }

  if (root(q) != n)
    {
      cerr << "Fehler: Wurzel falsch in Test " << 0 << " bei Zeile " << __LINE__ << endl;
      cerr << "n = " << n << endl << "r = " << r << endl;
      exit (-1);
    }

  for (i = 1; i <= nooftests; i++)
    {
      n = randl (CLINTRNDLN/2);
      q = n * n;
      r = issqr(q);

      if ((n > 0) && (0 == r))
        {
          cerr << "Fehler: Quadrat nicht erkannt in Test " << i << " bei Zeile " << __LINE__ << endl;
          cerr << "n = " << n << endl << "r = " << r << endl;
          exit (-1);
        }

      if (r != n)
        {
          cerr << "Fehler: Wurzel falsch in Test " << i << " bei Zeile " << __LINE__ << endl;
          cerr << "n = " << n << endl << "r = " << r << endl;
          exit (-1);
        }

      if (root(q) != n)
        {
          cerr << "Fehler: Wurzel falsch in Test " << i << " bei Zeile " << __LINE__ << endl;
          cerr << "n = " << n << endl << "r = " << r << endl;
          exit (-1);
        }
    }

  return 0;
}



