0
$\begingroup$

Given a finite field GF(P^Q), having a subgroup with a prime order of L (P,Q,L are all primes), how difficult is it to find the discrete log, is it related to P and Q or is it related to L, or to both. What is the time required? O(sqrt(L)) ?

Does index calculus apply to Galois fields?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ The index calculus applies in the multiplicative group of all finite fields. Also, if $p$ is small a recent algorithm (Gaudry et al.) works even better ("quasi-polynomial"). $\endgroup$ – fkraiem Jan 12 '15 at 2:10
  • $\begingroup$ @fkraiem In which case an additional question might be what is the difficulty of factoring elements of finite fields (e.g. GF) into primes. Do you know? $\endgroup$ – Martin Jan 12 '15 at 2:14
  • $\begingroup$ What do you mean by "factoring elements of finite fields into primes"? There are no prime elements in a field. $\endgroup$ – fkraiem Jan 12 '15 at 2:19
  • $\begingroup$ @fkraiem then how does index calculus work in finite fields? Aren't there irreducible or prime elements in a UFD? Isn't that a requirement for index calculus (as a method for faster DL). What am I missing? $\endgroup$ – Martin Jan 12 '15 at 2:22
  • $\begingroup$ To solve $g^x = h$, $h$ is factored into primes in $\mathbf{Z}$ (or some larger ring, in the case of non-prime finite fields), not in the original field. For example, $6 = 3\times 2$, $3$ and $2$ are prime in $\mathbf{Z}$ but not in $\mathbf{F}_p$ (for any $p$ where they make sense). $\endgroup$ – fkraiem Jan 12 '15 at 12:06
1
$\begingroup$

First there are the "generic" discrete logarithm algorithms like Shanks's "baby step, giant step" and Pollard's $\rho$, which run in $O(\sqrt{L})$ and are thus of exponential complexity (in the size of $L$). Those algorithms work in virtually any group.

In the special case of the multiplicative groups of finite fields, we have subexponential algorithms (i.e, algorithms which are "in between" polynomial and exponential). The index calculus algorithm has many variants whose complexity varies slightly depending on the relative sizes of $p$ and $q$ (see the Wikipedia page and its references), but the details are not very important unless you want to specialise in discrete log algorithms (in which case, read the references mentioned above). What's important for cryptography is that due to such algorithms, cryptosystems based on the discrete log in finite fields must use larger keys than those based on the discrete log in elliptic curves for the same level of security.

Also, the "quasi-polynomial" algorithm of Gaudry et al. works for small $p$ (basically, when $p \le q$), and such cases should therefore be avoided, but they were rarely used in the first place anyway.

Improve this answer
$\endgroup$
4
  • $\begingroup$ which wikipedia page exactly? which references? $\endgroup$ – Martin Jan 12 '15 at 13:45
  • $\begingroup$ The one about the index calculus algorithms, obviously. ;) I'll add inline links. $\endgroup$ – fkraiem Jan 12 '15 at 14:14
  • $\begingroup$ thanks, maybe you'd care to ad the big-O complexity of the index calculus attacks, since you've added it for the other types. $\endgroup$ – Martin Jan 13 '15 at 5:57
  • $\begingroup$ There is no such thing as "the big-O complexity of the index calculus". First, you'd have to spcifiy which algorithm you are talking about, and even then you can only have an estimate of its complexity, based on a large number of heuristics. If you're really that interested, again, read the references mentioned on the Wikipedia page (or others). $\endgroup$ – fkraiem Jan 13 '15 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.