BigInt: RandomRange Funktion?

[Z4ppy]

Ich hab mir diese BigInt-Klasse runtergeladen und in mein neustes Projekt eingebunden. Nun bräuchte ich da aber ein Pendant zur RandomRange-Funktion aus der Math-Unit... Gibts sowas? Wenn nein: Wie kann man sowas programmieren? Nach welchen Regeln muss man da vorgehen?

MfG Z4ppy

[Z4ppy]

*push*

MfG Z4ppy

[blackdrake]

Hallo.

In der Math.pas ist RandomRange definiert mit:

Delphi-Quellcode:

function RandomRange(const AFrom, ATo: Integer): Integer;
begin
  if AFrom > ATo then
    Result := Random(AFrom - ATo) + ATo
  else
    Result := Random(ATo - AFrom) + AFrom;
end;

Du brauchst also ein Random(), das mit BigInt funktioniert.

Leider enthält die BigInt.pas keine Random-Routine.

Eine Google recherche hat mich zu folgendem Forenbeitrag geführt:

http://www.delphi-forum.de/viewtopic...hlight=bignum2

Wenn du auf BigNum2 umsteigst, müsstest du eine Random()-Routine dabei haben.

Wenn es unbedingt BigInt sein muss, könntest du irgendwie das normale "Random(): Integer" so oft kopieren, sodass der BigInteger möglichst voll ausgenutzt wird. Das halte ich aber für etwas umständlich und unprofessionell. Folgender Code (der im Moment nicht funktioniert) als Denkanstoß:

Delphi-Quellcode:

function BigRandom(): TBigInt;
var
  i: integer;
  bg: TBigInt;
begin
  bg := TBigInt.Create;
  for i := 1 to (High(bg) div High(Integer)) do
  begin
    bg.Add(Random(High(Integer));
  end;
  result := bg;
end;

Dann müsstest du eben schauen, wie oft der Integer maximal in den BigInteger "reinpasst" (unter der Annahme, dass Random() stets den höchste Integer-Wert annimmt). Ich würde das mit einer For-Schleife, wie oben gezeigt, machen.

Gruß
blackdrake

[Apollonius]

Dummerweise sind die Zufallszahlen, die du mit der zweiten Methode erhältst, nicht gleich- sondern (annährend) normalverteilt.

[blackdrake]

Zitat:

Zitat von Apollonius

Dummerweise sind die Zufallszahlen, die du mit der zweiten Methode erhältst, nicht gleich- sondern (annährend) normalverteilt.

Da kenne ich leider nicht die mathematischen Hintergründe. Aber ich denke, dass es doch ziemlich egal ist, wie die Verteilung ist, wenn man nicht unbedingt mit Verschlüsselungen arbeitet. Bei der Verschlüsselung ist ja die normale Delphi-Variante von Random() sehr unsicher, da sie nur mit der Systemzeit rechnet und teilweise berechenbar ist. Wenn Random() also unsicher ist, dann ist es ja egal, ob man n verschiedene Random's zusammenaddiert, oder?

// Edit: Mein oben genannter Code ohne obere Grenze kann gar nicht funktionieren, da TBigInt theoretisch unendlich große Werte verwalten kann, also High(BigInteger) = unendlich.

Gruß
blackdrake

[Z4ppy]

Dummerweise arbeite ich mit Verschlüsselungen :D
Zum verlinkten Thema: Leider scheint in dieser Unit auch keine Random-Funktion enthalten zu sein :(
Gibts denn irgendwie "bessere" Random-Funktionen als die der Math-Unit?

MfG Z4ppy

[Meflin]

Zitat:

Zitat von Z4ppy

Gibts denn irgendwie "bessere" Random-Funktionen als die der Math-Unit?

Naja, wenn dus wirklich gut haben willst: Klick ;)

[Apollonius]

Die Windows-Crypto-API bietet die Funktion CryptGenRandom. Wenn du dir damit eine gewisse Anzahl zufälliger Bytes holst, hast du eine gleichverteilte Zufallszahl. Der einzige Nachteil ist, dass der Umfang deines Zahlenraums von der Form 2^n sein muss.

[Dax]

Das macht doch nix - aus den Bytes erstellt man eine BigInt-Instanz und nimmt Min(candidate, max) ;)

[Apollonius]

Das hat dann aber wirklich nichts mehr mit Gleichverteilung zu tun.

[Z4ppy]

@Meflin: Schaut ja eigentlich ganz gut aus, is aber glaube ich ein bisschen zu viel des Guten (ohne Blick auf die Source, kb aufs Reggen :D)

MfG Z4ppy

[gammatester]

Es gibt eine schnellere (mit sehr kleiner Bias) und eine etwas langsamere Methode, die allerdings Gleichverteilung erzeugt. Der Einfachheit sollen bigints zwischen 0 und R-1 erzeigt werden. Wenn R n bits braucht, erzeugst Du ein bigint x mit n random bits.

