Polynomial finite fields; ElGamal decryption

[LANS]

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.

 

[Michael Redei]

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 F₂₃ 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 a^p-1 ≡ 1 (mod p), which you can use to show 21^-6 = 21¹⁶ in F₂₃.

Also, since addition in F₂₃ is done modulo 23, you have x = 23 - x for all x ∈ F₂₃, which gives you 21¹⁶ = 2¹⁶.

 

[LANS]

Thanks, that helps.

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