//*****************************************************************************/
//                                                                            */
//  Software zum Buch "Kryptographie in C und C++"                            */
//  Autor: Michael Welschenbach                                               */
//                                                                            */
//  Quelldatei testxgcd.cpp Stand: 28.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 MAXTESTLEN (CLINTMAXBIT/2)
#define CLINTRNDLN (1 + ulrand64_l() % MAXTESTLEN/2)

static int general_tests (int);

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

  initrand64_lt ();
  initrandBBS_lt ();
  general_tests (10000);

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


static int general_tests (int nooftests)
{
  LINT a, b, u, v, g, gg;
  int i, sign_u, sign_v;

  for (i = 1; i <= nooftests; i++)
    {
      a = randl (CLINTRNDLN/2);
      b = randl (CLINTRNDLN/2);

      g = gcd (a, b);
      gg = xgcd (a, b, u, sign_u, v, sign_v);

      if (g != gg)
        {
          cerr << "Fehler bei Vergleich von Friend-Funktionen" << endl;
          cerr << "gcd und xgcd in Test " << i << " bei Zeile " << __LINE__ << endl;
          exit (-1);
        }

      if (g == 1 && b > 1)
        {
          if ((a * inv (a, b)) % b != 1)
            {
              cerr << "Fehler in Friend-Funktion inv in Test " << i;
              cerr << " bei Zeile " << __LINE__ << endl;
              exit (-1);
            }
        }

      if (a * b != g * lcm (a, b))      // ggT (a, b) * kgV (a, b) = a * b
        {
          cerr << "Fehler in Friend-Funktion lcm" << endl;
          cerr << "in test " << i << " bei Zeile " << __LINE__ << endl;
          exit (-1);
        }


      a *= u;
      b *= v;

      if (sign_u == 1 && sign_v == 1) a += b;
      if (sign_u == -1 && sign_v == 1) a = b - a;
      if (sign_u == 1 && sign_v == -1) a -= b;

      if (a != gg)
        {
          cerr << "Fehler in Friend-Funktion xgcd in Test " << i;
          cerr << " bei Zeile " << __LINE__ << endl;
          exit (-1);
        }
    }

  for (i = 1; i <= nooftests; i++)
    {
      a = randl (CLINTRNDLN/2);
      b = randl (CLINTRNDLN/2);

      g = a.gcd (b);
      gg = a.xgcd (b, u, sign_u, v, sign_v);

      if (g != gg)
        {
          cerr << "Fehler bei Vergleich von Member-Funktionen" << endl;
          cerr << "gcd und xgcd in Test " << i << " bei Zeile " << __LINE__ << endl;
          exit (-1);
        }

      if (g == 1 && b > 1)
        {
          if ((a * a.inv (b)) % b != 1)
            {
              cerr << "Fehler in Member-Funktion inv in Test " << i;
              cerr << " bei Zeile " << __LINE__ << endl;
              exit (-1);
            }
        }

      if (a * b != g * a.lcm (b))      // ggT (a, b) * kgV (a, b) = a * b
        {
          cerr << "Fehler in Member-Funktion lcm" << endl;
          cerr << "in test " << i << " bei Zeile " << __LINE__ << endl;
          exit (-1);
        }


      a *= u;
      b *= v;

      if (sign_u == 1 && sign_v == 1) a += b;
      if (sign_u == -1 && sign_v == 1) a = b - a;
      if (sign_u == 1 && sign_v == -1) a -= b;

      if (a != gg)
        {
          cerr << "Fehler in Member-Funktion xgcd in Test " << i;
          cerr << " bei Zeile " << __LINE__ << endl;
          exit (-1);
        }
    }

  return 0;
}

