Proleme mit Rabin-Miller-Primzahlentest

[SilentKiller]

Hallo!

Nach dem ich jetzt mittlerweile seit etwa 1 Woche an meinem Programm sitze und nicht mehr weiter weiß, wende ich mich Hilfe suchend an euch. Ich versuche gerade ein Programm zu schreiben das mir mit Hilfe des Miller - Rabin - Primzahlentest große Primzahlen generiert. Ich hatte es beinahe geschafft das Programm zum Laufen zu bekommen, aber mittlerweile will der Computer nicht mal mehr Zahlen die größer 1000 sind berechnen. Die RM-Programmteile habe ich von dieser seite: Fh Flensburg. Zu meiner Entschuldigung: Ich hab's selber versucht zu programmieren, aber die RM - Test Definition war einfach zu hoch für mich . Den Fermat-Test hatte ich jedoch schon selbst geschafft .

Hier ist nun mein Code:

#include <iostream>
#include <fstream>
#include <time.h>
#include <math.h>

using namespace std;

typedef unsigned long long u64;

u64 pot(u64 a, u64 basis){
	u64 temp;
	temp = a;

	for(int i=1; i<basis; i++){
		a = a*temp;
	}
	return a;
}

u64 length(u64 k)
    {
        u64 r = 0;
        while (k != 0)
        {
            k >>= 1;
            r++;
        }
		cout << "length " << r <<endl;
        return r;
    }


u64 bit(u64 i, u64 e)
    {
        return e >> i & 1;
    }

	
		

u64 modexp2(u64 m, u64 e, u64 n)
{
    u64 p = 1;
    for (u64 i = length(e) - 1; i >= 0; i--)
    {
        p = p * p % n;
        if (bit(i, e) == 1)
            p = p * m % n;
    }
    return p;
}

bool witness(u64 a, u64 n)
{
    u64 f=1, x;
    for (u64 i=length(n-1)-1; i>=0; i--) 
    {
        x=f;
        f=x*x%n;
		if (f==1 && x!=1 && x!=n-1) return true;
        if (bit(i, n-1)==) f=f*a%n;
    }
    return f!=1;
}

bool miller_rabin(u64 n, u64 k)
{
    u64 a=1;
	u64 count = 0;
    for (u64 i=0; i<k; i++) 
    {
		while (a!=-1){
			a = rand()%n-1;
			count +=1;
			if (a<n-1 && a>2 && a%2 != 0)
				break;
		}
        if (witness(a, n)) return true;
    }
    return false;
}

int main (){
	fstream datei("d:\\# Privat\\primNumbers.grr", ios_base::out);

	if (!datei.is_open())
	{
		cerr << "Error: Can't open file!" << endl;
		system("Pause");
		exit(1);
	}

	u64 prim=1;
	u64 n=10, counter=0;

	srand((int)time(0));

	cout << "primeTest: ";
	cin >> prim;
	prim = pot(2,prim)-1;

	cout << prim << endl;
	while(1){
	if(!miller_rabin(prim,n)){
		datei << prim << " ";
		counter +=1;
		if(counter == 5){
			datei << "\n";
			counter = 0;
		}
	}
	else
		;
	prim += 2;
	cin.clear();
	}
	system("PAUSE");
	return 0;
}

Nun zu meiner Frage: Könnte mir jemand folgendes erklären:
1. Wie kann man per cout Zahlen in Dualschreibweise ausgeben? Ich kenne

cout << oct << Zahl << hex << Zahl << dec << Zahl

2. Wie kann ich selber Datentyp definieren? Zb. eine Integer Zahl die 128 Bits hat.
3. Was ist überhaupt an meinem Code oben falsch?

Ich wäre sehr dankbar über eine Antwort, da ich mittlerweile am verzweifeln bin!
Achja, Also Compiler benutz ich Visual Studio C++ 2005.

Mfg

SiK

 

[KHORN]

2. Wie kann ich selber Datentyp definieren? Zb. eine Integer Zahl die 128 Bits hat.

Wenn du ganz große Zahlen hast, die nicht in ein normales int passen, dann nimm doch einfach :

unsigned int zahl;

Hab dich hoffentlich nicht falsch verstanden



Gruß KHORN

 

[Tobias K.]

moin


Zu 1.:
Für binäre Dahrstellung gibt es glaube ich nichts fertiges. Wie man das aber macht wurde hier schon oft besprochen.

Zu 2.:
Es gibt ne Klasse, welche glaube ich "Large Number" heisst. Die ist für genau sowas gemacht.

Zu 3.:

if (bit(i, n-1)==) f=f*a%n;

Nach dem == sollte noch was kommen....


mfg
umbrasaxum

 

[SilentKiller]

@KHORN Leider reicht das nicht aus. Da wird ja nur das Vorzeichen "weggeschnitten".

@Tbias K. Ja du ahst Recht, da sollte eigentlich dastehen:

if (bit(i, n-1)==1) f=f*a%n;

Weisst du zufällig wie die Klasse heisst, weil ich bisher noch nichts gefunden hab.

Mittlerweile weiss ich das es an der integer Zahl liegt, da die "sinnlos" zahlen verarbeitet wenn die zahl zu groß wird. und das passiert bei mir. Deswegen brauch ich einen großen Integer Zahlentyp.

Bin dankbar für jeden Lösungsansatz!

Mfg

SiK

 

[deepthroat]

Hi.

Dein Problem ist, das du überall unsigned long long verwendest, allerdings mehrere Tests auf < 0 hast -- unsigned Variablen können logischerweise nicht kleiner als 0 sein.

Dann solltest du die rand() Funktion anders anwenden, so bekommst du ziemlich schlechte Zufallszahlen. (siehe http://www.tutorials.de/tutorials225751.html)

Gruß