# Polynomial finite fields; ElGamal decryption

## Homework Statement

Given some ElGamal private key, and an encrypted message, decrypt it.

## Homework Equations

Public key (F_q, g, b)
Private key a such that b=g^a

Message m encrypted so that r=g^k, t=mb^k

Decrypt: tr^-a = m

## The Attempt at a Solution

My problem is finding r^-a. I don't quite get polynomial finite fields, and I can't figure out how to get x such that r^x = r^-a in F_q.

I have an example from the textbook:
Public key (F_23, 7, 4), private key a=6, encrypted message r=21, t=11

The textbook then does 11*21^-6 = 11*21^16 = 11*2^16 = 11*9 = 7

I understand why 11*2^16 = 7 in F_23, but I don't get how 21^-6 = 21^16 and how 21^16 = 2^16.

Any help is appreciated.

I understand why 11*2^16 = 7 in F_23, but I don't get how 21^-6 = 21^16 and how 21^16 = 2^16.

Since 23 is a prime number, the field F23 is essentially just the set {0,1,2,...,22} with addition and multiplication carried out modulo 23.

Do you know Fermat's Little Theorem? It says that for any prime p and and any integer a, we have ap-1 ≡ 1 (mod p), which you can use to show 21-6 = 2116 in F23.

Also, since addition in F23 is done modulo 23, you have x = 23 - x for all x ∈ F23, which gives you 2116 = 216.

Thanks, that helps.

Yes, I do know Fermat's little theorem, I feel silly now for not thinking of it.