Große Primzahlen für RSA berechnen

Ich habe auf dem Gym im Informatikunterricht ein kleines Java - Programm geschrieben um Primzahlen zu berechnen:

// auszug der Berechnung, ohne ausgabe
int zahl=3;
int n=1;
int prim[] = new int[anzahl];
prim[0]=2;
while(n < anzahl)
{
   istprim = true;
   int m= 0;
   while(istprim && m < n && zahl >= prim[m]*prim[m])
   {
      if(zahl%prim[m] == 0) istprim=false;
      m++;
   }
   if(istprim)
   {
      prim[n]= zahl;
      n++;
   }
   zahl+=2;
}

Nun erstmal das ganze in cpp nachgeschrieben (lerne cpp gerade, bin noch ganz am Anfang). Das Problem bei großen Primzahlen ist, dass alle vorherigen im Array abgelegt werden und ich ein int myArray[] "nur" mit 1048576 (int myArray[1048576]) initialisieren kann (nehme an liegt am Speicher?) geschachtelt genauso in myArry[1024][1024] max. sonst Fehler beim compilen ...

Meine Idee war dann, die Zahlen in ein File zu schreiben und wieder auszulesen ... Der folgende source ist mit Sicherheit nich schön, aber vergebt den Anfängern ...

#include <iostream>
#include <string>
#include <sstream>
#include <math.h>
#include <fstream>

std::istringstream is;
std::string anzahlS;
std::string end;
unsigned int anzahl;
unsigned int zahl = 5;
unsigned int currentZahl = 3;
bool istprim;
const char *pfad = "C:\\Borland\\Bcc55\\Bin\\primlist.dat";
std::fstream list;

int main()
{
    std::cout<<"Anzahl der gewünschten Stellen der Primzahl eingeben ..."
             <<std::endl;
    std::getline(std::cin, anzahlS);
    is.str(anzahlS);
    is >> anzahl;
    unsigned int stellen = pow(10,(anzahl-1));
    std::cout<<stellen<<std::endl;
    std::getline(std::cin,end);
    list.open(pfad, std::ios::out|std::ios::trunc);
    if(!list)
    {
        std::cout<<"File not found!\n";
        list.close();
    }
    else
    {
        list<<"3";
        list.close();
        while(zahl <= stellen)
        {
            list.open(pfad, std::ios::in);
            list.seekg(std::ios::beg);
            istprim = true;
            while(istprim && !list.eof() && zahl >= currentZahl*currentZahl)
            {
                list>>currentZahl;
                if(zahl%currentZahl == 0) istprim = false;
            }
            list.close();
            if(istprim)
            {
                list.open(pfad, std::ios::out|std::ios::app);
                list<<"\n"<<zahl;
                list.close();
                std::cout<<zahl<<" zahl: "<<zahl<<" currentZahl: "
                         <<currentZahl<<" modula: "
                         <<zahl%currentZahl<<std::endl;
            }
            zahl += 2;
        }
        list.close();
    }
    std::getline(std::cin,end);
}

So, läuft aber nicht anständig ... Hab ich Java - Operatoren übernommen, die so
nicht funzen, oder woran liegt's????

Danke schon mal im Voraus!

Hoi,

Primzahlen in der Größe, wie du sie für den RSA benötigst, werden nicht berechnet sondern abgeschätzt. Es gibt spezielle Näherungsverfahren, mit denen man abschätzen kann, wie wahrscheinlich es ist, dass eine bestimmte Zahl eine Primzahl ist.

Wenn ich richtig informiert bin, geht man von einer Primzahl aus, wenn die Wahrscheinlichkeit kleiner als (1/2)^60 ist, dass die Zahl keine Primzahl ist.
Man bezeichnet solche Primzahlen, als "industriell", weil sie nicht mathematisch 100%ig korrekt berechnet werden. Andererseits ist es wohl wahrscheinlicher, dass du zweimal hintereinander den Jackpot knackst, als dass sich so ein Verfahren irrt.
Am besten du siehst dir mal im Java API den Source der Klasse java.math.BigInteger an, die implementiert einen solchen Algorithmus.

Das Problem bei großen Primzahlen ist, dass alle vorherigen im Array abgelegt werden und ich ein int myArray[] "nur" mit 1048576 (int myArray[1048576]) initialisieren kann (nehme an liegt am Speicher?) geschachtelt genauso in myArry[1024][1024] max. sonst Fehler beim compilen ...

Wirklich Fehler beim Compilieren? Welchen Compiler benutzt du denn?

Große Arrays muss man auf den Heap (mit new) anlegen, weil der Stack nicht groß genug ist.

Benutze Borland 5.5
könntest du mir ein Beispiel snippet posten für die initialisierung eines solchen Arrays? plz
Fehler bei int myArray[1073741824]; :

Error E2449 prim.cpp 16: Size of 'myArray' is unknown or zero

nehme mal an RTFM, right?

1073741824

nicht übertreiben. das ist zuviel...

int* myArray = new int[2000000];
// mit dem array arbeiten
delete[] myArray;

Naja, wahrscheinlich werden deshalb auch keine Primzahlen, wie oben erwähnt berechnet, zumindest nicht so wie ich das mache ZUviel gibt's nicht

[quote]ZUviel gibt's nicht[quote]

Für mehr brauchst du ein 64-bit CPU und Betriebssystem und viel Speicher.

Kann ich auch eine größere int initialisieren?

muhkuhmasta

du brauchst 6545 arrayelemente wenn du alle primzahlen im bereich eines unsigned long int berechnen willst. ablegen würd ich alle folgenden in ner datei. und wenn du noch größere zahlen (also für rsa) berechnen willst hast du zwei möglichkeiten 1) du holst dir eine library für "arbitrary length integer math"
2) du schreibst dir selbst die funktionen dafür

und meines wissens nach braucht man keinen 64bit cpu und ne menge speicher um pgp zu benutzen

SideWinder

Nein größere Integer sind im Standard nicht vorhanden, viele Systeme bieten allerdings noch einen "long long" bzw. auch manchmal "__int64" genannten Integer an.

Wenn du noch größere Zahlen benötigst wirst du eine externe Library benötigen, findest du bestimmt bei Google.

Zum Thema Array schlage ich vor du kümmerst dich ganz kurz in der Hilfe um std::vector und kannst relaxed beliebig viele Elemente verwalten

MfG SideWinder