Nyilvános kulcsú titkosírás

• RSA (Ron Rivest, Adi Shamir, Leon Adleman)
  • könnyû: n prímszám-e
  • nehéz: n felbontása két >1 szám szorzatára
• diszkrét logaritmus (W. Diffie, M.E. Hellmann)
  • könnyû: kiszámolni y=gⁿ-t (mod p)
  • nehéz: y, g és pbõl kiszámolni n-et.
• Méretek: minden szám 100 - 500 decimális jegyû.

Gyors hatványozás

• g, g², g⁴, g⁸, g¹⁶, g³², stb. kiszámitása
      (ismételt négyzetreemelés)
• a fentiek közül bizonyosakat összeszorzunk