Skip to main content
Cryptography

Return to Question

Tweeted twitter.com/StackCrypto/status/1001051168389419008
Minor edits
Link
edit approved May 28, 2018 at 3:45
Rodrigo de Azevedo
edit approved May 28, 2018 at 3:45
Rodrigo de Azevedo
  • 1
  • 1
  • 10

Why does a Galois field have to have an order of p^n$p^n$ where p$p$ is prime?

Fixed a mistake relating to how affine ciphers work (the multiplication factor must be relatively prime, the shift amount can be anything).
Source Link
Zen Hacker
Zen Hacker
  • 193
  • 5

I was reading about this in a cryptography book last night. I have a hunch about this, but I can't quite put my finger on it. I think this is a similar situation to an affine cipher, where the shift amountmultiplication factor has to be relatively prime with the size of the alphabet in order for the function to be surjective. Obviously for practical purposes, it would have to be $p^n$ where $p$ is the arity of the number system and $n$ is the bit width of a memory unit. But is there also a theoretical basis for requiring that a Galois field be of size $p^n?$

I was reading about this in a cryptography book last night. I have a hunch about this, but I can't quite put my finger on it. I think this is a similar situation to an affine cipher, where the shift amount has to be relatively prime with the size of the alphabet in order for the function to be surjective. Obviously for practical purposes, it would have to be $p^n$ where $p$ is the arity of the number system and $n$ is the bit width of a memory unit. But is there also a theoretical basis for requiring that a Galois field be of size $p^n?$

I was reading about this in a cryptography book last night. I have a hunch about this, but I can't quite put my finger on it. I think this is a similar situation to an affine cipher, where the multiplication factor has to be relatively prime with the size of the alphabet in order for the function to be surjective. Obviously for practical purposes, it would have to be $p^n$ where $p$ is the arity of the number system and $n$ is the bit width of a memory unit. But is there also a theoretical basis for requiring that a Galois field be of size $p^n?$

Source Link
Zen Hacker
Zen Hacker
  • 193
  • 5

Why does a Galois field have to have an order of p^n where p is prime?

I was reading about this in a cryptography book last night. I have a hunch about this, but I can't quite put my finger on it. I think this is a similar situation to an affine cipher, where the shift amount has to be relatively prime with the size of the alphabet in order for the function to be surjective. Obviously for practical purposes, it would have to be $p^n$ where $p$ is the arity of the number system and $n$ is the bit width of a memory unit. But is there also a theoretical basis for requiring that a Galois field be of size $p^n?$