Code-Beispiel
Modulares Potenzieren und Quadrieren
| Lizenz: | Erster Autor: | Letzte Bearbeitung: |
| k. A. |  stephanbrunker |  05.11.2015 |
Bei vielen Verschlüsselungsalgorithmen kommt Modulararithmetik zum Einsatz, das heißt das mit Modulo einer Primzahl gerechnet wird. Damit ist es auch möglich, eine 32bit Zahl mit einer zweiten 32bit Zahl zu potenzieren und das Ergebnis bleibt bei 32bit. Da man für die Multiplikation zweier 32-bit Zahlen ein 64bit Ergebnis erhält, ist das auch die Obergrenze. ( Für 2048bit Modulorechnung gibt es die Bigint-Erweiterung )
Berechnet wird dies wie eine "normales" Potenzieren, nur dass nach jedem Schritt modulo dividiert wird:
'modular exponentiation @32bit
Function mod_pow32(ByRef bb As ULong, ByRef ee As ULong, ByRef m As ULong) As ULong
If ee < 0 Then Print "Cannot raise a integer to a negative power"
If ee = 0 Then Return 1
Dim As LongInt r=1, b=bb
Dim As Byte i,bitlen
For i = 31 To 0 Step -1
If Bit(ee,i) Then
bitlen = i
Exit For
End If
Next i
b Mod= m
For i = 0 To bitlen-1
If Bit(ee,i) Then
r *= b
r Mod= m
End If
b = b * b
b Mod= m
Next i
r *= b
r Mod= m
Return CULng(r)
End Function
Einfacher ist es beim quadrieren:
'modular square @32bit
Function mod_square32(ByRef b As ULong, ByRef m As ULong) As ULong
Dim As LongInt r
r = b*b
r Mod= m
Return CULng(r)
End Function
| Zusätzliche Informationen und Funktionen |
|---|
- Das Code-Beispiel wurde am 05.11.2015 von stephanbrunker angelegt.
- Die aktuellste Version wurde am 05.11.2015 von stephanbrunker gespeichert.
|
|
Wer ist online?
Buchempfehlung
FreeBASIC-Chat
FreeBASIC-Nachrichten jetzt auch über Twitter erhalten. Follow us!
Bearbeiten
Versionen