Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Algorithmische Primfaktorzerlegung
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Algorithmische Primfaktorzerlegung
 
Autor Nachricht
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 24 Aug 2005 - 17:02:55    Titel: Algorithmische Primfaktorzerlegung

Hallo miteinander,

Da ich gerade ein Computeralgebrasystem schreibe, muss ich wissen, wie ich verhältnismässig schnell eine natürliche Zahl x in ihre Primfaktoren zerlege.
Wie es vom Prinzip her funktioniert, weiss ich, nämlich:
Alle Primzahlen (2, 3, 5, ...) durchgehen, und testen, ob x/primzahl restlos aufgeht, und mit dem Ergebnis vom x/primzahl weitermachen.

Nun ja, bei einer relativ grossen Zahl wie z.b. 123456789012 ist der letzte Primfaktor 10288065751. Mein Algorithmus würde also Stunden dauern, bis er alle Primzahlen bis dahin getestet hat. Mein Taschenrechner spuckt die Lösung allerdings in 1s aus.

Wie muss ich es also eine Primfaktorzerlegung gescheit anstellen, dass sie realtiv schnell ist? Hab auch schon ewig gegoogelt und nichts gefunden.

Gruss, Marko
xaggi
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 15.03.2004
Beiträge: 1190

BeitragVerfasst am: 24 Aug 2005 - 18:35:14    Titel:

Also das folgende primitive Programm:

Code:

#include <stdio.h>
#include <math.h>

int isprim(unsigned long z)
{
  unsigned long i;
  for(i=2; i<=z/2; i++)
  {
    if(!(z%i))
    {
      return 0;
    }
  }
  return 1;
}

int main(void)
{
  unsigned long z, i;
  printf("Zahl:");
  scanf("%lu",&z);
  printf("\nErgebnis:");
  while(z>1)
  {
    printf("\nnaechster durchgang: %lu",z);
    i=2;
    while(1)
    {
      if(!(z%i) && isprim(i))
      {
        printf(" %lu",i);
        z/=i;
        break;
      }
      i++;
    }
  }       
  printf(" ENDE\n");
  return 0;
}


Rechnet mir Primfaktoren in deutlich unter 1 s aus.
Datentypbedingt ist die Grenze natürlich bei 4294967295.

Einen wesentlich effizienteren Algorithmus gibt es meines wissens nicht, was ja gerade der grund dafür ist, dass die bewährten verschlüsselungstechniken (RSA etc.) die auf großen primzahlen basieren so sicher sind.
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 24 Aug 2005 - 21:29:04    Titel:

Das Script wird für die Zahl 123456789012 auch ein paar Minuten wenn nicht sogar Stunden brauchen, angenommen, es könnte grosse Zahlen handhaben.

Danke trotzdem, Marko
xaggi
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 15.03.2004
Beiträge: 1190

BeitragVerfasst am: 24 Aug 2005 - 21:42:05    Titel:

Rein interessehalber: Was hast du eigentlich für nen Taschenrechner, dass der sowas kann?
Whoooo
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 08.06.2005
Beiträge: 8988

BeitragVerfasst am: 24 Aug 2005 - 21:43:00    Titel:

das hab ich mich auch gefragt^^
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 24 Aug 2005 - 22:06:25    Titel:

TI89 von Texas Instruments.

Ich bin gerade dabei, das hier zu implementieren:
http://de.wikipedia.org/wiki/Quadratisches_Sieb

Kennt das jemand? Es funktioniert so gut wie, nur hab ich ein Beispiel gefunden, bei dem ich scheinbar keine 2 k (aus x^2=k (mod n)) finden kann, das 'glatt' ist, also dessen höchste Primfaktoren kleiner als 20 sind, nämlich: 5415729.

Hier noch eine Seite dazu:
http://www.iti.fh-flensburg.de/lang/krypto/algo/quadraticsieve.htm

Gruss
tech
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 14.08.2005
Beiträge: 14

BeitragVerfasst am: 25 Aug 2005 - 23:15:02    Titel:

Versucht doch mal den Algorithmus von Rabin-Miller. Ist sehr schnell, liefert gelegentlich eine falsche Antwort.
Ist n zusammengesetzt, ist die Wahrscheinlichkeit eines Irrtums <1/4
tech
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 14.08.2005
Beiträge: 14

BeitragVerfasst am: 25 Aug 2005 - 23:17:55    Titel:

Sorry, ich dachte es um Primzahltest, nicht um Primfaktorzerlegung Laughing
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 26 Aug 2005 - 15:06:16    Titel:

Das ist gut, beim Primfaktorenzerlegen nach Rho (was ich implementiert habe) muss man gelgentlich auch testen, ob x eine Primzahl ist.

Miller-Rabin hört sich gut an, aber bei einer Zahl wie z.B. 3894729384721 ist q bei n-1=2^k*q 1947364692360. Weil man ja im Algorithmus (a^q) mod n rechnen muss, kann ich einpacken, denn a^1947364692360 wird ne weile dauern (auch bei sukzessiver Quadratbildung).

Wie kann ich es also noch ein wenig geschickter lösen?

Danke & Gruss
fas
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 26.05.2005
Beiträge: 2086

BeitragVerfasst am: 26 Aug 2005 - 21:13:49    Titel:

Hab alles gelöst.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Algorithmische Primfaktorzerlegung
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum