This template must be substituted. Replace {{Archive header with {{subst:Archive header.

{| width = "100%"

|- ! colspan="3" align="center" | Mathematics desk |- ! width="20%" align="left" | < September 1 ! width="25%" align="center"|<< Aug | September | Oct >> ! width="20%" align="right" |Current desk > |}

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.

September 2

Finding reverse mapping in modular arithmetic problem

This is not a homework problem, but it is a subproblem in one of the online problems in SPOJ (which I do for fun and learning). Thus, I am not asking for a solution, but asking for some hints and directions to look for, which enables me to solve the problem myself.

The subproblem is a simple cryptanalysis problem: Given a prime number p and an integer

0\leq q<p

,

find the integer

0\leq j\leq {\frac {p-1}{2}}

such that q is the remainder of

{\frac {j^{2}}{p}}

The most simpleminded manner to solve this would be by a brute force method, where I would simply iterate through all possible values of j, compute the remainder r of ${\frac {j^{2}}{p}}$ , and stop when r=q. However, not only is this a stupid and boring approach, but p also has a value of a few billions, and in the actual problem I need to find j for fixed p for thousands of different values of q within a few seconds of computational time.

So, it is very simple to find r(j; p), the problem is finding the reverse mapping j(r; p).

Apparently, for uniquely resolving j this implies that the mapping between j and r is a one-to-one function.

Actually, the limit I have stated for j is not stated in the actual problem, but since

j^{2}\quad (\operatorname {mod} \ p)=(p-j)^{2}\quad (\operatorname {mod} \ p)

I can see that j and p-j gives the same remainder. Thus, j should only extend up to (p-1)/2 (p is odd) as after that the mapping is mirrored and no longer one-to-one.

To further approach the problem, not being very mathematically knowledgeable about modular arithmetics, I have tried to start with small primes p = 3, 5, 7, 11, 13,... and simply write down the r(j) for the different possible js to try and find a pattern or some systematics in how to go the other way and find generalizations valid for much larger ps. For instance for p = 11, I do find that the mapping is one-to-one, as no two js 0,...,5 give the same remainder

Simple p=11 example
j     r   floor(j*j/p)
0     0           0
1     1           0
2     4           0
3     9           0
4     5           1
5     3           2

For all the primes I have tried the mapping is one-to-one, although I have not yet understood why that is so? Nor have I managed to find a pattern.

I would appreciate a hint, but not a spoiler. --Slaunger (talk) 13:54, 2 September 2011 (UTC)

Hint: read primitive root modulo n and discrete logarithm. Gandalf61 (talk) 14:28, 2 September 2011 (UTC)

Thanks for the hints, which has given me several new topics in number theory to study and understand. The articles are certainly not a give away of the solution (I did not find any obvious hints in my first skimming, but I will now study them closer). I appreciate that. --Slaunger (talk) 20:37, 2 September 2011 (UTC)

I am confused. The theory in those articles is very much focused on algorithms for finding the exponent x for a known base/generator g solving g^x = h (mod n). But in this case the base is unknown, whereas I know the exponent is 2. Would it be possible to get an additional hint, please? --Slaunger (talk) 21:43, 2 September 2011 (UTC)

Take a look at Cipolla's algorithm, Pocklington's algorithm and Tonelli–Shanks algorithm. Gandalf61 (talk) 13:05, 3 September 2011 (UTC)

Thanks! Wow, it is a revelation of cool recipes. Should be easy now. These guys were really smart. --Slaunger (talk) 19:19, 3 September 2011 (UTC)

Problem solved! Turned out the p in the problem had properties, which made the problem quite simple to solve using Pocklington's algorithm. Now, I learned something new today. --Slaunger (talk) 20:27, 3 September 2011 (UTC)

Column comparison

This is statistics, but I figure it goes in this desk... I am looking at a table with 3 columns: A, B, and C. A, B, and C are exclusive (ie: White, Black, Other). The values are averages, like average height for everyone in each group. It has notations next to the values like * or +. At the bottom, it says "* A vs. B p<0.05" and "+ A vs. B p<0.01". I want to know for certain what this means. I think it means that there is a correlation, but I don't know the specific terminology such as "95% confidence correlation". -- kainaw ™ 16:05, 2 September 2011 (UTC)

P-value may help. --Tagishsimon (talk) 16:23, 2 September 2011 (UTC)

You really need to look at either the article text or the Methods section of the paper -- one or the other should tell you what statistical test was performed on the data from the table. The numbers probably mean there is a statistically significant difference between the values for A and B, but without more information it is impossible to be sure. Looie496 (talk) 16:52, 2 September 2011 (UTC)

After searching and searching, I found the method buried in the paper. It is a student's t-test. -- kainaw ™ 17:12, 2 September 2011 (UTC)

Then yes, it means there is a statistically significant difference between the A and B values, at a significance level of 0.05 (or 0.01). Looie496 (talk) 17:47, 2 September 2011 (UTC)

Cubic metric

We all know that given x, y, z etc that the square root of the sum of the squares ( x^2 + y^2 + z^2 ) ^ 1/2 is a metric that equates to the distance between points 0,0,0 and x,y,z in a mutually orthogonal geometry.

Does the cubic metric ( x^3 + y^3 + z^3 ) ^ 1/3 have either any use or any practical meaning? -- 81.98.137.99 (talk) 18:38, 2 September 2011 (UTC)

What you describe is the p-norm for p = 3. It does not have as many nice properties as p = 2; for example, it is not a Hilbert space (see Lp space#Special cases). —Bkell (talk) 19:25, 2 September 2011 (UTC)

Would being a p-norm require absolute values, that is: ( |x|^3 + |y|^3 + |z|^3 ) ^ 1/3? What is the significance of omitting them? The OP's "cubic metric" can be negative. -- 110.49.233.26 (talk) 00:02, 3 September 2011 (UTC)

Oh, yeah, thanks, 100.49.233.26, for catching that. I overlooked the absence of absolute values. —Bkell (talk) 04:48, 3 September 2011 (UTC)

The p-norm, where p is any positive real number, does require the moduli. The definition is

||{\mathbf {x} }||_{p}:=\left(\sum _{k=1}^{n}|x_{k}|^{p}\right)^{\frac {1}{p}}.

I like norm because the "unit ball" as p tends to infinity is a diamond. — Fly by Night (talk) 02:28, 3 September 2011 (UTC)

The "unit ball" under the ∞-norm is a square in two dimensions, and a cube in three dimensions. Perhaps you're thinking of the 1-norm, which gives for the "unit ball" a diamond (i.e., a square rotated 45°) in two dimensions, an octahedron in three dimensions, and, in general, a cross-polytope? —Bkell (talk)

I was thinking of the ∞-norm, but I got the mental image wrong. You're right, it should be a square and not a diamond. — Fly by Night (talk) 17:05, 3 September 2011 (UTC)

Probability issue and programming it

I'm trying to program (language not relevant) a function that will tell me probabilities of exact frequencies. For example, if we have 3 dice, each with different number of faces (for example a 6, 12, and 18 sided one). What are the odds that 2 of them, and only 2 of them will be the number 1.

I've been solving it by summing the probabilities of each matching set. So in this example, 1/6 * 1/12 * (1 - 1/18) = 13%... repeat for the other sets... 1/6 * (1 - 1/12) * 1/18... etc., and then sum the result. This matches the results of a simulation I ran a few million times.

So I have 3 questions: 1) is this method correct and what is it called? 2) is there an easier way to do this? 3) are there any common ways of programming a function to do this (for instance, using a bit mask to create the sets or nesting loops)?

I ask #3 because while I could emulate my pen and paper method, calculating the matching sets itself seems cumbersome, let alone all the stats part. Lanytei (talk) 23:04, 2 September 2011 (UTC)

Your method seems valid (although your 13% should be 1.3%), but, wherever possible, I'd instead run through all the possibilities, and count the number which match your conditions. Here's a simple example (in Fortran):

subroutine DICE ()
implicit none

integer I,J,K,COUNT,MATCH
real    PROB

MATCH = 0
do I = 1,6
  do J = 1,12
    do K = 1,18
      COUNT = 0
      if (I .eq. 1) COUNT = COUNT + 1
      if (J .eq. 1) COUNT = COUNT + 1
      if (K .eq. 1) COUNT = COUNT + 1
      if (COUNT .eq. 2) MATCH = MATCH + 1
    enddo
  enddo
enddo

PROB = 100.0*MATCH/(6.0*12.0*18.0)
print *,"Probability = ",PROB,"%"

return
end

Note that this assumes fair dice. Unlike your simulation, the results should be exact (except for round-off error). The inside loop should only run 1296 times, too, so it should be quite quick. StuRat (talk) 23:26, 2 September 2011 (UTC)

To make this subroutine more flexible, you could:

1) Pass in I_MAX, J_MAX, and K_MAX, instead of hard-coding 6, 12, and 18.

2) Pass in I_LIST, J_LIST, and K_LIST, which would be lists of numbers for each die considered to be a match, instead of hard-coding 1 for each.

