Exponentieren und dann Modulo: große Zahlen

[himitsu]

leider erst ab D2006

> anderer Thread siehe Beitrag #15

[gammatester]

Zitat:

Zitat von himitsu

Zitat:

Zitat von gammatester

Das ist natürlich gerade für RSA völlig ungeeignet, da die wichtigste Routine, um die es in diesem Thread ja geht, nämlich eine ExpMod gänzlich fehlt.

na gut, dieses könnte man sich da notfalls noch nachrüsten.

@himitsu: ich meinte nicht Deine Routine, sondern das VLI.PAS. Da gibt's noch nicht mal eine Divisionsroutine.

Wenn Ihr also schon nicht die DEC-Routine nehmen wollt, empfehle ich selbstverständlich meine MPArith. Im Archiv ist eine RSA-Unit mit Padding etc. ZZ arbeitete ich an einem RSA-Update, daß via CRT ca. 4mal schneller ist.

Gruß Gammatester

[himitsu]

@gammatester:
ich meinte da ja auch das VLI :angel2:

Division kann man über 'ne Umkerung des Multiplikation regeln ... mach ich nicht anders :stupid: (weils so schön einfach ist)

Modulo über 'ne Division+Multiplication+Subtraktion

Multiplicaion ist ja auch nur 'ne Mehrfache Addition



im Grunde führe ich alles auf eine Addition zurück.


abgesehn, daß VLI dank der dezimalen Operationen in einem dualen System wohl etwas langsamer sein dürfte.

[gammatester]

Zitat:

Zitat von himitsu

@gammatester:
ich meinte da ja auch das VLI :angel2:

Division kann man über 'ne Umkerung des Multiplikation regeln ... mach ich nicht anders :stupid: (weils so schön einfach ist)

Modulo über 'ne Division+Multiplication+Subtraktion

Multiplicaion ist ja auch nur 'ne Mehrfache Addition



im Grunde führe ich alles auf eine Addition zurück.


abgesehn, daß VLI dank der dezimalen Operationen in einem dualen System wohl etwas langsamer sein dürfte.

Das ist theoretisch vielleicht OK, aber Performamce wirst Du damit nicht erreichen. Besonders

Zitat:

Modulo über 'ne Division+Multiplication+Subtraktion

dürfte eine mittlere Katastrophe werden, wenn mod beim modularem Potenzieren benutzt wird: Dann ist selbst meist eine normale mod-Funktion zu langsam und man benutzt Montgomery- oder Barret-Reduktion für allgemeine Zahlen; für spezielle Moduli kann man noch schneller Reduktionsverfahren benutzen.

Gruß Gammatester

[tuxianer]

ich habs jetzt in delphi2007 probiert:

Delphi-Quellcode:

[DCC Fehler] BigInt.pas(175): E2393 Ungültige Operatordeklaration
[DCC Fehler] BigInt.pas(175): E2029 Bezeichner erwartet, aber 'CONST' gefunden
[DCC Fehler] BigInt.pas(175): E2086 Typ 'TBigInt' ist nicht vollständig definiert
[DCC Fehler] BigInt.pas(175): E2086 Typ 'TBigInt' ist nicht vollständig definiert
[DCC Fehler] BigInt.pas(177): E2029 ; erwartet, aber Bezeichner 'Operator' gefunden
[DCC Fehler] BigInt.pas(177): E2029 Ausdruck erwartet, aber 'CONST' gefunden
[DCC Fehler] BigInt.pas(177): E2086 Typ 'TBigInt' ist nicht vollständig definiert
[DCC Fehler] BigInt.pas(177): E2029 '=' erwartet, aber ')' gefunden
[DCC Fehler] BigInt.pas(178): E2029 ; erwartet, aber Bezeichner 'Operator' gefunden
[DCC Fehler] BigInt.pas(178): E2029 Ausdruck erwartet, aber 'CONST' gefunden
[DCC Fehler] BigInt.pas(178): E2004 Bezeichner redefiniert: 'Oper1'
[DCC Fehler] BigInt.pas(178): E2004 Bezeichner redefiniert: 'Oper2'
[DCC Fehler] BigInt.pas(178): E2086 Typ 'TBigInt' ist nicht vollständig definiert
[DCC Fehler] BigInt.pas(179): E2029 ; erwartet, aber Bezeichner 'Private' gefunden
[DCC Fehler] BigInt.pas(1334): E2393 Ungültige Operatordeklaration
[DCC Fehler] BigInt.pas(1334): E2029 '=' erwartet, aber ')' gefunden
[DCC Fehler] BigInt.pas(1335): E2029 Ausdruck erwartet, aber 'BEGIN' gefunden
[DCC Fehler] BigInt.pas(1336): E2003 Undefinierter Bezeichner: 'Result'
[DCC Fehler] BigInt.pas(1337): E2066 Operator oder Semikolon fehlt
[DCC Fehler] BigInt.pas(1340): E2393 Ungültige Operatordeklaration
[DCC Fehler] BigInt.pas(1340): E2029 '=' erwartet, aber ';' gefunden
[DCC Fehler] BigInt.pas(1340): E2029 '=' erwartet, aber ')' gefunden
[DCC Fehler] BigInt.pas(1341): E2066 Operator oder Semikolon fehlt
[DCC Fehler] BigInt.pas(1342): E2003 Undefinierter Bezeichner: 'Result'
[DCC Fehler] BigInt.pas(1343): E2066 Operator oder Semikolon fehlt
[DCC Fehler] BigInt.pas(1346): E2393 Ungültige Operatordeklaration
[DCC Fehler] BigInt.pas(1346): E2029 '=' erwartet, aber ';' gefunden
[DCC Fehler] BigInt.pas(1346): E2029 '=' erwartet, aber ')' gefunden
[DCC Fehler] BigInt.pas(1347): E2066 Operator oder Semikolon fehlt
[DCC Fehler] BigInt.pas(1348): E2003 Undefinierter Bezeichner: 'Result'
[DCC Fehler] BigInt.pas(1349): E2066 Operator oder Semikolon fehlt
[DCC Fehler] BigInt.pas(2694): E2015 Operator ist auf diesen Operandentyp nicht anwendbar
[DCC Fehler] BigInt.pas(2694): E2015 Operator ist auf diesen Operandentyp nicht anwendbar
[DCC Fehler] Unit1.pas(7): F2063 Verwendete Unit 'BigInt.pas' kann nicht compiliert werden

