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;
}