test pierwszości na b. dużych liczbach

0

Witam.
Albowiem najpierw opisze co robię.
Tak więc piszę test pierwszości na b. dużych liczbach.
Wybrałem dwa algorytmy
-Millera Rabina (propabilistyczny)
-AKS (deterministyczny)

Napisałem własną klasę do obsługi b. dużych liczb.
Przeciążyłem odpowiednie operatory
I przerobiłem wcześniej napisany algorytm Millera Rabina by działał pod obsługą mojej klasy.

Problem polega na tym, że przestaje działać. wysypuje błąd z pamięcią.
Nie wiem czy to błąd z mojej klasie dla dużych liczb... bo ona przy testowaniu (osobno, operatorów) działała już poprawnie.
Debbuguje sobie krok po kroku w VS tylko za każdym razem jak coś zmienię by "poprawić" błąd to pojawia się zaraz obok.

Oto mój kod.
Funkcja główna

 #include "stdafx.h"
#include <iostream>
#include "total.h"
#include "Miller_Rabin.h"
using namespace std;



int main()
{
total n,k;

cout<<"Podaj liczby.\n";
cin >>n;
cin >>k;

if (test(n, k) == 1)
cout<<"Liczba jest prawdopodobnie pierwsza.\n";
else
cout<<"Liczba jest zlozona.\n";
system("PAUSE"); 
return 0;
}


I Plik Miller_Rabin.h

 #include <stdio.h>
#include <stdlib.h>
#include <time.h>

int potega_dwojki[128];
total dwa=2,jeden=1,zero,radzik; 
int tpow2(int b)
{
     int i,powerek=1;
	 if(b==0) return 1;
	 else if(b==1) return 2;
     for(i=0;i<b; ++i)
     powerek*=2;
     return powerek;
} 
//------------------------------------------------
//      a^b mod m
//------------------------------------------------
total modulo(total a, total b, total m)
{
	total i;
	total wynik;
	wynik = jeden;
	total x;
    x = a % m;  //a mod m 
 
		for (i=jeden; i<=b; i*=dwa)
		{
			x %= m;   // x = x mod m 
			if ((b == i) != 0)  // ( b AND i ) różne od 0
			{
				wynik *= x; // wynik = wynik * x
				wynik %= m; // wynik = wynik mod m 
			}
			x *= x; // x = x^2
		}
 
return wynik;
}
 
 
//------------------------------------------------
//      TEST PIERWSZOSCI MILERA_RABINA
//
//      Liczba Ferriera 20988936657440586486151264256610222593863921
//------------------------------------------------
int test(total n, total k)
{
	
    for (int i=0; i<=127; i++)
	{	
      potega_dwojki[i]=tpow2(i);  // generownie poteg dwojki 
	}  //algorytm potegowania dwojki
	total a, d, i, s,r;
    int pierwsza;
	srand(time(NULL));
 
	if (n%dwa == 0) // jezeli parzysta to liczba jest zlozona 
	{
		return 0;
	}

//------------------------------------------------
//      OBLICZENIE s i d
//------------------------------------------------
 
 for(d = n - jeden; d % dwa == 0; ++s) // petla wykonuje sie do osiagniecia nieparzystosci d
	 d /= dwa;
//------------------------------------------------
//      KROTNOSC SPRAWDZENIA
//------------------------------------------------
for (i=0; i<k; ++i)
{
	radzik=rand();
	total _tmp;
    _tmp=n-jeden;
    a = (radzik % _tmp)+jeden; // wybór świadka pierwszości 
	if (modulo(a, d, n) != jeden) //obliczanie a^d mod n
	{
		pierwsza = 0;
		total _tmp2;
        _tmp2=(s-jeden);
		for (r=0; r<=_tmp2; ++r)
		{
			total _tmp3;
			_tmp3=d*int(potega_dwojki[int(r)]);
            total mod=modulo(a, _tmp3, n);
			_tmp=n-jeden;
            if (mod == _tmp )// obliczenie a^(2^r*d) mod n
			{
				pierwsza = 1;
				break;
			}
		}
	if (pierwsza == 0)
	{
		return 0;
	}
	}
}
 
return 1;
}
0

łatwo sprawdzić gdzie jest błąd. Zrób na początku typedef long long int total; i usuń includa Twojej klasy i zobacz czy będzie działać dla liczb w okolicy 2^63

EDIT:
swoją drogą, patrząc na te dwie linijki:

int potega_dwojki[128];
total dwa=2,jeden=1,zero,radzik; 

w pliku nagłówkowym polecam Ci wrócić do kursu C++

1 użytkowników online, w tym zalogowanych: 0, gości: 1