[himitsu]

da es mit Zeile 175 anfängt

ersetzt mal den Namen BitwiseNot durch LogicalNot :gruebel:
(Zeilen 175 und 1334)

stimmt zwar von der Logik her nicht ganz, aber von der Funktion her sollte es damit auch gehn.
(Delphi unterscheidet ja angeblich nicht zwischen binären und logischen Operatoren :? )

nja, und dann mal sehen welche der Folgefehler noch übrig bleiben :stupid:

[tuxianer]

geht leider noch nicht:

Delphi-Quellcode:

[DCC Fehler] BigInt.pas(177): E2393 Ungültige Operatordeklaration
[DCC Fehler] BigInt.pas(177): E2029 Bezeichner erwartet, aber 'CONST' gefunden
[DCC Fehler] BigInt.pas(177): E2086 Typ 'TBigInt' ist nicht vollständig definiert
[DCC Fehler] BigInt.pas(177): E2029 '=' erwartet, aber ')' gefunden
[DCC Fehler] BigInt.pas(178): E2029 ; erwartet, aber Bezeichner 'Operator' gefunden
[DCC Fehler] BigInt.pas(178): E2029 Ausdruck erwartet, aber 'CONST' gefunden
[DCC Fehler] BigInt.pas(178): E2004 Bezeichner redefiniert: 'Oper1'
[DCC Fehler] BigInt.pas(178): E2004 Bezeichner redefiniert: 'Oper2'
[DCC Fehler] BigInt.pas(178): E2086 Typ 'TBigInt' ist nicht vollständig definiert
[DCC Fehler] BigInt.pas(179): E2029 ; erwartet, aber Bezeichner 'Private' gefunden
[DCC Fehler] BigInt.pas(1340): E2393 Ungültige Operatordeklaration
[DCC Fehler] BigInt.pas(1340): E2029 '=' erwartet, aber ';' gefunden
[DCC Fehler] BigInt.pas(1340): E2029 '=' erwartet, aber ')' gefunden
[DCC Fehler] BigInt.pas(1341): E2066 Operator oder Semikolon fehlt
[DCC Fehler] BigInt.pas(1342): E2003 Undefinierter Bezeichner: 'Result'
[DCC Fehler] BigInt.pas(1343): E2066 Operator oder Semikolon fehlt
[DCC Fehler] BigInt.pas(1346): E2393 Ungültige Operatordeklaration
[DCC Fehler] BigInt.pas(1346): E2029 '=' erwartet, aber ';' gefunden
[DCC Fehler] BigInt.pas(1346): E2029 '=' erwartet, aber ')' gefunden
[DCC Fehler] BigInt.pas(1347): E2066 Operator oder Semikolon fehlt
[DCC Fehler] BigInt.pas(1348): E2003 Undefinierter Bezeichner: 'Result'
[DCC Fehler] BigInt.pas(1349): E2066 Operator oder Semikolon fehlt
[DCC Fehler] BigInt.pas(2694): E2015 Operator ist auf diesen Operandentyp nicht anwendbar
[DCC Fehler] BigInt.pas(2694): E2015 Operator ist auf diesen Operandentyp nicht anwendbar
[DCC Fehler] Unit1.pas(7): F2063 Verwendete Unit 'BigInt.pas' kann nicht compiliert werden

[himitsu]

