Join Log in
Score:3
Poseidon23 avatar Crypto

Polynomial Breakdown in proof of lower bounds on Discrete Log in the Generic Group

cn flag
Poseidon23

In Shoup's proof of the hardness of discrete log in the generic group in this paper, he mentions that:

At any step in the game, the algorithm has computed a list $F_1,\dots,F_k$ of linear polynomials in $Z/p^t[X]$ along with a list of values $z_1,\dots,z_k$ in $Z/s$, and a list $\sigma_1,\dots,\sigma_k$ of distinct values in $S$.

The algorithm is initially given the encodings of $1,x$ and access to the group operation + inverses so it is clear that anything the algorithm computes can be expressed as a linear polynomial in $Z/n[X]$, where $n=p^t s$. However, I don't see how this breaks down into a linear polynomial in $Z/p^t[X]$ and a constant in $Z/s$.

37
0 + 0
ggm
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.