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?

$\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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 12:06

1 Answer 1

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.

$\endgroup$
4
  • $\begingroup$ which wikipedia page exactly? which references? $\endgroup$
    – Martin
    Jan 12, 2015 at 13:45
  • $\begingroup$ The one about the index calculus algorithms, obviously. ;) I'll add inline links. $\endgroup$
    – fkraiem
    Jan 12, 2015 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, 2015 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, 2015 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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