[VB6] hoe kan dit sneller gedaan worden?

[dudek]

Ik ben bezig met een programmaatje in VB om tekst te coderen (en te encoderen) mbv het rsa algoritme.
Het is voor mijn profielwerkstuk en ik ben tot het volgende gekomen

code:

Private Function ToAscii(strInput As String) As Integer()

Dim i As Long, arrOut() As Integer
ReDim arrOut(Len(strInput) - 1)

For i = 1 To Len(strInput)
'Zet elk chacter om
arrOut(i - 1) = Asc(Mid(strInput, i, 1))
Next

ToAscii = arrOut
End Function
Function DoubleMod(ByVal c As Double, n As Integer) As Double
'coded by Xenophage
Dim aa As Integer, bb As Integer

    Do While c > n
      If c > (100 * n) Then c = c - (100 * n)
      If c > (10 * n) Then c = c - (10 * n)
      If c > n Then c = c - n
      DoEvents
    Loop
      
    DoubleMod = c
    
End Function

Private Sub Command1_Click()
Dim p As Integer, q As Integer, n As Integer, a As Integer
Dim e As Integer, d As Integer, c As Double, m As Integer
Dim c1 As Integer, strOutput As String, arrGait() As Integer


'alle waardes voor het RSA algoritme worden vastgelegd
p = 13
q = 17
n = p * q
a = (p - 1) * (q - 1)
e = 5
d = 77
'de benodigde velden worden geleegd
List1.Clear
Text2.Text = ""
'arrGait wordt gevuld met ascii codes van de letters van tekstvak 1
arrGait = ToAscii(Text1.Text)

'tekst 1 wordt gecodeerd
For i = 0 To Len(Text1.Text) - 1
'Label1.Caption = "letter: " & List3.List(i) 'hoort er nog niet bij
m = arrGait(i)
c = m ^ e
c1 = DoubleMod(c, n) 'de ciphertext wordt berekend
List1.AddItem (c1)
Text2.Text = Text2.Text & Chr$(List1.List(i)) 'de gecodeerde ascii codes worden omgezet en in het tekstvak gezet
Next i
End Sub

toelichting:
de eerste functie zet de string van tekstvak 1 om in ascii-code en zet alles in een array
de tweede functie berekent mod van m^e en n


voor lagere waardes van e gaat het codeerproces vrij snel, maar zogauw er grotere waardes voor e worden ingevoerd (waardoor m^e dus ontzettend groot wordt) gaat het echt verschrikkelijk langzaam.

Dat komt dus door de functie doublemod (die heb ik gekregen van Xenophage). Als ik gewoon m^e mod n deed kreeg ik een overflow, maar met die functie gaat het wel goed, alleen niet zo heel erg snel.

Wie kan mij vertellen wat ik hier aan kan doen om het sneller te laten werken?

[johnwoo]

Zijn er geen lekker kleine DLL's te vinden waarin een bikkel het zo efficient mogelijk heeft gedaan in hardcore assembly?

[Lister]

Voor de snelheid zou ik de DoEvents in ieder geval uit de loop slopen en volgens mij kan ie wel helemaal uit je functie.

En aa en bb declareer je maar gebruik je niet, het zal niet echt veel schelen maar die je kan je dan wel weglaten.

[mulder]

By the way, waarom een function, je geeft niet eens een result terug. Eventueel componenten die je update in je loop Visible = False maken, kan ook iets schelen.

[Lister]

code:

DoubleMod = c

en

code:

c1 = DoubleMod(c, n) 'de ciphertext wordt berekend

Hoezo geen resultaat teruggeven

[Verwijderd]

code:

Function DoubleMod(ByVal c As Double, n As Integer) As Double
'coded by Xenophage
    Dim n100 As Integer
    Dim n10 As Integer
    
    n100 = 100 * n
    n10 = 10 * n
    While c > n100: c = c - n100: Wend
    While c > n10:  c = c - n10: Wend
    If c > n Then c = c - n
   
    DoubleMod = c
