Exponentieren und dann Modulo: große Zahlen

[himitsu]

leider erst ab D2006

> anderer Thread siehe Beitrag #15

[gammatester]

Zitat von himitsu:

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

Division kann man über 'ne Umkerung des Multiplikation regeln ... mach ich nicht anders (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 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
(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

[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 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 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
(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!

[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;