Zitat:

Zitat von tuxianer

bringt leider auch nix:

doch schon ... der Fehler in Zeile 175 ist ja behoben ... nur gib es noch andere ... hab leider kein D2007 zum Testen.

Zitat:

Zitat von tuxianer

[DCC Fehler] BigInt.pas(175): E2065 Ungenügende Forward- oder External-Deklaration: 'TBigInt.LogicalNot'

hast aber in Zeile 1334 das BitwiseNot noch nicht durch LogicalNot ersetzt :angel2:
(Deklaraion und Funktion müssen ja umbenannt werden)


Zeile 177+178 = ShiftRight und ShiftLeft
ich dachte zwar die haben es schon mit dem Updat behoben,
aber vielleicht heißt das bei dir RightShift und LeftShift (umgekerte Reinfolge)
ShiftRight > RightShift
ShiftLeft > LeftShift

[tuxianer]

ok es kommen jetztkeine fehler mehr nach all diesen Korrekturen! :dancer:

[tuxianer]

noch was:

Delphi-Quellcode:

Function tF_Haupt.mod_exp(Basis, Exponent, Modulo: TBigInt): TBigInt;
  Begin
    Result := 1;
    While Exponent > 0 do Begin
      If Exponent.Data and $1 <> 0 Then
        Result := (Result * Basis) mod Modulo;
      Basis := (Basis * Basis) mod Modulo;
      Exponent := Exponent div 2;
    End;
  End;

Delphi-Quellcode:

[DCC Fehler] Unit1.pas(176): E2015 Operator ist auf diesen Operandentyp nicht anwendbar
[DCC Warnung] Unit1.pas(176): W1023 Vorzeichenbehaftete und -lose Typen werden verglichen - beide Operanden werden erweitert

Diese jedoch geht:

Delphi-Quellcode:

Function tF_Haupt.mod_exp(Basis, Exponent, Modulo: TBigInt): TBigInt;
  Begin
    Result := 1;
    If not Exponent.isNegative Then
      While not Exponent.isZero do Begin
        If Exponent.Data[0] and $1 <> 0 Then Begin
          Result.Multiply(Basis);
          Result.Modulus(Modulo);
        End;
        Basis.Multiply(Basis);
        Basis.Modulus(Modulo);
        Exponent.bShR(1);
      End;
  End;

meine mit Bigint geht auch:

Delphi-Quellcode:

function tF_Haupt.mod_exp(basis,exponent,modulo:TBigInt):TBigInt;
var e:TBigInt;
begin
  e:=1;
  while (exponent>0) do begin
    if (exponent mod 2 > 0) then e:=(e*basis) mod modulo;
    basis:=(basis*basis) mod modulo;
    exponent:=exponent div 2;
  end;
  result:=e;
end;

[himitsu]

Delphi-Quellcode:

Function tF_Haupt.mod_exp(Const Basis, Exponent, Modulo: TBigInt): TBigInt;
  Begin
    Result := Basis;
    Result.ExpMod(Exponent, Modulo);
  End;

Zitat:

[DCC Fehler] Unit1.pas(176): E2015 Operator ist auf diesen Operandentyp nicht anwendbar

welches ist denn die Zeile 176?
[add]
hab 'nen verdacht :stupid:

Code:

If Exponent.Data[color=#ff0000][0][/color] and $1 <> 0 Then

[/add]

[tuxianer]

naja es lief ja jetzt nur stützt es bei primzahlen >>20.000 ab und hängt sich auch beim entschlüsseln auf...

[himitsu]

hast du da mal ein Testprogramm für mich?

[Macci]

Übrigens kommt bei der Rechnung
666^58613

folgende Zahl raus:


19723971160619624455773050692305579086788641379042 79
64198191449046292583386241568038339803081818...(16 5395 Ziffern).

und das ist
eine Septenvigintmilliaquingentduooktogintillion neunhundertzweiundsiebzig Septenvigintmilliaquingentunoktogintilliarden dreihundertsiebenundneunzig Septenvigintmilliaquingentunoktogintillionen einhundertsechzehn Septenvigintmilliaquingentoktogintilliarden einundsechzig Septenvigintmilliaquingentoktogintillionen neunhundertzweiundsechzig Septenvigintmilliaquingentnovemseptuagintilliarden vierhundertfünfundvierzig Septenvigintmilliaquingentnovemseptuagintillionen fünfhundertsiebenundsiebzig Septenvigintmilliaquingentoktoseptuagintilliarden dreihundertfünf Septenvigintmilliaquingentoktoseptuagintillionen neunundsechzig Septenvigintmilliaquingentseptenseptuagintilliarde n zweihundertdreißig Septenvigintmilliaquingentseptenseptuagintillionen ....

Wer den vollständigen Namen will (der übrigens über 3 MB groß ist), soll mir eine PM schicken ;-)

wollte ich nur mal anmerken *g*,
Macci