Zum Inhalt springen

Rsa verfahren Primfaktorzerlegung


SurTana

Empfohlene Beiträge

Hi Leute

hab da ein Problem beim RSA verfahren.

ich soll für Informatik einen Algorythmus schreiben der den Öffentlichen schlüssel N in die beiden Primzahlen p und q zerlegt habe aber keine ahnung wie man das macht. habe auch schon versucht über google was zu finden bin aber auf keine lösung gestoßen.

ich weiss zwar wie man eine zahl in ihre Primfaktoren zerlegt aber das bringt mir nichts weil man dabei auf eine vielzahl von primzahlen stößt ich muss aber wissen wie man von einer Zahl genau 2 primfaktoren bekommt.

ich hoffe ihr versteht mein problem.

und wenn jemand das kann, ich soll den algorythmus in Java machen, aber mir würde die mathematische funktion auch schon reichen den rest würde ich vielleicht selber hinbekommen, auch wenn ich ncihtmal mehr weiss wie man ein grundgerüst macht ^^

vielen dank

SurTana

Link zu diesem Kommentar
Auf anderen Seiten teilen

es ist ja so das ich den öffentlich schlüssel (N) vom RSA verfahren habe und der wird ja aus 2 primzahlen zusammengesetzt ( p * q ). Die Zahl die ich abfrage ist also auf jedenfall eine Zahl mit 2 primzahlen. ich will ja ganricht jede Zahl zerlegen nur eine bestimmte die auf diese weise entstanden ist.

Link zu diesem Kommentar
Auf anderen Seiten teilen

Du kannst doch nicht jede Zahl in genau zwei Primzahlen zerlegen. Sonst gäbs ja die Primfaktorzerlegung nicht mit n Primzahlen.

Peter

Nein, aber ich wette das es genau einen Fall gibt wo es nur zwei Primfaktoren gibt...und genau die sucht man ja.

/: So aus dem groben heraus würde ich es so machen:


p = 2

q = 2

do {

 p = nextPrim(p)

 do {

  q = nextPrim(q)

  if(p*q == N) {

   //gefunden

  }

 } while (q < N)

} while(p < N)

//nextPrim liefert jeweils die nächste Primzahl

Anders als schlichtes durchprobieren geht nicht, das is ja der Trick an der Sachen mit Primfaktoren

(Natürlich ist das da oben total unoptimiert und mir fallen auch schon wieder 2 Sachen ein wie man eine MENGE Iterationen sparen könnte, aber das machst du schön selbst ;) )

Link zu diesem Kommentar
Auf anderen Seiten teilen

Ok, das wusste ich nicht, dass dieser Schlüssel aus zwei Primzahlen gefertigt wird.

Die Bruteforce-Methode ist natürlich jetzt, durch die Primzahlen zu iterieren und versuchen, die Zahl damit mit einem Modulo-Teiler auf das Ergebnis 0 zu bringen. In welchem Zahlenraum bewegen wir uns denn dann? Soll heissen, welche mögliche Anzahl Primzahlen gibt es in diesem Raum?

@Whatever: das glaube ich nicht. Es gibt ganz viele Fälle, wo eine Zahl aus genau zwei Primzahlen gebildet wurde. Mir war nur nicht bekannt, das bei diesem Schlüssel diese Voraussetzung zutrifft.

Peter

Link zu diesem Kommentar
Auf anderen Seiten teilen

irgendwie funktioniert das nicht so ganz. erstens habe ich keine methode nextprim. hab mal versucht eine zu finden aber das klappt nicht. der sagt bei p*q == N das Wert erforderlich ist aber Variable gefunden Wurde.

ich verzweifel hier volkommen weil es einfach nicht klappt

so sieht mein programm aus


import java.io.*;

import java.awt.*;

import java.awt.event.*;




/**

 * <p>Überschrift: </p>

 *

 * <p>Beschreibung: </p>

 *

 * <p>Copyright: Copyright (c) 2006</p>

 *

 * <p>Organisation: </p>

 *

 * @author unbekannt

 * @version 1.0

 */

public class Main extends Frame implements ActionListener

{

    int p,q,N;

    int x=1;

    long prim;

    Button calc;

    Button quit;

    Label nfo;

    TextField input, output;


    public Main()

    {

           setLayout(null);

     setSize(600,500);

     setTitle("Primfaktorzerlegung");

     setBackground(Color.gray);

     calc=new Button("Berechnen");

     calc.setBounds(50,400,200,50);

     calc.addActionListener(this);

     add(calc);

     quit=new Button("Schliessen");

     quit.setBounds(300,400,200,50);

     quit.addActionListener(this);

     add(quit);

     nfo=new Label(" Geben Sie hier die zu berechnende Zahl ein:");

     nfo.setBounds(50,70,300,50);

     add(nfo);

     input=new TextField();

     input.setBounds(50,150,200,20);

     add(input);

     output=new TextField();

     output.disable();

     output.setBounds(50,250,200,20);

     add(output);

     show();


    }


