Tag Info

The $GF$ in $GF(p^n)$ is not a function — it just stands for "Galois field (of $p^n$ elements)". As for what a Galois field is, it's a finite set of things (which we might represent e.g. with the numbers from $0$ to $p^n-1$), with some mathematical operations (specifically, addition and multiplication, and their inverses) defined on them that let us ...

Discrete logarithms in $\mathbb{F}_{p}$ share the same asymptotic complexity as integer factorization for general numbers: $L_p[1/3,1.923]$ for general integers, $L_p[1/3,1.587]$ for special integers. Discrete logarithms in $\mathbb{F}_{p^n}$ have the same asymptotic complexity as factoring special integers, i.e. $L_{p^n}[1/3, 1.587]$, via the Function ...

Let $n = \lceil \log q \rceil$ (with "$\log$" being the base-2 logarithm, so $n$ is the size, in bits, of $q$). If $q$ is a prime integer (i.e. $\mathbb{F}_q$ is the field of integers modulo $q$), then classical implementations will have cost $O(n)$ for addition and subtraction, $O(n^2)$ for multiplications and divisions. The cost of multiplications can be ...

Well, if $q$ is a prime (and not $p^n$ with $n>1$), then addition, subtraction and multiplication can be performed by doing the traditional operations modulo $q$, that is: $a +_{\mathbb{F}_q}b \equiv (a+b) \bmod q$ $a -_{\mathbb{F}_q}b \equiv (a-b) \bmod q$ $a \times_{\mathbb{F}_q}b \equiv (a\times b) \bmod q$ As such, addition and subtraction can be ...

There is no reason in Shamir's scheme for the finite field $\mathbb F$ to have a prime number $p$ of elements; the field can have $p^m$ elements for suitable prime $p$ and integer $m \geq 1$. So, using $F_{2^8}$, the field with $2^8$ elements is perfectly all right. However, choosing $m = 1$ has the advantage that calculations in $\mathbb F_p$ can be done ...

I think there are some gaps and some misunderstandings in what you say. A finite field or Galois field $GF(p^n)$ is a collection of $p^n$ $n$-dimensional vectors. Here, $p$ is a prime, and each coordinate in a vector is an integer in the range $[0,p-1]$; that is, an element of $GF(p)$. Thus, $$\mathbf A = (a_0, a_1, \ldots, a_{n-1}), ~~ a_i \in GF(p)$$ is ...

Antoine Joux very kindly sent me the following on the topic: People worry that [logarithms over fields with composite exponent] might be easier, this is why they use prime exponent. For some factorization of the exponent, viewing the finite field as a tower of extensions $(p^{n_1})^{n_2}$ indeed makes things easier. See "The function field sieve ...

For security of ECC, the choice of the irreducible polynomial is unimportant, because all finite fields with the same cardinal are isomorphic to each other (and the isomorphisms are easy to compute); this is why we can say "the finite field $GF(2^{163})$" even though there are many irreducible polynomials of degree $163$ over $GF(2)$. So the algebraic ...

To complete @Samuel's answer, there are a few shortcuts that can be used when n is composite; however, they only contribute small constant factors, hence they do not change the asymptotic behavior: If n can be divided by r, then one can first solve the discrete logarithm in the subfield GF(2r). In a sieve-based algorithm, this can provide up to half the ...