3) Pass in COUNT_TARGET, the number the COUNT should match to be considered a "hit", instead of hard-coding 2.

4) Expand it to work for more than 3 dice.

5) Return the PROBABILITY, instead of just printing it out. StuRat (talk) 23:34, 2 September 2011 (UTC)

Thank you for that, but my probabilities scale much too quickly for me to reliably use that method. Does anyone know what this kind of problem/solution is called? Lanytei (talk) 04:02, 3 September 2011 (UTC)

So how many dice with how many sides are we talking about ? StuRat (talk) 05:53, 3 September 2011 (UTC)

You have probabilities

p_{1},p_{2},\cdots ,p_{n}

and independent Bernoulli trials with the corresponding probabilities. You want the probability that exactly k of the trials is positive. This is

\sum _{|A|=k}\left(\prod _{i\in A}p_{i}\prod _{i\not \in A}(1-p_{i})\right)

. Denoting

\alpha _{i}={\frac {1-p_{i}}{p_{i}}}

, this is equal to

\prod _{i}p_{i}\cdot \sum _{|A|=n-k}\prod _{i\in A}\alpha _{i}

. One option is to brute-force all

{\binom {n}{k}}

summands (I'd use a virtual nested loop for this). Another is to use the fact that

\sum _{|A|=n-k}\prod _{i\in A}\alpha _{i}

is the coefficient of

x^{k}

in the polynomial

f(x)=\prod _{i}^{}(x+\alpha _{i})

, which is equal to

{\frac {f^{(k)}(0)}{k!}}

. So you can find your answer using numerical differentiation. -- Meni Rosenfeld (talk) 20:33, 3 September 2011 (UTC)

(ec / Meni Rosenfeld, but a similar construction) I don't know what it's called, but your initial approach is close to the simplest way of doing it. One may have (in some cases) fewer calculations if one does it recursively

P_{m}^{n}=p_{n}P_{m-1}^{n-1}+(1-p_{n})P_{m}^{n-1}

where P_mⁿ is the probability of getting exactly m hits among the first n dice. — Arthur Rubin (talk) 20:39, 3 September 2011 (UTC)

So I use symbolic polynomial multiplication, Meni uses numerical or formal differentiation. — Arthur Rubin (talk) 20:42, 3 September 2011 (UTC)

Your method is better, I just missed the point that you only need

O(n^{2})

operations if you multiply out the polynomial one term at a time, or equivalently, using memoization in recursively calculating probabilities. In all cases numerical robustness issues should be considered. -- Meni Rosenfeld (talk) 09:21, 4 September 2011 (UTC)