Primzahlgenerator für sehr sehr große Primzahlen

Computer: Software & Programmierung .NET & C#
#1

hi Leute,

ich habe in c#.net einen „Pseudo“- Zufallsgenerator für sehr große ungerade Zufallszahlen (4000 bit und größer) programmiert. Mit dem Miller-Rabin-Test prüfe ich ob diese Zahl eine Primzahl ist, wenn nicht erhöhe ich meine Zahl um 2.

Solch ein Test läuft bei mir meist über 1 Stunde. Das ist mir viel zu lange:
Ist dies ein Problem einer schlechten Programmierung oder ist C# einfach nur viel zu langsam.

Vortest mit Quersummen auf Teilbarkeit brachten keinen Erfolg.

Wer hat mir einen Tipp wie ich weitermachen soll. Danke

#2

Hi Peter,
Sowas in der Art hatte ich auch mal gebastelt. Hab’s grad eben nochmal mit meiner Python-Implementierung ausprobiert: Zufällige Primzahl max. 4096bit: 0,006s…
Hier mal die C# Version:

using System;
public class PrimeNumbers{
 public static int PowerMod(int x,int y,int z){
 if(y==0){return 1;}
 if(y%2==0){return PowerMod((x\*x)%z,y/2,z);}
 else{return x\*PowerMod(x,y-1,z)%z;}
 }
 public static bool isPrime(int x){
 if(x==2){return true;}
 if(x
Hoffe, das funktioniert...
P.S.: Bei Bedarf hätt ich das ganze auch noch in Python, C++, PHP, JavaScript und FreeBASIC.
#3

Hallo Isendrak,

Wenn ich mir Deinen Code anschaue und richtig verstehe, kann man damit höchstens eine Primzahl mit 32 Bit finden, mehr kann ein UInt nicht verwalten. Mit Uint64 maximal 64 Bit.

Die Primzahlprüfung stimmt bei Ergebnis: false auf jeden Fall, bei Ergebnis: true ist das aber nicht zu 100 % garantiert.

Mache ich her einen Denkfehler?

Dank an Isendrak und die anderen die sich Zeit für mein Problem nehmen.

#4

Ahoi Peter,

Uint32 maximal 32 Bit,
Uint64 maximal 64 Bit.

Whoops, versuch mal statt „int“, „System.Numerics.BigInteger“ (http://msdn.microsoft.com/de-de/library/system.numer…)…
MSDN: „Stellt eine beliebig große ganze Zahl mit Vorzeichen dar.“

P.S.: Bzgl. „isPrime“: Ich hab leider vergessen, woher ich diese Methode hatte, aber bisher, hatte ich damit noch keine Probleme… Möglicherweise aber auch nur, weil ich bisher nur mit (sehr) kleinen Primzahlen gearbeitet/die Funktion getestet habe…
P.P.S.: Ursprünglich hatte ich dieses Primzahlenzeug auch nur gebastelt, um zu sehen, ob es funktioniert… Könnte ggf. fehlerhaft sein.
P.P.P.S.: Sollte es dennoch helfen, dann wars die ca. 500Byte für die C#-Implementierung definitiv wert…

#5

Hi Isendrak,

ich benutze schon die BigInteger-Variable, aber je größer die Zahl wird desto länger wird die Rechenzeit. Es ist leider nicht so wie bei normalem Int, daß die Rechenzeit unabhägig vom Betrag der Zahl ist. Die Ermittlung einer Primzahl mit 1024 Bit funzt in Sekunden, von 4096 Bit in Minuten bis 1 Stunde, 8192 Bit nach 4 Stunden abgerochen.

Dein Listing hat mir sehr gefallen, denn es hat mir gezeigt, daß meine Grundidee zur Primzahlenerzeugung nicht falsch ist. Nur an der Geschwindigkeit haberts halt noch.

Vielen herzlichen Dank für Deine Bemühungen und Hilfe
Grüße Peter