libNT

#include "libnt.h"

// Standard libraries
#include <string>
#include <iostream>

// For the BigInteger class itself.
#include "BigInteger.hh"

// For the 4 routines `easy BI/BU <=> string' and `iostream' integration.
#include "BigIntegerUtils.hh"


using namespace std;

libnt::libnt()
{
}

libnt::~libnt()
{
}

bool libnt::MillerRabin(BigInteger ulZahl)
{
 
    // shack the devil:
    srand( (BigInteger)time( NULL ) );

    BigInteger ulBasis;      
    BigInteger ulUngerade;   // eine Zahl, geteilt durch 2 != Rest 0
    BigInteger uiStellen;    // Stellenanzahl + 1 von ulZahl
    BigInteger zero;		 // 
    BigInteger two=2;
    BigInteger one=1;
    BigInteger tv = 42;		 // The answer of all questions ;-)
    BigInteger three = 3;
    BigInteger ten = 10;
    //BigInteger rand;
    BigInteger rand_max = 2147483647;
    BigInteger step1;
    BigInteger step2;

    int random = rand();
    //rand = (BigInteger)rand();
   /* ulBasis = (ulZahl-1) * rand() / (RAND_MAX + 1.0);
    if(ulBasis%2 == 0)
        ulBasis--;*/
    ulBasis = 2;
    step1 = (rand_max + three);
    step2.multiply(tv,(BigInteger)random);
    ulUngerade = step2/step1 ;
    if(ulUngerade%two == zero)
        ulUngerade--;

    uiStellen = 1;

    BigInteger ulBuffer = ulZahl;

    while(ulBuffer > zero)
    {
        ulBuffer = ulBuffer/ten;
        uiStellen++;
    }
    
    // ulBasis und ulZahl müssen teilerfremd sein. => ggT == 1
    
    if(this.ggT(ulZahl, ulBasis) != one)
        return false;



    bool bTest1 = false;
    bool bTest2 = false;

    // Teste Zahlen durch:
    // Test 1:
    if(pow(ulBasis, ulUngerade)%ulZahl != one)
        bTest1 = true;

    // Test 2:
    for(BigInteger t = 0; t < uiStellen; t++)
    {
        BigInteger ulPow = pow(two, t);
        ulPow = ulPow * ulUngerade;
        if((BigInteger)pow(ulBasis, ulPow)%ulZahl != -1)
            bTest2 = true;
        else
            bTest2 = false;
    }

    if(bTest1 && bTest2)
        return true;
    else
        return false;


}

BigInteger libnt::pow(BigInteger base, BigInteger exp)
{
	
	BigInteger nTemp = base;
	for(BigInteger i=0; i<=exp; i++)
		nTemp*=base;
		
	return nTemp;
}

BigInteger libnt::ggT(BigInteger m, BigInteger n)
{
  BigInteger iBuffer;
  BigInteger zero;
  while (n > zero)
  {
    iBuffer = n;
    n = m%n;        // Rest aus m/n
    m = iBuffer;    // m = altes n
  }
  return m;
}

BigInteger libnt::bigSqrt(BigInteger a)
{
	BigInteger x    = 1;
	BigInteger y    = 1;
	BigInteger x1    = 1;
	BigInteger y1    = 1;
	BigInteger z    = 0;
	BigInteger nRef = 0;
	BigInteger erg1 = 0;
	BigInteger erg2 = 0;
	BigInteger two = 2;
	BigInteger nTemp = 10;
	
	nRef = a/two;
	x =a;
	while(x!=nRef)
	{
	  x1=x+y;
	  x1=x1 / two;
      y1=a/x1;
      x=x1;
      y=y1;
      nRef=x;
	}
	
	return x;
}