End Function

van ~5.5sec naar ~250msec hier.. nog steeds niet al te best maarja goed genoeg naar mijn smaak.

[mbravenboer]

Heb je trouwens al getest waar de bottle-neck zit?

Misschien heeft dit zin:

code:

Do While c > n
      If c > (100 * n) Then c = c - (100 * n)
      If c > (10 * n) Then c = c - (10 * n)
      If c > n Then c = c - n
      DoEvents
    Loop

n verandert helemaal niet, dus waarom steeds 100 * n en 10 * n uitrekenen?

code:

int n100 = 100 * n
int n10  = 10  * n

Do While c > n
      If c > n100 Then c = c - n100
      If c > n10 Then c = c - n10
      If c > n Then c = c - n
    Loop

Verder kan je misschien nog iets doen met het zo vaak mogelijk aftrekken van de grootste keuze. Double berekeningen zijn duur. Dus:

code:

int n100 = 100 * n
int n101 = 101 * n

Do While c > n101
       c = c - n100
    Loop

int n10 = 10 * n
int n11 = 11 * n

Do While c > n11
       c = c - n10
    Loop

Do While c > n
       c = c - n
    Loop

Misschien dat je dit nog een klein beetje moet aanpassen (weet niet of het echt wel het goede doet, dus even goed testen!!), maar zoals je ziet wordt er veel minder gechecked en wordt er zo veel mogelijk de grote aftrekking gekozen. Het is een beetje te laat om nog in te zien of die 101 en 11 echt nodig zijn, maar ik vermoed van wel .

[Verwijderd]

Volgens mij klopte de uitkomst van m'n vorige niet.

code:

Function DoubleMod(ByVal c As Double, n As Integer) As Double
    Dim tn As Long
    tn = n: tn = tn * 1000000
    Do While c > n
      Do While c > tn: c = c - tn: Loop
      If tn > n Then
        tn = tn \ 10
      End If
    Loop
    DoubleMod = c
End Function

rete snel, en nog getest ook. 10000x aan te roepen in ~300msec

[mbravenboer]

Yarvieh: van ~5.5sec naar ~250msec hier.. nog steeds niet al te best maarja goed genoeg naar mijn smaak.

He! Ik was hetzelfde aan het doen .

[mbravenboer]

Yarvieh: rete snel, en nog getest ook. 10000x aan te roepen in ~300msec

Hum dat ziet er inderdaad nog beter uit .

[Verwijderd]

Op zondag 18 november 2001 02:22 schreef mbravenboer het volgende:
He! Ik was hetzelfde aan het doen .

Waar zijn OiSyn en curry eigenlijk? is er eindelijk weer wat te benchmarken zijn ze niet van de partij...

[.oisyn]

och, ik vind /14 niet zo interessant meer als voorheen...
(Misschien heeft dat iets met die splitsing te maken niet dat ik me interesseer in webscripting, maar ik heb toch het idee dat programming een beetje is uitgestorven sinds die splitsing )

