Wikipedia:Reference desk/Mathematics

Welcome to the mathematics section
of the Wikipedia reference desk.

skip to bottom

Select a section:

• Computing
• Entertainment
• Humanities
• Language
• Mathematics
• Science
• Miscellaneous
• Archives

Want a faster answer?

Main page: Help searching Wikipedia

   

How can I get my question answered?

• Select the section of the desk that best fits the general topic of your question (see the navigation column to the right).
• Post your question to only one section, providing a short header that gives the topic of your question.
• Type '~~~~' (that is, four tilde characters) at the end – this signs and dates your contribution so we know who wrote what and when.
• Don't post personal contact information – it will be removed. Any answers will be provided here.
• Please be as specific as possible, and include all relevant context – the usefulness of answers may depend on the context.
• Note:
  • We don't answer (and may remove) questions that require medical diagnosis or legal advice.
  • We don't answer requests for opinions, predictions or debate.
  • We don't do your homework for you, though we'll help you past the stuck point.
  • We don't conduct original research or provide a free source of ideas, but we'll help you find information you need.

Ready? Ask a new question!

How do I answer a question?

Main page: Wikipedia:Reference desk/Guidelines

• The best answers address the question directly, and back up facts with wikilinks and links to sources. Do not edit others' comments and do not give any medical or legal advice.

See also:

• Teahouse
• Help desk
• Village pump
• Help manual

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)

October 29

If the white amazon (QN) in Maharajah and the Sepoys is replaced by the fairy chess pieces, does black still have a winning strategy? Or white have a winning strategy? Or draw?

If the white amazon (QN) in Maharajah and the Sepoys is replaced by the fairy chess pieces, does black still have a winning strategy? Or white have a winning strategy? Or draw?

1. QNN (amazon rider in pocket mutation chess, elephant in wolf chess)
2. QNC (combine of queen and wildebeest in wildebeest chess)
3. QNNCC (combine of queen and “wildebeest rider”)
4. QNAD (combine of queen and squirrel)
5. QNNAD (combine of amazon rider and squirrel)
6. QNNAADD (combine of queen and “squirrel rider”)

218.187.64.154 (talk) 17:38, 29 October 2024 (UTC)

Another question: If use wildebeest chess to play Maharajah and the Sepoys, i.e. on a 11×10 board, black has a full, wildebeest chess pieces in the position of the wildebeest chess, white only has one piece, which can move as either a queen or as a wildebeest on White's turn, andthis piece can be placed in any square in rank 1 to rank 6 (cannot be placed in the squares in rank 7 or rank 8, since the squares in rank 7 or rank 8 may capture Black's pieces (exclude pawns) or be captured by Black's pieces (or pawns), especially e7, g7, e8, g8, which may capture Black's king). Black's goal is to checkmate the only one of White, while White's is to checkmate Black's king. There is no promotion. (Unlike wildebeest chess, stalemate is considered as a draw) Who has a winning strategy? Or this game will be draw by perfect play? 218.187.64.154 (talk) 17:31, 1 November 2024 (UTC)

November 4

Name of distance function

I have a distance function in my code. I know it has a name and a Wikipedia article (because I worked on the article), but I am old and the name of the function has skipped my mind. I'm trying to reverse search by using the formula to find the name of the function, but I can't figure out how to do it. So, what is the name of this distance function: d_ab = -lnΣ√a_ib_i. 68.187.174.155 (talk) 12:53, 4 November 2024 (UTC)

If $a=(0.6,0.8)$ and $b=(0.8,0.6),$ the value of this measure is about $-0.326\,.$ This does not make sense for an indication of distance.  --Lambiam 15:02, 4 November 2024 (UTC)

My brain finally turned back on and I remembered it is an implementation of Bhattacharyya distance. 68.187.174.155 (talk) 15:52, 4 November 2024 (UTC)

Normally when you call something a distance function it has to obey the axioms of a metric space. Since Bhattacharyya distance applies only to probability distributions, the previous example would not be relevant. Still, the term "distance function" is used rather loosely since (according to the article) the Bhattacharyya distance does not obey the triangle inequality. The w:Category:Statistical distance has 38 entries, and I doubt many people are familiar with most of them. --RDBury (talk) 18:08, 4 November 2024 (UTC)

When I was in college in the 70s, terminology was more precise. Now, many words have lost meaning. Using the old, some would say "prehistoric" terminology, a function is something that maps or relates a single value to each unique input. If the input is the set X, the function gives you the set Y such that each value of X has a value in Y and if the same value exists more than once in X, you get the same Y for it each time. Distance functions produce unbounded values. Similarity and difference functions are bounded, usually 0 to 1 or -1 to 1. Distance is usually bounded on one end, such as 0, and unbounded on the other. You can always get more distant. The distance function mentioned here is bounded on one end, but not the other. It does not obey triangle inequality, as you noted, so it is not a metric. Distance functions have to obey that to be metrics. Then, we were constantly drilled with the difference between indexes and coefficients. This function should be an index from my cursory read-through because it is logarithmic. If you double the result, you don't have double the distance. I've seen all those definitions that used to be important fade away over the decades, so I expect that it doesn't truly matter what the function is called now. 12.116.29.106 (talk) 16:12, 5 November 2024 (UTC)