Mal wieder was über BigInt

[Sauer-RAM]

Hi mal wieder.
Nun bin ich auch an dem Punkt, an dem ich mal n BigInt brauchen könnte. (Für RSA)

Mir fallen dazu zwei Lösungsansätze ein: 1. Das ganze mit Arrays oder Listen zu realisieren oder 2. Die Zahlen einfach in einem Buffer zu halten.

Ich habe schon gelesen dass Stargate da mal was gemacht hat (habe es aber nicht vollständig angeschaut wie ich zugeben muss) und er löst die Sache ja scheinbar durch ne Struktur mit einem Array.
Ich habe mir wie gesagt den Code nicht ganz angeschaut, aber aus dem Bauch heraus würde ich sagen, dass es doch eigentlich (Wenn man wie ich nur Ganzzahle braucht) schneller sein müsste, das Berechnen direkt durch logische Operationen mit den Bits im RAM zu realisieren oder gehe ich da falsch in der Annahme?
Und: Könnte man da nicht mit InlineASM noch ein wenig viel an der Performance drehen? Ein Poke-/PeekBit() gibt es ja leider nicht.

Wie schätzt ihr die Lage bezüglich des Aufwandes ein? Ich bin gerade am überlegen, ob ich doch lieber eine DLL Lib oder sonstiges nehmen sollte, habe damit aber noch nie gearbeitet und daher auch keine Ahnung. Hier gibts ja ein paar Threads über RSA, aber immer höre ich gegen Ende, dass es da nicht wirklich eine Fertige Crypto.dll gibt, sondern man da mit Informagic noch ein wenig rumzaubern muss.

Viele Grüße,
Sauer-RAM

[STARGÅTE]

Hallo Sauer-RAM,

damit eine Big-Integers Lib schnell ist muss sie komplett in ASM geschrieben werden.
An diesem Punkt bin ich inzwischen angekommen und habe auch schon ein Include das mit Hochleistungsprogrammen messen kann.
Da dieses Include inzwischen fast 2 Jahre Entwicklungszeit hatte (natürlich mit Pausen), möchte ich ungern den Source freigeben.
Aber ich habe eine DLL erstellt mit PB-Include, dass es ermöglicht die Zahlen direkt in PB zu nutzen:

Code: Alles auswählen

XIncludeFile "UnlimitedIntegerArithmetic.dll.pbi"

Define.Z A, B, C

; Eingabe von Zahlen über Quads oder Strings:
Z_Number(A, "1000000000000000000000000000001")
Z_Set(B, 30)

; Ausgabe von Zahlen durch Strings oder Quads:
Debug Z_String(A)
Debug Z_Get(B)

; Rechnen mit Zahlen:
Z_Add(A, B)
Debug Z_String(A)

Z_Multiply(A, B)
Debug Z_String(A)

Z_Power(A, B)
Debug Z_String(A)

Z_Factorial(B)
Debug Z_String(B)

Z_Modulo(A, B)
Debug Z_String(A)

Z_GreatestCommonDivisor(C, A, B)
Debug Z_String(C)

Hier war ein veralteter Link
(Danke an dieser Stelle an Helle und CSHW89 die dazu beigetragen haben, das der ASM Code sehr schnell ist)

Wie du siehst, kann man die Zahlen normal in PB als Typ: Z definieren
und dann mti den Proceduren für die unlimitierten Ganzzahlen nutzen.

Da die Zahlen als PB-Struktur definiert werden, werden die auch automatisch in Procedure wieder freigegeben usw.

Da immer mehr anfragen zu Big-Integers kommen, üpberlege ich ob ich es vielleich doch offiziell veröffentliche.

Ansonsten bei Fragen einfach fragen.
Ich kann die DLL auch als x64, oder Thread-Safe anbieten, dann arbeitet die Multiplikation bei sehr sehr großen Zahlen mit Threads.

[Sauer-RAM]

Ein RIESENLOB an dich Stargate!!! Vielen vielen Dank. Das erstpart mir einen haufen Arbeit.
Und wenn es dir wirklich nichts ausmacht, würde ich mich sehr über eine x64 Version der DLL freuen \^-^/.