Oh, en bovendien heb ik een natuurlijke afkeer tegen VB (dan vraag je je toch af wat ik in dit topic doe... om 5 uur 'snachts )

gelukkig komt er een nieuw forum waar ik me helemaal uit kan leven


Maar even over de topicstarter, je hebt het over coderen en weer encoderen. Ik hoop voor je werkstuk dat wat je hier hebt geschreven maar een tiepfout is, want coderen is in principe gelijk aan encoderen, en het andere wat je doet om het weer terug te krijgen heet decoderen
Niet bedoeld om je af te zeiken hoor, maar het staat zo lullig als het zo in je werkstuk belandt

[Verwijderd]

Om het echt snel te krijgen moet je niet eerst de hele machtsverheffing uitrekenen en daarna gaan modden.

Da's langzaam en je krijgt heel gauw een overflow (bij fatsoenlijk grote priems).

Je moet al modden tijdens het machten. Dit heet een powermod, en dit is een standaard operatie op de meeste cryptoprocessoren omdat dit héél veel voor komt.

[dudek]

Op zaterdag 17 november 2001 20:25 schreef Lister het volgende:
Voor de snelheid zou ik de DoEvents in ieder geval uit de loop slopen en volgens mij kan ie wel helemaal uit je functie.

voor die DoEvents hoort ook een '. Ik had em er in om VB niet te laten vastlopen tijdens het testen

quote by Oisyn

Maar even over de topicstarter, je hebt het over coderen en weer encoderen. Ik hoop voor je werkstuk dat wat je hier hebt geschreven maar een tiepfout is, want coderen is in principe gelijk aan encoderen, en het andere wat je doet om het weer terug te krijgen heet decoderen
Niet bedoeld om je af te zeiken hoor, maar het staat zo lullig als het zo in je werkstuk belandt

typefout ja
natuurlijk is het coderen en decoderen...

En die functie van Yarvieh werkt heel snel, zolang je maar kleine waardes voor e gebruikt..

[Verwijderd]

Ik spreek geen woord VB dus hier is mijn mod functie in Delphi:

code:

function MijnMod(a, n: longint): longint;
var n2: longint;
    temp: longint;
begin
  n2 := n;
  temp := Floor(a/2);
  while n2 <= temp do n2 := 2 * n2;

  while n2 <= a do
  begin
    a := a - n2;
    while (n2 > a) and (n2 > n) do n2 := n2 div 2;
  end;

  result := a;
end;

Misschien dat iemand met een talenknobbel dit even kan vertalen naar VB.
BTW, ik gebruik een div, en die zul je wel niet hebben in VB (anders vroeg je niet om deze mod), maar dat is alleen om een typeconflict uit de weg te gaan, je kunt in principe die div door een / vervangen, want het is gegarandeerd een deling zonder rest, alleen begreep mijn compiler dat niet
Volgens mij is dit best snel, iig zou het net zo goed moeten werken voor hele grote a en n als voor kleine.

edit:
servicepack 1 gereleased, en je weet het: "If it doesn't have a servicepack, we don't use it."

[Verwijderd]

O, nog één ding, in een Double (32 bit signed?) kun jij nooit een n kwijt die enige bescherming biedt...

[.oisyn]

een Double is een 64 bits floating point type, maar je hebt idd wel gelijk, dan nog steeds past er geen goede n in

[Verwijderd]

Ik weet niet of iemand deze thread nog leest, maar hier is een functie die je zooitje echt gaat versnellen. Het is de PowerMod functie waar ik het een paar berichten hiervoor over had. Dit algoritme is een door mij aangepaste versie van een algoritme uit: "Introduction to Algoritms, 2nd ed." van Cormen, Leiserson, Rivest en Stein (GE-WEL-DIG boek). Voor de versie in dit boek heb je de bitrepresentatie van b nodig, en het lijkt me dat bitoperaties in VB niet echt makkelijk zullen zijn.

Omdat ik nogsteeds geen VB spreek en het ook niet wil leren, is hier de code in Delphi.

code:

Temporarily out of order

Behalve snel is deze code ook veel flexibeler dan je oude manier, omdat je hiermee veel minder snel een overflow zult krijgen. Deze functie berekent:

a^b mod n

en het zal goed gaan zolang a*a en n*n in een Double passen, ongeacht b dus! Voor de mods in dit algoritme zou ik een van de algorimes die hierboven staan nemen (ik vind die van mij de beste ) en de div is eigenlijk weer een gewone / omdat het altijd een deling zal zijn die geen rest oplevert.

[Verwijderd]

bump

[Verwijderd]

Dit is de code waar ik het 2 posts hierboven over heb. Er zaten eerst wat foutjes in die code, maar ik mocht de gebugfixte versie niet meer plaatsen want dat mag maar tot 24 uur na het posten van het bericht.

code:

function PowerMod(a, b, n: int64): int64;
var d: int64;
    e: int64;
begin
  d := a;
  e := 1;

  while b > 1 do
  begin
    if (b mod 2) = 1 then
    begin
    e := (d * e) mod n;
    b := b - 1;
    end;
    d := (d * d) mod n;
    b := b div 2;
  end;

  result := (d * e) mod n;
end;

[dudek]

Op dinsdag 20 november 2001 20:33 schreef Xalista het volgende:
Dit is de code waar ik het 2 posts hierboven over heb. Er zaten eerst wat foutjes in die code, maar ik mocht de gebugfixte versie niet meer plaatsen want dat mag maar tot 24 uur na het posten van het bericht.

code:

function PowerMod(a, b, n: int64): int64;
var d: int64;
    e: int64;
begin
  d := a;
  e := 1;

  while b > 1 do
  begin
    if (b mod 2) = 1 then
    begin
    e := (d * e) mod n;
    b := b - 1;
    end;
    d := (d * d) mod n;
    b := b div 2;
  end;

  result := (d * e) mod n;
end;

Ik heb de code net proberen om te zetten in VB en volgens mij heb ik dat ook wel goed gedaan, maar de code is blijkbaar toch niet goed (er komen verkeerde waardes uit)

dit is wat ik ervan gemaakt heb (voor de vb-kenners: willen jullie dit even controleren?)

code:

Function PowerMod(a As Double, b As Double, n As Double) As Double

Dim d As Double, e As Double

  d = a
  e = 1

  Do While b > 1
    If (b Mod 2) = 1 Then

    e = (d * e) Mod n
    b = b - 1
    End If
    d = (d * d) Mod n
    b = b / 2
  Loop

  PowerMod = (d * e) Mod n
End Function

ik heb ook de mods al vervangen door de zelfgemaakte mod-functie en dat geeft hetzelfde resultaat..

er moet dus toch blijkbaar iets fout zitten in de code, maar ik ben er tot nog toe niet uit..

[Mr. B.]

Op dinsdag 20 november 2001 20:55 schreef dudek het volgende:

[..]

Ik heb de code net proberen om te zetten in VB en volgens mij heb ik dat ook wel goed gedaan, maar de code is blijkbaar toch niet goed (er komen verkeerde waardes uit)

dit is wat ik ervan gemaakt heb (voor de vb-kenners: willen jullie dit even controleren?)

code:

Function PowerMod(a As Double, b As Double, n As Double) As Double

Dim d As Double, e As Double

  d = a
  e = 1

  Do While b > 1
    If (b Mod 2) = 1 Then

    e = (d * e) Mod n
    b = b - 1
    End If
    d = (d * d) Mod n
    b = b / 2
  Loop

  PowerMod = (d * e) Mod n
End Function

ik heb ook de mods al vervangen door de zelfgemaakte mod-functie en dat geeft hetzelfde resultaat..

er moet dus toch blijkbaar iets fout zitten in de code, maar ik ben er tot nog toe niet uit..

b := b div 2 in Pascal wordt in VB b = b \ 2, niet b = b / 2.
Wat in Pascal de div is, is in VB de backslash (deling zonder rest, een forward slash is deling met rest).

[dudek]

Op dinsdag 20 november 2001 21:25 schreef Mr. B. het volgende:

[..]

b := b div 2 in Pascal wordt in VB b = b \ 2, niet b = b / 2.
Wat in Pascal de div is, is in VB de backslash (deling zonder rest, een forward slash is deling met rest).

dat zal het wel zijn...
ik zal het even proberen...

[dudek]

dat van die backslash klopt, maar nu zet ie alleen nog maar de eerste letter om en de rest laat ie gewoon zoals het was, dat ga ik nu nog even proberen op te lossen..

[Verwijderd]

Ik heb de code nog een klein beetje weten te vereenvoudigen, maar dat heeft geen effect op de functionaliteit. Ik weet niet hoe dat in VB werkt, maar als je in Delphi een parameter "by value" meegeeft kun je die in je procedure/functie gewoon gebruiken als ware het een locale parameter, dat is dus wat ik nu doe.

code:

function PowerMod(a, b, n: int64): int64;
var c: int64;
begin
  c := 1;

  while b > 1 do
  begin
    if (b mod 2) = 1 then
    begin
    c := (a * c) mod n;
    b := b - 1;
    end;
    a := (a * a) mod n;
    b := b div 2;
  end;

  result := (a * c) mod n;
end;

Werkt de VB div (\ dus) eigenlijk wel op doubles? Waarom de mod dan niet? En heb je in VB geen 64 bit integers? Lijkt me een beetje onzinig om met floating point te werken als je met pure integer aritmetiek bezig bent.

[Mr. B.]

Op dinsdag 20 november 2001 22:19 schreef Xalista het volgende:
Ik heb de code nog een klein beetje weten te vereenvoudigen, maar dat heeft geen effect op de functionaliteit. Ik weet niet hoe dat in VB werkt, maar als je in Delphi een parameter "by value" meegeeft kun je die in je procedure/functie gewoon gebruiken als ware het een locale parameter, dat is dus wat ik nu doe.

In VB worden parameters standaard by reference meegegeven, je kunt het keyword ByVal voor een parameternaam plaatsen om 'm by value mee te geven.

Werkt de VB div (\ dus) eigenlijk wel op doubles?

Ja, a \ b is in VB in feite niks anders dan Int(a / b)

Waarom de mod dan niet?

Hoe wou je de modulus van een floating point getal bepalen?

En heb je in VB geen 64 bit integers?

Helaas niet
Het grootste integer-datatype in VB is een Long (een 32-bits signed integer).
(In VB.NET is een Long geloof ik 64-bits signed, maar dat weet ik niet zeker)

[Verwijderd]

Op dinsdag 20 november 2001 22:46 schreef Mr. B. het volgende:

[..]

In VB worden parameters standaard by reference meegegeven, je kunt het keyword ByVal voor een parameternaam plaatsen om 'm by value mee te geven.

Nou, dan moet de topicposter er maar gauw ByVal bij zetten,
anders gelden de wijzigingen die je aan a en b aanbrengt ook buiten de scope van de functie (waardoor je dus de key van je RSA algoritme killt).
Vandaar dat zijn programma alleen de eerst char codeerde, na die eerste char is zijn exponent namelijk 1 geworden en a^1 mod n is hoogstwaarschijnlijk gewoon weer a.

[..]

Ja, a \ b is in VB in feite niks anders dan Int(a / b)

In delphi ook, maar div werkt daar alleen als a en b beide integers zijn. Da's ook niet zo raar, want div is officieel een integer functie. Als je het met floats wilt moet je zelf maar Int(a/b) doen... (in Delphi tenminste)

[..]

Hoe wou je de modulus van een floating point getal bepalen?

Wil ik ook niet, maar omdat de div in VB blijkbaar ook op floats werkt, terwijl dat wiskundig gezien niet juist is dacht ik dat ze de mod misschien ook op floats hadden gedefineerd. Op zich zou je de mod van 2 floats ook gewoon kunnen defineren als de rest bij deling van die floats.

[dudek]

Op dinsdag 20 november 2001 23:18 schreef Xalista het volgende:

[..]

Nou, dan moet de topicposter er maar gauw ByVal bij zetten,
anders gelden de wijzigingen die je aan a en b aanbrengt ook buiten de scope van de functie (waardoor je dus de key van je RSA algoritme killt).
Vandaar dat zijn programma alleen de eerst char codeerde, na die eerste char is zijn exponent namelijk 1 geworden en a^1 mod n is hoogstwaarschijnlijk gewoon weer a.

dat was inderdaad het probleem...
de e en de d waardes werden steeds veranderd. Daarom heb ik die steeds opnieuw de goede waarde gegeven voordat ze de functie doorliepen, maar ByVal is wat mooier en zal later ook functioneler zijn, dus ik verander em ff snel..