Rabin Krypto Kongruenzbedingung

hi,

schreibe grad eine (bzw. versuche es grad) eine Rabin verschlüsselung zu realisieren.
Ich hab dabei nur ein Problem nämlich das ich nicht weiss wie ich die Kongruenzbedingung realisieren soll.
Kann mir da bitte jemand einen denkanstoß geben.

Schon mal vielen dank.

An bei die Kongruenzbedingung lautet:

p≡q≡3(mod 4)

Thuruk

Hast du schon eine Liste von Primzahlen?

bool finde_primzahlen_nach_bedingung(int *zahlen, int *i, int *j)
{
    int anzahl=sizeof(zahlen)/sizeof(int);
    for(*i=0; *i<anzahl; ++*i)for(*j=0; *j<anzahl; ++*j)if(bedingung&&i!=j) return true;
    return false;
}

//...

int *zahlen;

//erstelle Liste mit Primzahlen

int i,j;

if(finde_primzahlen_nach_bedingung(zahlen, &i, &j))
{
    //mache etwas mit zahlen[i] und zahlen[j]
}

hi

erst mal danke aber ich hätte noch ne frage verstehe ich dich richtig das ich zahlen mehrere Primzahlen hinterlegen muss, wenn ja wie viele währen da angebracht.

Könnte man die Funktion auch so umschreiben das man diese nur mit 2 primzahlen durchführt und dann ein true ode false bekommt? Wie müsste das dann aussehen?

Thuruk

diese nur mit 2 primzahlen durchführt und dann ein true ode false bekommt?

Die 'bedingung' im Code sollte in diesem Fall true sein. Die Funktion musst du halt noch aufstellen, ebenso eine, um Primzahlen zu finden, wenn du noch keine vorgegebenen hast.

ok ich blick die funktion nicht so ganz vielleicht kanst du mir ja helfen hab folgende Funktion um eine primzahl zu ermitteln

long int primzahl() {
        	// Variablendefinition - belegung
        	   long int a;          //Hier wird die wahrscheinliche Primzahl gespeichert
        	   int i;               //Zaehlvariable
        	   int flag;            //einfache entscheidungs - variable

            // Voreinstellung fuer das ermitteln der Zuffalszahl
               srand(time(0));

            // Ermitteln der Primzahl beginnt mit abarbeitung der Schleife
            	do {
                    // entscheidungsvariable zuruecksetzten
            		   flag = 0;    
            		// Zufallszahl ermitteln 
            		   a =rand()%400+1;
            		// prüfen ob es eine Primzahl ist 
            		   if (a % 2 == 0) {
 	                       flag = 1;
                       }
     	            // Versuche variable a mit den ungeraden Zahlen von 3 bis sqrt(a) zu teilen!  
     	               for (i = 3; i <= sqrt(a); i = i + 2) {
                	       if (a% i == 0) { //Teilertest
                	          flag = 1;
             	           }
           	            }
     	            // Wenn es hier rausgeht dann ist a eine Primzahl
            	}while (flag == 1); 
        	// Rueckgabe der Primzahl
               return a;           
        }

und jetzt hab ich mir gedacht das ich in etwa sowas gedacht

//...

long int p;
long int q;

do {

  // 2 Primzahlen ermitteln die ungleich sind
  do {
    p = primzahl();
    q = primzahl();
  } while (p!=q);

  // und jetzt schauhen wir ob die bedingung erfuellt ist wenn nicht dann wiederholen wir das ganze

} while(primzahl_nach_bedingung(p,q));

// ...

Nun meine frage wie müsste die bedingung primzahl_nach_bedingung(long int p,long int q) aussehen

Thuruk

Ich würde keine zufälligen Zahlen untersuchen, sondern eine Liste von z.B. 100000 bis 200000 abarbeiten und alle gefundenen Primzahlen in ein Array schreiben.

http://de.wikipedia.org/wiki/Sieb_von_Atkin

Solche Methoden zu verwenden, ist sicher effektiver. Kannst aber auch jede Zahl von x bis y durch alle zahlen bis sqrt(zahl) dividieren - ist der Rest niemals 0, so ist es eine Primzahl.

Danach kannst du die ermittelte Liste durchgehen, um ein Paar zu finden, dass die Kongruenzbedingung erfüllt.

ja das ist auch nen guter ansatz hab jetzt aber schon ein größeres hintergrundprogramm daher bin ich jetzt ein bisschen gezwungen mit zufahlzahlen zu arbeiten, ein weiterer grund dafür ist das ich mich auch gezwungen sehe etwas auf die Effektivität zu achten. daher meine bitte könntest du mir mal zeigen wie die funktion ausehen müsste.

Wie gesagt riesen dank von meiner seite für die bisherige und zukünftige unterstützung^^

Thuruk

#include <iostream>
using namespace std;

bool bedingung(int i, int j)
{
	//Bedingung
}

int main()
{
	int ende=100; //oder andere
	int start=0; //oder andere
	int i, j, k=0, *zahlen_pre=new int[ende-start];
	bool kontrolle=true;

	for(i=start; i<ende; ++i)
	{
		for(j=2; j<=sqrt((double)i); ++j) if(i!=j&&i%j==0) kontrolle=false; //Primzahl?
		if(kontrolle)
		{
			zahlen_pre[k]=i;
			++k;
		}
		kontrolle=true;
	}

	int *zahlen=new int[k];
	for(i=0; i<k; ++i) zahlen[i]=zahlen_pre[i];
	delete []zahlen_pre;

	for(i=0; i<k; ++i) for(j=0; j<k; ++j) if(i!=j&&bedingung(zahlen[i], zahlen[j]))
	{
		cout << zahlen[i] << '\t' << zahlen[j] << '\n';
		//mache etwas mit zahlen[i] und zahlen[j]
	}
}

Weiter verbessern kannst du das mit angepassten Variablenlängen je nach Zahlenbereich und den schon erwähnten Siebmethoden.