Wenn ich das RSA-Modul fertig hab, mach ich mit deiner Erlaubnis auch eine DLL davon und poste sie dann hier rein, da da ja scheinbar auch von mancher Stelle schon interesse gezeigt wurde.

[STARGÅTE]

Noch ein Hinweis:

Sachen wie 230911^1721 Mod 263713 könnten mit Power() und Modulo() berechnet werden.
Das geht auch recht fix, allerdings wäre es natürlich sinvoller die Eigenschaft von PowerMod zu nutzen:

(A*B) Mod C = (A*(B Mod C)) Mod C

Diese Funktion würde ich noch nachreichen ...

... allerdings kannst du für solche Sachen auch die Quads von PB nutzen, solange die Basis in eine Long passt.

Code: Alles auswählen

Procedure.q PowerMod(Base.q, Exponent.q, Modulo.q)
  
  Protected Result.q = 1
  
  Base = Base % Modulo
  While Exponent > 0
    If Exponent & 1
      Result = (Result * Base) % Modulo
    EndIf
    Exponent >> 1
    Base = (Base * Base) % Modulo
  Wend    
  
  ProcedureReturn Result
  
EndProcedure

Debug PowerMod(230911, 1721, 263713)

[STARGÅTE]

Bitte schön:
.../UnlimitedIntegerArithmetic.zip
Achtung: Auf Grund eines Bugs in der DLL, musste der Download entfernt werden!

32Bit/64Bit und Ascii/Unicode

PowerModulo ist nun auch drin.
Leider gibs noch keine Hilfe, da es wie gesagt nicht offiziell veröffentlicht ist.

[Sauer-RAM]

Vielen Dank *.*... Ich fang gleich heute oder morgen an mit dem RSA-Modul.

[Sauer-RAM]

Jep, jetzt kommt eine Anfängerfrage... Warum geht das nicht, und kann man das in der Richtung in etwa hinbiegen?

Code: Alles auswählen

XIncludeFile "UnlimitedIntegerArithmetic.dll.pbi"

Define Number.Z
Procedure CreateNumber()
  If Not OpenCryptRandom()
    ProcedureReturn 0
  EndIf
  
  For n = 1 To 10
    NumberString.s + Str(CryptRandom(10))
  Next
  CloseCryptRandom()
  Z_Number(Number.Z,NumberString)
  ProcedureReturn Number
EndProcedure

Number = CreateNumber()
Debug Z_String(Number)

[NicTheQuick]

Nutze "EnableExplicit" und du wirst deinen Fehler finden.

[Sauer-RAM]

Code: Alles auswählen

XIncludeFile "UnlimitedIntegerArithmetic.dll.pbi"
EnableExplicit
Define Number.Z
Procedure CreateNumber()
  Protected n
  Protected NumberString.s
  Protected Number.Z
  If Not OpenCryptRandom()
    ProcedureReturn 0
  EndIf
  
  For n = 1 To 10
    NumberString.s + Str(CryptRandom(10))
  Next
  Debug NumberString
  CloseCryptRandom()
  Z_Number(Number.Z,NumberString)
  Debug Number
  ProcedureReturn Number
EndProcedure

Number = CreateNumber()
Debug Z_String(Number)

Error 404: Bug not Found

[STARGÅTE]

Der Typ "Z" ist in PB immer noch eine Struktur und kein normler Rückgabe wert.
Du kannst eine Zahl also nicht als Value über ProcedureReturn zurückgeben, sondern nur als Pointer

Code: Alles auswählen

XIncludeFile "UnlimitedIntegerArithmetic.dll.pbi"
EnableExplicit

Define Number.Z

Procedure CreateNumber(*Number.Z)
  Protected n
  Protected NumberString.s
  
  If Not OpenCryptRandom()
    ProcedureReturn 0
  EndIf
  
  For n = 1 To 10
    NumberString.s + Str(CryptRandom(10))
  Next
  Debug NumberString
  CloseCryptRandom()
  Z_Number(*Number,NumberString)
  ProcedureReturn *Number
EndProcedure

CreateNumber(Number)

Debug Z_String(Number)