[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: [email protected]*Subject*: Re: Q's on Number Theory/Quadriatic Residues*From*: [email protected] (Hadmut Danisch)*Date*: Mon, 14 Aug 1995 14:12:49 +0200*Cc*: [email protected]*Sender*: [email protected]

> >Bzzt! Try Again. If you use bc, you will notice that 9^2 mod 35 == 11 > >and 8^2 mod 35 == 29... You should go take your number theory class! > > Definitely. Is there an easy way to get from the 29 to the 8? I can see how > it goes > the other way, but what I didnt' see was how, if given 29, I could get the > 8? (Euclid's?) You can get the square root mod p (p prime) easily, if p+1 is divisible by 4. You (should) know that x ^ (p-1) equals to 1 mod p for every given x > 0. Therefore x ^ ( (p-1)/2 ) is either +1 or -1 mod p. Now you have a given x^2 and want to find x (one of both, there are two..) ( x^2 ) ^ ((p+1)/4) = x ^ ( (p+1)/2 ) = x * x ^( (p-1)/2 ) = +/- x . If p+1 is not divisible by 4, it's a little bit more difficult... In your example, 35+1 is luckily divisible by 4. But this doesn't help, because 35 is not a prime. 35 = 5*7 , you can use the chinese remainder and find the root mod 5 and the root mod 7. 7+1 is divisible by 4, you can use the trick: ( 8 ^ 2 ) ^ 2 mod 7 = +/- 1. (which is correct since 8 = 1 mod 7); +1 and -1 are the roots of (8^2) modulo 7. Modulo 5 we can't use the trick, but we guess the roots of (8^2) = 4 mod 5 as 2 and 3. Back to the main problem: You want to have the root of (8^2) mod 35. We found the roots 1 and 6 as roots of (8^2) mod 7 and the roots 2 and 3 as roots of (8^2) mod 5. Now solve the Chinese remainder for each possible pair (1,2), (1,3), (6,2), (6,3), and you get the _four_ roots of (8^2) mod 35. Two of them will be 8 and -8, and there are another two. BTW: This is one way to do a mental coin flipping. Hadmut :-)

- Prev by Date:
**votelink - some discussions on Phil Z & ITAR** - Next by Date:
**premail www interface** - Prev by thread:
**Re: Q's on Number Theory/Quadriatic Residues** - Next by thread:
**Re: Q's on Number Theory/Quadriatic Residues** - Index(es):