Methode 1: random = x mod R (wie gesagt hier hast Du eine kleine Störung der Gleichverteilung, die allerdings umso kleiner ist, als R größer wird)

Methode 2:

Code:

repeat
  x = n random bits
  until x<R;
random = x;

Als einfachen cryptografischen Generator kannst Du ISAAC von Bob Jenkins verwenden, statt des Pascal-Link auf seiner Seite kannst Du gleich direkt meine deutsche Seite gehenWE's (C)PRNG.

Gammatester

[Z4ppy]

THX, allerdings muss ich zugeben, dass ich mit dieser Unit net ganz klarkomm :oops:
Was bedeutet denn dieses ctx in jeder Prozedur/Funktion?
Wie generiert man dort nun eine Zufallszahl zwischen 1 und x?

MfG Z4ppy

€dit: Ich glaub, ich werd des random = x mod R machen, denn ich hab ohnehin riesige Primzahlen (1000 bis 20000 stellig :D) in meinem Programm ;) Von denen kann ich dann halt n R berechnen... Was sollte man denn als x nehmen?

[gammatester]

Zitat:

Zitat von Z4ppy

THX, allerdings muss ich zugeben, dass ich mit dieser Unit net ganz klarkomm :oops:
Was bedeutet denn dieses ctx in jeder Prozedur/Funktion?
Wie generiert man dort nun eine Zufallszahl zwischen 1 und x?

MfG Z4ppy

€dit: Ich glaub, ich werd des random = x mod R machen, denn ich hab ohnehin riesige Primzahlen (1000 bis 20000 stellig :D) in meinem Programm ;) Von denen kann ich dann halt n R berechnen... Was sollte man denn als x nehmen?

ctx ist ein Kontext-Record, d.h. Du kannst mehrere Generatoren gleichzeitig haben, bei Delphi hast Du nur einen Kontext nämlich randseed (ein Kontext ist so ähnlich wie eine Klasse oder ein Objekt). Rufe eine der Init-Prozeduren mit Deinen seed(s) auf und dann eine der Funktion isaac_word, oder isaac_long etc. Wenn Du viele Bytes brauchst isaac_read. Wenn Du ein 32-Bit Dword brauchst geht's mit ctx.next und ctx.nextres.

Welche Funktionen Du verwenden kannst, hängt von den biginst ab. Wenn's ein array of cardinal ist, etwa isaac_read(ctx, @DeinArray, length(DeinArray)*sizeof(cardinal)).

Zitat:

Wie generiert man dort nun eine Zufallszahl zwischen 1 und x?

Soll wohl heißen 1 <= ZZ <= x: Wenn dein x zwischen 2^(n-1) und 2^n liegt, mußt Du mindestens n Bits erzeugen, d.h. Du liest mindestens n bits in ein bigint y, bildest y mod x und addierst 1. Bei der letzten Frage: mit x mod R ist halt zwischen 0 und R-1 und wenn Du 1 draufaddierst zwischen 1 und R.

Gammatester

[Z4ppy]

Danke für deine Erklärung, muss aber gleich weg, werds mir daher später ansehen...

Ich meinte: Was muss x sein ;) Eine beliebige, möglichst grosse Zahl?

MfG Z4ppy

[Z4ppy]

Nun nochmal: ich nehme random:=x mod R, R ist eine riesige Zahl - was muss x sein?

MfG Z4ppy

[gammatester]

Zitat:

Zitat von Z4ppy

Nun nochmal: ich nehme random:=x mod R, R ist eine riesige Zahl - was muss x sein?

Und auch noch mal :wink: - damit jetzt endlich klar ist was gemacht werden soll:


R ist eine riesige Zahl und Du sucht eine Zufallszahl z mit 0 <= z < R.

Sei l = ceil(log2(R)) die Bitlänge von R.

Die bessere Methode:

Code:

repeat
  erzeuge l Zufalls-BITS
  mach aus den l BITS ein bigint x >=0
until x < R
z := x;

Mit der mod-Methode erzeugst Du l+k BITS, machst aus diesen BITS ein bigint x und setzt z := x mod R.

Je größer k ist, desto bessere Gleichverteilung erhältst Du. Also zB k=32: Abweichung von der Gleichverteilung ca 1 : 4 Milliarden.

Gruß Gammatester

[Z4ppy]

Und wie erzeugt man nun ein Zufallsbit? Und wie macht man daraus ein BigInt?!

MfG Z4ppy

[gammatester]

Zitat:

Zitat von Z4ppy

Und wie erzeugt man nun ein Zufallsbit? Und wie macht man daraus ein BigInt?!

Siehe Beitrag #14. Im übrigen kann man das ganz natürlich besser und mit Beweisen nachlesen, z.B. in Kapitel 9.2: Generating a random number from a given interval von Victor Shoup's Buch: A Computational Introduction to Number Theory and Algebra (Version 2) als PDF erhältlich auf http://shoup.net/ntb.

