Wikipedia:Reference desk/Archives/Mathematics/2011 September 2

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an 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)