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.
$\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.