Wikipedia:Reference desk/Archives/Mathematics/2011 December 23

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.

December 23

Help understanding an algorithm

I have to use an algorithm to solve a congruence and am struggling to understand what is going. Could someone please take a look and help me fill in the gaps?

Suppose that p − 1, where p is prime, is a power of 2 and let g be a primitive root mod p, i.e. a generator for the multiplicative group of non-zero residues mod p. To solve the congruence $x^{2}\equiv a{\pmod {p}}$we substitute $x\equiv g^{r}{\pmod {p}}$ where $r=\sum _{j\geq 0}r_{j}2^{j}$ with rj ∈ {0,1}. Raising each side of the original congruence to suitable powers it is possible to solve for the binary digits r0,r1,r2,... in turn. The first step is then listed as being used to determine r_0, whereby r_0 is equal to one if $a^{(p-1)/4}\equiv -1{\pmod {p}}$ or zero if $a^{(p-1)/4}\equiv 1{\pmod {p}}$.

My problem is that I don't see the motivation behind this algorithm. I don't understand how raising each side to appropriate powers gives you any information and I don't see where this expression for r_0 has come from, to name my most clearly defined issues. Thanks. 92.19.231.140 (talk) 14:29, 23 December 2011 (UTC)

As mentioned above, there are only a few primes known that are one more than a power of 2 so the algorithm would have very limited applicability. But in such a case the multiplicative group would be cyclic of order 2ⁿ. We want to find r so g^r=a, raise both sides to the power of 2^n-1. The lhs becomes g^2n-1r₀=(-1)^r₀, and the rhs is ±1. Now raise both sides to the power of 2^n-2 to get g^{2n-1r₁+2n-2r₀}=a2^n-2. If g^2n-2r₀=a2^n-2 then take r₁=0 else r₁=1. At each step if you know last k digits then raise both sides to 2^n-k-1; there are then two choices for the next digit and you can find which one is correct by evaluating. Once you have r, a solution to x²=a is g^r/2, with no solution if r is odd.--RDBury (talk) 15:56, 23 December 2011 (UTC)

That's very instructive, thank you. One question though; after raising both sides to the power 2^n-1, should the rhs not be g^{2n-2r₁+2n-1r₀}? 92.19.231.140 (talk) 17:05, 23 December 2011 (UTC)

Also, just to sum up the algorithm I want to work with, I start with g^r=a. I then raise to the power 2^n-1, giving g^2n-1r₀=(-1)^r₀ = (-1)^r₀, giving r₀ is one if we have minus one and zero if we have one. Then, at each subsequent stage, we raise the previous stage to the power 2^n-k-1 and test whether or not g^2n-k-1r_k-1=a^2n-k-1, taking r_k as zero if they are equal and one otherwise. Have I understood the procedure correctly? 92.19.231.140 (talk) 19:21, 23 December 2011 (UTC)

First question: The rhs would a^2n-1 which is ±1 since if you square it you get 1. Second question, that sound like what I have in mind. It might help to try an example, say p=17 and g=5, a=11.--RDBury (talk) 14:01, 24 December 2011 (UTC)

Tensegrity

What simple shape / construction contains a tensegrity of ten struts? Kittybrewster ☎ 21:53, 23 December 2011 (UTC)