The Handbook on Applied Cryptography (link to the pdf version is on Alfred's webpage) has some of the known techniques to do finite field arithematic. If you are doing arithmetic to implement Elliptic Curve Cryptography (note the comment made by Paulo), then there are methods that depends on whether you are doing it in Jacobian or Projective plane (inverse ...

There are several questions hidden in your question. You'll have to distinguish between the polynomial ring $\mathbb Z_2[X]$, and the factor field $GF(2^8) = \mathbb Z_2[X]/F$ (where $F$ is any irreductible polynomial of degree 8). In $\mathbb Z_2[X]$, the only polynomial which is a factor of all others is the trivial polynomial $1$. (In general, in a ...

While I haven't read the paper, I believe I can answer these questions: I'm not sure if the implied modulus of each operation is $q$, as I added myself to the above formulas. Could someone please clarify this? The paper omits it... No, the arithmetic is done modulo $p$. Remember, you're working in a subgroup of size $q$ of $\mathbb{Z}^*_{p}$; ...

As far as I can tell from your description, the modulus is p. To multiply two group elements, you compute x*y (mod p); because the generator g you choose has period q it'll all work out fine. No, p, q, and g can (and must) all be public. This is ElGamal, not RSA we're talking about - the security comes from the (presumed) hardness of taking discrete ...

While $GF(2^8)$ is indeed isomorphic to $GF((2^4)^2)$ (and to the other fields you have mentioned), if you use the latter you will need a conversion routine to change the field representation from and to $GF(2^8)$. This will probably defeat any performance gain with the alternative representation (and I'm not sure there would be any). Another related issue ...

Actually, the choice of irreducible polynomial is unimportant in AES; for any polynomial representation of $GF(2^8)$, you can modify the affine tranformation (and the MixCollumn) operation to come up with a block cipher that is equivalent to AES (meaning that any break to that can be translated to a break on the original AES). The key observation here is ...

Ok so you probably know that fields are interesting structures to study...they are places where arithmetic works nicely. Most cryptosystems depending heavily on numbers usually must take the numbers from some field in order for things to work out. Now there are many fields with infinitely many elements, $\mathbb{Q}, \mathbb{R}, \mathbb{C}...$, but what ...

The complexity of the number field sieve can be obtained from the expected size of the coefficients of the polynomial $f(x) = x^d + c_{d-1} x^{d-1} + \ldots + c_0$: if $c_i \le N^{\epsilon/d}$, then the expected runtime is $$ \exp\left(\left(\left(\frac{32(1 + \epsilon)}{9}\right)^{1/3} + o(1)\right) (\log N )^{1/3} (\log \log N)^{2/3}\right),$$ or simply ...

It has to do with which modulus you use. You did all your arithmetic modulo 11. However, when using Feldman's VSS, you gotta use two different moduli (using each one in the appropriate spot). In your example, you shouldn't do all arithmetic modulo 11. Instead, you should be doing some arithmetic modulo 11, and some arithmetic modulo 5 (the order of $g$ ...

Antoine Joux announced the computation of discrete logarithm over $\mathbb{F}_{2^{257 \times 24}}$, which is now pretty close to what was being used in pairing-based cryptography. According to Joux, "a direct consequence of this record is that supersingular curves (of genus 1 or 2) defined over GF(2^257) cannot be used securely for pairing-based ...

Yes. $r^n$ needs to be coprime with $n^2$. The only elements which have don't an inverse modulo $p^2 q^2$ are all multiples of $p$ and all multiples of $q$, so we just require $\gcd{(r^n, p)} = \gcd{(r^n, q)} = 1$. $\implies \gcd{(r^n, n}) = 1$ Clearly, if $r$ is coprime to $n$, then $r \times r \times \cdots \times r ~ (n ~ \mathrm{times})$ will also be ...

In addition to some of the other answers, what has helped me the most in understanding finite fields, or any algebraic structure for that matter is playing with them. For this, I have found Sage to be indispensible. So, looking at Galois Fields in Sage goes something like this: sage: f = GF(2^8, 'x') sage: f Finite field in x of size 2^8 sage: ...

Finite fields are a fascinating subject, but it's not really something you can understand from a forum. I really recommend you take a book about number theory and spend some time with it. It will help you greatly for the rest of your life. For instance, I like "A Computational Introduction to Number Theory and Algebra" by Victor Shoup. The whole book is ...

This is probably just a difference in notation than any failure in understanding or implementation. Some people define recurrence relations with subscripts in reverse order than others; the original description given by Berlekamp in his 1968 book Algebraic Coding Theory began counting from $1$ instead of $0$ etc. Observe that $$x^7 + x^4 + x^3 + x^1 = x^7(1 ...

Even after revision, this question makes litle sense. The OP wants a polynomial with the property that ... this polynomial must factor all the polynomials or possibly ... will factor into all the polynomials in the field With regard to the first, a polynomial is not an operator or algorithm that can be used to factor a polynomial (or decide ...