     public void actionPerformed (ActionEvent ae)

     {

     if (ae.getSource()==quit)

        System.exit(0);

     if (ae.getSource()==calc)

        prim(prim);


     }


    /* public void textValueChanged(TextEvent te)

     {


     }

         */

    public long prim(long prim)

    {


       String N = input.getText();

       prim=Integer.parseInt(N);

       // N = 2773;

        p = 2;

        q = 2;

        do {

            p = nextprim();

                do

            {

                q = nextprim();

                    if( p * q = N)

                    {

                        System.out.println(p);



                } while (q < N);

            }while(p < N);

        }while (p*q == N);



        return p;

    }


    /**

     * nextPrim

     *

     * @param p int

     * @return int

        */


  static int nextprim()


  {


    do


    {


      //Primzahlen ausschliesslich ungerade (ab 3)


      x += 2;


    }


    while (!(isprim(x)));


    //Kommentar kann zu Testzwecken entfernt werden.


    //Ausgabe nur um zu zeigen, dass das Programm arbeitet


    //System.out.println(x);


    return x;


  }




  //normaler Algorithmus: Ueberpruefung, ob eine Zahl von n/2


  //bis 1 n teilt => keine Primzahl (sehr lange Rechenzeit)


  //deshalb wird hier ein sehr viel schnellerer Algorithmus


  //verwendet


  static boolean isprim(int n)


  {


    int k = bisqrt(n);


    //stellt sicher, dass k ungerade ist


    k = k + 1  + (k%2);


    return (!(isdiv(k,n)));


  }




  //Ueberprueft, ob eine Zahl von k bis 1 n teilt


  static boolean isdiv(int k, int n)


  {


    int t = 3;


    boolean b = false;




    while (t <= k)


    {


      if ((n % t) == 0)


      {


        b = true;


        break;


      }


      t += 2;


    }


    return b;


  }




  //rekursive Berechnung der ganzzahligen Quadratwurzel von n


  static int bisqrt(int n)


  {


    int l=0;




    if (n == 0)


      return 0;


    else


    {


      l = 2 * bisqrt(n/4) +1;


      if (l*l <= n)


        return l;


      else


        return l-1;


    }


  }



    public static void main(String[] args) {

        Main main = new Main();


    }

}


Link zu diesem Kommentar
Auf anderen Seiten teilen

Servus,

Du solltest erst mal Deine Compilerfehler bereinigen, die nichts mit dem Problem zu tun haben. Dann könntest Du Deinen Code um unwichtige Teile erleichtern, da ich keine Zeit habe, 229 Zeilen zu lesen und nachzuvollziehen, wenn das Problem vielleicht in 5 Zeilen steckt.

Die Fehler, die der Compiler bis jetzt schmeisst, sind im if in Zeile 84, da solltest Du vielleicht mit "==" statt mit "=" prüfen. Danach kommen drei Fehler in den Zeilen 89, 90 und 91, wo Du Strings mit "<" oder "==" vergleichen willst. Und in einer statischen Methode (nextprim) kannst Du natürlich keine nichtstatischen Attribute der Klasse ansprechen (Zeilen 114, 118, 126).

Das sind jetzt alles wirkliche Anfängerfehler, die Dir der Compiler erklärt und die Du beim nächsten Mal bitte bereinigst, bevor Du Code anbietest.

Bis nachher!

Peter

Link zu diesem Kommentar
Auf anderen Seiten teilen

Dein Kommentar

Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.

Gast
Auf dieses Thema antworten...

×   Du hast formatierten Text eingefügt.   Formatierung wiederherstellen

  Nur 75 Emojis sind erlaubt.

×   Dein Link wurde automatisch eingebettet.   Einbetten rückgängig machen und als Link darstellen

×   Dein vorheriger Inhalt wurde wiederhergestellt.   Editor leeren

×   Du kannst Bilder nicht direkt einfügen. Lade Bilder hoch oder lade sie von einer URL.

Fachinformatiker.de, 2024 by SE Internet Services

fidelogo_small.png

Schicke uns eine Nachricht!

Fachinformatiker.de ist die größte IT-Community
rund um Ausbildung, Job, Weiterbildung für IT-Fachkräfte.

Fachinformatiker.de App

Download on the App Store
Get it on Google Play

Kontakt

Hier werben?
Oder sende eine E-Mail an

Social media u. feeds

Jobboard für Fachinformatiker und IT-Fachkräfte

×
×
  • Neu erstellen...