# Tag Info

## Hot answers tagged finite-field

Accepted

### How to determine the order of an elliptic curve group from its parameters?

There is a rather deep polynomial-time algorithm for counting the $\mathbb F_q$-rational points of an elliptic curve published by René Schoof in 1985 (with subsequent improvements by Noam Elkies and A....
• 11.2k
Accepted

### Are there any (asymmetric) cryptographic primitives not relying on arithmetic over prime fields and/or finite fields?

Braid cryptography? Knapsack cryptosystems, like Nasako–Murikami? Lattice-based cryptography tends to work in polynomial rings or modules with coefficients in finite fields, but whose higher-level ...
• 46.2k

### What is the main difference between finite fields and rings?

Since you specified finite fields and other answers didn't talk about it, I am adding the following: Fields are rings which are commutative and in which all nonzero elements have multiplicative ...
Accepted

### What is the main difference between finite fields and rings?

In general rings do not have inverse multiplication, as you claimed. Think for example about the integers modulo $4$. In this case, $2$ is not invertible as there is no element that multiplied by $2$ ...
• 3,812
Accepted

### how does BearSSL's GCM modular reduction work?

There are three important points here to consider. 1. We work in $\mathbb{F}_2[X]$. This means that we do additions and multiplications of binary polynomials, i.e. polynomials whose coefficients are ...
• 85.1k
Accepted

• 11.2k
Accepted

• 126k
Accepted

### How to calculate AES logarithm table?

(Note: I'm using hexadecimal numbers to denote AES field elements and decimal numbers to denote integers.) First of all, you have to fix a generator of the AES field's multiplicative group. There's ...
• 11.2k
Accepted

### Do $v_1=\alpha\cdot r_1$ and $v_2=\alpha\cdot r_2$ leak information about $\alpha$

Question: Given $n$ values $v_1=\alpha \cdot r_1 \bmod p,..., v_n=\alpha \cdot r_n \bmod p$ for a large $n$ can the adversary learn the value $\alpha$? Answer: assuming that the $r_i$ values are ...
• 135k
Accepted

### Is it necessary for the Rijndael polynomial to be primitive?

Is it necessary to choose a primitive polynomial for an S-Box? Actually, it is not necessary (and, as the polynomial they actually use in AES, $x^8 + x^4+ x^3 + x + 1$, is not primitive, and so it's ...
• 135k
Accepted

### Why doesn't the GCM spec use a more efficient multiplication algorithm?

My question is... why? There are a number of different algorithms that perform $GF(2^{128})$ multiplication, all with different trade-offs (speed on specific platforms, program size, memory usage, ...
• 135k

### Why are binary extension fields preferred for Shamir secret sharing?

The main reason is that there is no disadvantage to using a binary extension field. Since the computing and communications infrastructure already runs over binary, this is the simplest and most ...
• 16.9k

### Random Galois fields

GF$(2^8)$ or $\mathbb F_{2^8}$ can also be viewed as the vector space $\mathbb F_2^8$ of $8$-bit vectors (or bytes) over GF$(2)$ or $\mathbb F_2$. Suppose $\{\beta_0, \beta_1, \cdots, \beta_7\}$ is a ...
• 2,636
Accepted

### Advantage of $\operatorname{GF}(2^8)$ over $\mathbb Z/2^8\mathbb Z$ in AES/Rijndael

One important property of the mixColumns step is that it is Maximum Distance Separable (MDS). That is, if $M$ is our multiplication matrix, if you take any two distinct input vectors $V$ and $V'$, ...
• 135k

### What is the main difference between finite fields and rings?

Take a set $S$ and an operation, let's call it $\oplus$. Also take another operation, say $\odot$. Also fix an element $\mathcal O\in S$ such that $\forall s\in S: \mathcal O\oplus s=s$ and fix ...
• 44.8k
Accepted

### How does Montgomery reduction work?

In 1985, Montgomery introduced a new clever way to represent the numbers $\mathbb{Z}/n \mathbb{Z}$ such that arithmetic, especially the modular multiplications become easier. Peter L. Montgomery; ...
• 44.3k
Accepted

### Need help understanding math behind Rijndael S-Box

The code is using the fact that the Rijndael's* Galois field has the following generators†: 3 5 6 9 11 14 17 18 19 20 23 24 25 26 28 30 31 33 34 35 39 40 42 44 48 49 60 62 63 65 69 70 71 72 73 75 76 ...
• 44.3k

### Choosing finite field size in Shamir's Secret Sharing Scheme

Actually, you can do Shamir Secret Sharing over any finite field $GF(p^k)$, for any prime $p$ and any integer $k$. If $k=1$, you have the $GF(p)$ field you mentioned; however it works on extension ...
• 135k

### How to determine the order of an elliptic curve group from its parameters?

As yyyyyyy mentioned for counting number of points on elliptic curve over $\mathbb F_p$ we can use Elkies method. But for extension of fields use of this theorem make it so easy: Theorem : Let $E$ ...
• 2,285

### What is this "finite field cryptography"?

"Finite field cryptography" is fancy language for group-based cryptography done over the integers modulo a prime (instantiating a field) to distinguish this more "classic" approach from the new ...
• 44.8k
For any $g$ in the set $\mathbb Z_p^*=\{1,2,\dots,p-1\}$, consider the function $F_g$ over that set defined by $F_g(x)\;=\;g\cdot x\bmod p$. Since $p$ is prime, by Fermat's little theorem, iterating \$...