# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Author Message
Antrax
ESL Student

 Posted: Fri Mar 19, 2004 12:08 pm    Post subject: 1 Has to do with finding square roots modulo N=4k+1. The algorithm we were presented with relied on the ability to find a polynomial GCD of two polynoms, modulo something. How does that work, precisely? I tried using Euclid's algorithm, but you get residues that are of a higher degree than that of the number you're dividing, which hints the algorithm won't necessarily ever stop, etc. How are you supposed to do it? Antrax ------------------ "Look, that's why there's rules, understand? So that you think before you break 'em" - Lu-Tze, Thief of Time
zeek
Daedalian Member

Posted: Fri Mar 19, 2004 2:05 pm    Post subject: 2

 Quote: I tried using Euclid's algorithm, but you get residues that are of a higher degree than that of the number you're dividing

That doesn't make sense to me. When dividing one poly into another, the remainder should always have a lower degree than the divisor. If it doesn't you're not finished dividing.
Antrax
ESL Student

 Posted: Fri Mar 19, 2004 2:17 pm    Post subject: 3 I'll give you the example: find the GCD of X^6-1 and X^2-x+7 (mod 13). So we'll get: x^6-1 = x^4(x^2-x+7)+x^5-7x^4-1 and now we'll have to divide x^2-x+7 with x^5-7x^4-1, which leads to negative degrees, which contradicts the proof that the algorithms stops after log(a) of steps, etc. Antrax ------------------ "Look, that's why there's rules, understand? So that you think before you break 'em" - Lu-Tze, Thief of Time
zeek
Daedalian Member

 Posted: Fri Mar 19, 2004 2:25 pm    Post subject: 4 Like I said, you're not finished dividing. (x^2-x+7) can still divide into (x^5-7x^4-1).
zeek
Daedalian Member

 Posted: Fri Mar 19, 2004 2:31 pm    Post subject: 5 If I didn't screw this up... x^6 - 1 = (x^2-x+7)(x^4+x^3-6x^2-13x+29) + (120x-204)
Antrax
ESL Student

 Posted: Fri Mar 19, 2004 2:41 pm    Post subject: 6 How do you find the GCD from that? Antrax ------------------ "Look, that's why there's rules, understand? So that you think before you break 'em" - Lu-Tze, Thief of Time
zeek
Daedalian Member

 Posted: Fri Mar 19, 2004 2:47 pm    Post subject: 7 Well if my math was right, you then have to divide (120x-204) into (x^2-x+7). Since (120x-204) = 12(10x-17), it's easy to see they have no common factor, so the GCD is 1.
Antrax
ESL Student

 Posted: Fri Mar 19, 2004 3:08 pm    Post subject: 8 But but, the GCD is (x-3). x^2-x+7 = (x-3)(x+2) (mod 13) x^6 - 1 = (x-3)(x^2+6x+9)(x^3+1) (mod 13) Antrax ------------------ "Look, that's why there's rules, understand? So that you think before you break 'em" - Lu-Tze, Thief of Time
zeek
Daedalian Member

 Posted: Fri Mar 19, 2004 3:17 pm    Post subject: 9 Oh, I see where you going with this. mod 13. How about this: 120x-204 = 120(x-3) + 12*13, so 120x-204 = (x-3)120 (mod 13) x^2-x+7 = (x-3)(x+2) (mod 13)
zeek
Daedalian Member

 Posted: Fri Mar 19, 2004 3:32 pm    Post subject: 10 Here's an approach. Since 120 and x aren't divisible by 13, you can do.. 120(x^2-x+7) - x(120x-204) = 84x + 840 = 84(x+10) and (x+10) = (x-3) (mod 13)
kevinatilusa
Daedalian Member

 Posted: Sat Mar 20, 2004 5:33 am    Post subject: 11 If you were working in the real numbers and you had ax^2+bx+c and dx+e, you would take as your next step (ax^2+bx+c)-(a/d)(x)(dx+e) to eliminate the quadratic term. When we're working mod 13, we can do a similar thing, but just take a*d^(-1) instead of a/d (where d^(-1) is such that d*(d^(-1))=1 (mod 13), which you can find by the old-fashioned Euclidean algorithm).
lurker
Guest

 Posted: Sun Mar 21, 2004 4:56 pm    Post subject: 12 Why work with big numbers? Being in 'mod 13' already... 120x-204 is simply 3x+4, and so x2-x+7=(3x+4)*(9x+5) [having the table of multiplication in Z13 surely helps!]. Of course, myGCD = 3x+4 = 3x+4+13+13 = 3x+30 = 3(x+10) ~ x+10 = x+10-13 = x-3 = yourGCD...
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersAnonymousAntraxkevinatilusazeek Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum