Seite 1 von 3
Mal wieder was über BigInt
Verfasst: 22.05.2014 16:40
von 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
Re: Mal wieder was über BigInt
Verfasst: 22.05.2014 21:49
von 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)
(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.
Re: Mal wieder was über BigInt
Verfasst: 23.05.2014 09:01
von 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.
Re: Mal wieder was über BigInt
Verfasst: 23.05.2014 11:13
von 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)
Re: Mal wieder was über BigInt
Verfasst: 23.05.2014 17:01
von 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.
Re: Mal wieder was über BigInt
Verfasst: 23.05.2014 17:04
von Sauer-RAM
Vielen Dank *.*... Ich fang gleich heute oder morgen an mit dem RSA-Modul.
Re: Mal wieder was über BigInt
Verfasst: 23.05.2014 18:14
von 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)
Re: Mal wieder was über BigInt
Verfasst: 23.05.2014 18:38
von NicTheQuick
Nutze "EnableExplicit" und du wirst deinen Fehler finden.
Re: Mal wieder was über BigInt
Verfasst: 23.05.2014 18:46
von 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
Re: Mal wieder was über BigInt
Verfasst: 23.05.2014 20:28
von 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)