Question

I'm stuck on this question, and a little lost a bit in...

Assume that p ≡ 3 (mod 4) and n ≡ x**2 (mod p). Given n and p, find one possible value of x.

They give a hint to go with p = 3 + 4k, and to utilize Euler's Criterion to multiply by n at some point. But apart from some trivial statements, I'm stuck without introducing new variables I can't get rid of...

Can anyone walk me through the first few steps of this?

Answer 1

By Euler's Criterion, I can infer the following...

n ** (p-1)/ 2 is congruent to 1 (mod p)
x ** (p-1) is congruent to 1 (mod p)

Answer 2

what does x**2 mean?

Answer 3

Please excuse the notation. By x**2, I was attempting to show \[x ^{2}\]

Answer 4

x^2, thats what i thougt but was trying to make sure

Answer 5

p ≡ 3 (mod 4)

p = 3 + 4k

n ≡ x^2 (mod p)

n = x^2 + pt

n = x^2 + (3 + 4k)t

n - (3 + 4k)t = x^2

for some given n and p

Answer 6

not too sure if that would apply tho

Answer 7

I can get this far, sadly. The introduction of the 't' variable drives me crazy, since now we don't know that...

Answer 8

t and k are just some arbitrary integers that are used in the definition of "modity"

Answer 9

Well \[x^2-a^2=(x-a)(x+a) => x^2=(x-a)(x+a)+a^2\]
I this this could help. I used it to find an x.

Answer 10

I translate for myself: "I think this could help."

Answer 11

i cant say im familiar with Euler's Criterion to implement it in this case :/

Answer 12

I don't think we need it.

Answer 13

perhaps, i hate it when hints lead you astray ;)

Answer 14

It is just a hint. We can ignore it or take it.

Answer 15

i dunno about that ... last time i ignored a hint i ended up getting married :/

Answer 16

I'm not familiar with euler's thingy ma-jigger either.

Answer 17

I could be wrong actually.

Answer 18

So I guess we are suppose to write x in terms of n and p.

Answer 19

with any luck n>p

Answer 20

n >= p that is

Answer 21

Ok. Maybe we need the hint.

Answer 22

Thanks for all the time you've given me. I'm not sure I'll ever find the answer the PSet wants me to, but I've mulled it over in my head for about two days now and reached the same conclusions that you have.

You've restored my faith that I'm not in over my head as far as this material is concerned.

Thanks!

Answer 23

Is this from a book?

Answer 24

It's from MIT OCW's Mathematics for Computer Science course. I could answer every question on the set but that with relative ease...

Answer 25

So we can't choose values for p and n that satisfy the congruences? It has to have some kinda general solution for x.

Answer 26

That's what it sounds like to me. I mean, I can satisfy it if I can choose n and p, according to those restrictions.

Answer 27

The Problem Sets, unfortunately, don't have solutions, so I may never know what the intention of the question was -- but they're usually pretty good about wording them.

Answer 28

If you ever find out the answer, I would like to see it.

Answer 29

Well, currently the tiles in my bathroom are covered in white-board marker with every possible equation / congruence I can think of with this... so maybe once I give up, I'll take a shower and see it staring at me in the face.

Answer 30

lol. That's interesting.

Answer 31

http://books.google.com/books?id=jQxRYd65LxIC&pg=PA103&lpg=PA103&dq=can+we+use+Euler's+Criterion+to+help+us+solve+mod+congruence&source=bl&ots=O0VjYZE0rh&sig=7CG4ZsL9x8KQ5_vkXbqoUkpWzDo&hl=en&sa=X&ei=UpJxUtHWA4mfkQe82oCIBw&ved=0CDYQ6AEwAg#v=onepage&q=can%20we%20use%20Euler's%20Criterion%20to%20help%20us%20solve%20mod%20congruence&f=false
I'm reading page 104 right now.

Answer 32

I would have never guessed that.

Answer 33

It's blocked here in China. Land of Piracy. Who'd have thought?

Answer 34

This page actually shows how to get it. I'm trying to follow it.

Answer 35

Holy moly! That page does show everything I need. I bow to your google-fu.

Answer 36

lol. so apparently we have blum primes here which I never heard of such a cute name for primes.
Do you understand it?

Answer 37

How did they get (p+1)/4 as the exponent?

Answer 38

Mulling that over as we speak. Is it because...

n^((p-1)/2) * n = n^(p+1)/2

And n is the square of n?

Answer 39

n is the square of x...

Answer 40

So since \[n^\frac{p-1}{2} \underline{\approx } 1 \mod p \]
and
\[x^2 \underline{\approx} n (\mod p)\]
then
\[x^2 \underline{\approx} n ( 1) (\mod p)\]
replacing this 1 here with
\[x^2 \underline{\approx} n (n^\frac{p-1}{2} ) (\mod p)\]
I guess this congruencey would still hold.
\[x^2 \underline{\approx} (n^\frac{p+1}{2} ) (\mod p)\]
Then somehow we just raise both sides to the 1/2 power to isolate x I guess.

Answer 41

That would give us the desired result. But I wonder if we can do what I did above. Like I wonder if my logic is right.

Answer 42

That's been my logic, as well...

Answer 43

Your hint did say to multiply by that.

Answer 44

I'm not sure how into Crypto you are, but I've found an interesting paper on the Blum-Blum-Shub Pseudo-Random Generator...

http://www.cs.miami.edu/~burt/learning/Csc609.062/docs/bbs.pdf

Answer 45

I do think crypto is interesting. I didn't get into as much of it as I wanted, well the math side anyways.

Answer 46

well neither side really
but i wanted the math part

Answer 47

I think number theory is a cool subject, but I just have an elementary grasp on some of it.

Answer 48

Yeah. I'm trying to "fix" the mistake of going into Liberal arts in my youth.