Wikipedia:Reference desk/Archives/Mathematics/2024 October 25

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 25

Why does splitting extension field’s elements into several subfields doesn’t help solving discrete logs despite it helps computing exponentiations and multiplications ?

Let’s say I have 2 finite fields elements $A$ and $B$ in $GF_{p}^{6}$ having their discrete logarithm belonging to a large semiprime' suborder/subgroup $s$ such as $p>s$.

$A$ and $B$ can be represented as the cubic extension of $GF_{p}^{2}$ by splitting their finite field elements. This give $A.x\in GF_{p}^{2}$ ; $A.\in GF_{p}^{2}$ ; $A.z\in GF_{p}^{2}$ ; and $B.x\in GF_{p}^{2}$ ; $B.y\in GF_{p}^{2}$ ; $B.z\in GF_{p}^{2}$. This is useful for simplifying computations on $A$ or $B$ like multiplying or squaring by peforming such computations component wise. An example of which can be found here : https://github.com/ethereum/go-ethereum/blob/24c5493becc5f39df501d2b02989801471abdafa/crypto/bn256/cloudflare/gfp6.go#L94

However when the suborder/subgroup $s$ from $GF_{p}^{6}$ doesn’t exists in $GF_{p}^{2}$, why does solving the 3 discrete logarithm between each subfield element that are :

1. dlog of $A.x$ and $B.x$
2. dlog of $A.y$ and $B.y$
3. dlog of $A.z$ and $B.z$

doesn’t help establishing the discrete log of the whole $A$ and $B$ ? 82.66.26.199 (talk) 13:30, 25 October 2024 (UTC)

Supposing that you can solve the discrete log in GF(q), the question is to what extent this helps to compute the discrete log in GF(q^k). Let g be a multiplicative generator of $GF(q^{k})^{\times }$. Then Ng is a multiplicative generator of $GF(q)^{\times }$, when N is the norm map down to GF(q). Given A in $GF(q^{k})^{\times }$, suppose that we have x such that $NA=Ng^{x}$. Then $Ag^{-x}$ belongs to the kernel of the norm map, which is the cyclic group of order (q^k-1)/(q-1) generated by g^{q-1}. Therefore it is required to solve an additional discrete log problem in this new group, the kernel of the norm map. When the degree k is composite, we can break the process down iteratively by using a tower of norm maps. If (a big if) each of the norm one groups in the tower has order a product of small prime factors, then Pohlig-Hellman can be used in each of them. Tito Omburo (talk) 14:53, 25 October 2024 (UTC)

And when the order contains a 200‒bits long prime too large for Pohlig‑Hellman ? 82.66.26.199 (talk) 15:39, 25 October 2024 (UTC)

Well, the basic idea is that if k is composite, then the towers are "relatively small", so they would be smoother than the original problem, and might be a better candidate for PH than the original problem. It seems unlikely that a more powerful method like the function field sieve would be accelerated by having a discrete log oracle in the prime field. The prime field in that case is usually very small already. For methods with p^n where p is large, an oracle for the discrete log in the prime field also doesn't help much (unless you can do Pohlig-Hellman). Tito Omburo (talk) 16:06, 25 October 2024 (UTC)