HugeInt performance degradation

[kazalex]

flcHugeInt has serious performance degradation in comparison with version 4. RSA 4096-bit keys generation take about 30 sec. using cHugeInt (version 4) and more than 3 minutes with flcHugeInt (current version). Generation 8192-bit keys take about 3 minutes using cHugeInt (version 4) and more then 3 hours with flcHugeInt (current version). In my test i used equal entropy source for both versions.

[butlerdj]

Which compiler and target are you using?

[kazalex]

Delphi 10.4.2, Win32 Release, Win64 Release, Linux64 Release

[butlerdj]

For reference, benchmarks using 64 bit / 32 bit and using Release / Debug settings using the current code base:

 KeySize      Release64        Debug64          Release32      Debug32
 --------     ---------        -------          ---------      -------
 1024 bit     1.5s             1.5s             2.8s           3.1s
 1536 bit     4.0s             4.1s             9.2s           9.5s
 2048 bit     21s              21s              54s            57s
 3072 bit     39s              41s              121s           125s
 4096 bit     102s             105s             331s           342s
 8192 bit     72m              72m              282m           -

I will update this issue if any significant optimisations are made.

[sztdevel]

I replaced HugeWordPowerAndMod() internals with https://github.com/rvelthuis/DelphiBigNumbers and got RSA decription 5.6 times faster. This is a very dirty hack, but I think, it makes sense to give it a try and do it better, either by joining the two libraries more tightly, or incorporating the algorithm from BigIntegers. The most surprising is that the internal data representation is very similar, it is enough to move bytes between buffers.

procedure HugeWordPowerAndMod(var Res: HugeWord; const A, E, M: HugeWord);

{$IFDEF USE_VELTHUIS} //* Velthuis.BigInteger
  function FromHugeWord(const A: HugeWord): Velthuis.BigIntegers.BigInteger;
  begin
    Result.Create(A.Data, A.Used * HugeWordElementSize);
  end;
  function ToHugeWord(const A: Velthuis.BigIntegers.BigInteger): HugeWord;
  begin
    HugeWordInit(Result);
    HugeWordSetSize(Result, A.Size);
    Move(A.Data^, Result.Data^, A.Size * HugeWordElementSize); //* Binary compatible internal layout
  end;
var
  LA, LE, LM, LI: Velthuis.BigIntegers.BigInteger;
begin
  LA := FromHugeWord(A);
  LE := FromHugeWord(E);
  LM := FromHugeWord(M);
  LI := LI.ModPow(LA, LE, LM);
  Res := ToHugeWord(LI);

{$ELSE ~USE_VELTHUIS} //* Original code
var P, T, Y, F{, Q} : HugeWord;
begin
  HugeWordInitOne(P);                                  // P = 1
  HugeWordInit(T);
  HugeWordInitHugeWord(Y, A);                          // Y = A
  HugeWordInitHugeWord(F, E);                          // F = E
  //HugeWordInit(Q);
  try
    while not HugeWordIsZero(F) do
      begin
        if HugeWordIsOdd(F) then
          begin
            HugeWordMultiply_Long_NN_Unsafe(T, P, Y);  // T = P * Y             HugeWordMultiply(T, P, Y)
            HugeWordNormalise(T);
            HugeWordMod_Unsafe(T, M, P);
            //HugeWordDivide_RR_Unsafe(T, M, Q, P);      // P = (P * Y) mod M
          end;
        HugeWordMultiply_Long_NN_Unsafe(T, Y, Y);      // T = Y * Y             HugeWordSqr(T, Y)
        HugeWordNormalise(T);
        HugeWordMod_Unsafe(T, M, Y);
        //HugeWordDivide_RR_Unsafe(T, M, Q, Y);          // Y = (Y * Y) mod M
        HugeWordShr1(F);                               // F = F / 2
        HugeWordNormalise(F);
      end;
    HugeWordAssign(Res, P);
  finally
    //HugeWordFinalise(Q);
    HugeWordFinalise(F);
    HugeWordFinalise(Y);
    HugeWordFinalise(T);
    HugeWordFinalise(P);
  end;
{$ENDIF ~USE_VELTHUIS}
end;