1

I am going through my cryptography notes in a section about sub exponential factor base methods for computing discrete logarithms, and I come across a statement I don't understand about an algorithm to compute discrete logarithms:

Consider $p$ a prime and $F_p^\ast$ the group of invertible elements from the field $F_p$.

Given the prime $p$, create a factor base consisting of the first $t$ primes, where $t$ depends on the size of $p$. Select random values $a_i$ with $1 \leq a_i \leq p-1$ and compute $r_i = g^{a_i} \pmod{p}$. Store every value $r_i$ which is divisible only by primes in the factor base which I will denote $S$, and store them as

$r_i=g^{a_i} = \Pi_{S} p_j^{e_i,j} \pmod {p}$ . The logarithm with respect to $g$ of this relation can be reinterpreted as

$a_i \equiv \sum_{S}e_{i,j}\log(p_j) \pmod {p-1}$ .

This last statement is confusing me, I'm not sure where the $\pmod {p-1}$ part comes from. Any insights appreciated.

In addition I am not sure what the author means by $\log(p_j)$ in this context.

IntegrateThis
  • 3,778
  • Do you know Little Fermat's Theorem? – enedil Mar 11 '19 at 23:02
  • @enedil yes i do. – IntegrateThis Mar 11 '19 at 23:04
  • So by this theorem, the logarithm generates additive group mod $p-1$. – enedil Mar 11 '19 at 23:16
  • @enedil I don't follow, but I will study a bit and come back. If you could elaborate a bit that would be nice. I understand that if $p$ is prime and $gcd(a,p)=1$ then $a^{p-1} \equiv 1 mod (p)$. – IntegrateThis Mar 11 '19 at 23:19
  • @enedil the logarithm of what? – IntegrateThis Mar 11 '19 at 23:59
  • 1
    If $p$ is prime, then $gcd(a,p)=1$ for every $a$ except $0$. Consider nonzero $a$. Then $a^{x} \equiv_{p} a^{(x) \pmod {p-1}}$. So anything in exponent is interesting modulo $p-1$. Taking logarithm formalizes this approach - just as $\log(x)$ maps positive real numbers with multiplication into reals with addition, modular $\log$ changes multiplication into addition, but the exponent is taken modulo $p-1$. – enedil Mar 12 '19 at 00:01
  • @enedil I don't understand your notation there. Is there a typo? – IntegrateThis Mar 12 '19 at 00:03
  • 1
    No, there isn't. $\equiv_k $ means just equivalence modulo $k$, in the exponent there is a remainder modulo $p-1$. If you like it better, since $a^{y(p-1)+x}\equiv_p a^x$, then in fact, comparing exponents happens modulo $p-1$. – enedil Mar 12 '19 at 00:10
  • @enedil OK I get it now. Very interesting. Thanks for the help. – IntegrateThis Mar 12 '19 at 00:35

1 Answers1

2

$\log(p_j)$ is the logarithm of $p_j$ in $F_p^\ast$ (so modulo $p$, which is where we want to compute the target logarithms, so wrt some predetermined generator $g$). The $p_j$ are in the factor base and so by assumption we already precomputed the logarithm of all of them. That's part of the precomputation phase of this algorithm.

The $p-1$ comes from the fact that $F_p^\ast$ has $p-1$ elements (all field elements, except $0$), and the well-known sum/product identity for logs in this finite field setting then becomes $\log(xy) = \log(x) + \log(y) \pmod{p-1}$. The $\log$-function is a homomorphism from $F_p^\ast$ (multiplicative group) to $Z/{(p-1)\mathbb{Z}}$, the addive group, the inverse of $x \to g^x$. The latter is a homomorphism by Fermat's little theorem.

Henno Brandsma
  • 242,131