Wenn Du konkreten Code sehen willst, kannst Du ihn in meinem MPArith-Archiv (gleiche URL wie Beitrag #12) finden, ich werde mir jedenfalls keinen Code für die im Beitrag #1 genannte bigint-Klasse antun.

Gruß Gammatester

[Z4ppy]

Hmm, mir is grad noch ne ganz einfache methode eingefallen :D
Man generiert quasi einfach einen Zufallsstring aus Ziffern... Man muss die Zufallszahl natürlich in einer Variable zwischenspeichern, um sicher zu gehen, dass die Zahl mit Zufügen der Ziffer net grösser wird, als R... Am Schluss kann man den String ja dann einfach in nen BigInt umwandeln...

Werde das morgen mal testen, müsste aber eigentlich funktionieren...

MfG Z4ppy

[gammatester]

Zitat:

Zitat von Z4ppy

Hmm, mir is grad noch ne ganz einfache methode eingefallen :D
Man generiert quasi einfach einen Zufallsstring aus Ziffern... Man muss die Zufallszahl natürlich in einer Variable zwischenspeichern, um sicher zu gehen, dass die Zahl mit Zufügen der Ziffer net grösser wird, als R... Am Schluss kann man den String ja dann einfach in nen BigInt umwandeln...

Werde das morgen mal testen, müsste aber eigentlich funktionieren...

MfG Z4ppy

Wenn Du Ziffern durch Bits ersetzt, ist es doch genau das, was ich seit Tagen sage. Ziffern ist hier ein etwas unklares Konzept: Sind es Binärziffern, Dezimalziffern oder die Cardinals/Longword des bigint arrays? Wenn Du die Bits oder Arrayteile meinst, ist es wiederum genau das, was ich in #14 geschrieben habe (hier werden die Bits in einem Rutsch erzeugt und in das bigint-Array geschrieben):

Zitat:

Welche Funktionen Du verwenden kannst, hängt von den biginst ab. Wenn's ein array of cardinal ist, etwa isaac_read(ctx, @DeinArray, length(DeinArray)*sizeof(cardinal))

Gammatester

[Z4ppy]

Ich dachte eigentlich an Dezimalziffern ;) Also str:=str+inttostr(RandomRange(0,9)); wobei die erste Ziffer keine 0 sein sollte...

MfG Z4ppy

PS.: KP, ob die Syntax da oben jetz stimmt, sollte aber scho richtig sein... Und den String kann man dann ja mit TBigInt.Create(str); umwandeln...

[gammatester]

Zitat:

Zitat von Z4ppy

Ich dachte eigentlich an Dezimalziffern ;) Also str:=str+inttostr(RandomRange(0,9)); wobei die erste Ziffer keine 0 sein sollte...

MfG Z4ppy

PS.: KP, ob die Syntax da oben jetz stimmt, sollte aber scho richtig sein... Und den String kann man dann ja mit TBigInt.Create(str); umwandeln...

Dann wirst aus zwei Gründen aber viel Freude haben :wink:

1. Sind wir wieder beim Thema, daß RandomRange für kryptographische Anwendungen viel zu unsicher ist.

2. Wenn Du wirklich 20000-stellige Primzahlen mit der Methode erzeugen willst (das sind mehr als 66000 Bits, wenn "Stelle" wieder Dezimal bedeutet), wirst Du viel Zeit für andere Sachen haben. Versuch's erstmal mit 2048 Bits oder 1000 Dezimalstellen.

Auf jedenfall ist es besser mit den Arrayelementen zu arbeiten. Schau mal in das Testprogram der von Dir benutzten Klasse aus #1, dort wird genau das gemacht:

Delphi-Quellcode:

  p := TBigInt.Create(0);
  for i:=0 to CRYPTO_DIGITS do
    p.Digit[i] := random($FFFFFFFF);
  p.Digit[0] := p.Digit[0] or 1;

Jetzt brauchtst Du eigentlich nur noch random durch was kryptographisch Besseres zu ersetzen, zB mit dem ISAAC:

Delphi-Quellcode:

  p := TBigInt.Create(0);
  for i:=0 to CRYPTO_DIGITS do begin
    isaac_next(ctx);
    p.Digit[i] := LongWord(ctx.nextres);
  end;
  p.Digit[0] := p.Digit[0] or 1;

Gruß Gammatester

[Z4ppy]

Ich glaub, du hast mich net verstanden ;) Ich HABE Primzahlen bis 20k Stellen und will nun eine beliebige (natürliche) Zahl mit 1<x<p erzeugen, wobei p die 20k-stellige Zahl ist. Ich rede hier übrigens immer von Dezimalstellen...

Das mitm ISAAC werd ich mir nachher nochma ansehen ;)

MfG Z4ppy