The Math Thread - Page 28
Forum Index > General Forum |
enigmaticcam
United States280 Posts
| ||
Ciaus_Dronu
South Africa1848 Posts
On April 25 2019 04:46 enigmaticcam wrote: Thank you! I'll spend some time reading through the links you posted. My linear algebra is limited, so will take me some time to understand what they're saying. For considering the vectors involved, it is easier to imagine that your x slope and the mirror slope cross at the origin (slopes are invariant under translation). If you only care about calculating the slope after reflection, this will make everything muuuuch easier to calculate. | ||
Deleted User 3420
24492 Posts
Let's start it off with some question from my crypto class. It says, Determine the points on the elliptic curve E : y^2 = x^3 + 2x + 1 over Z_11 How many points are on this curve So, I have never quite done something like this before. Does this mean that both y, and x need to be in Z_11? And thus, if x^3 + 2x + 1 is not a perfect square, then the corresponding point will not be on the curve...? So do I need to simply solve for y^2 for x=0 to 10, and only keep the ones that are perfect squares and then solve for y? Furthermore, when I solve for y^2, do I do modulus to each x term, or do I only do modulus to the entire equation? Thanks! | ||
Simberto
Germany11032 Posts
Usually if you say "a curve over Z_11", you mean that both y and x are €Z_11 Furthermore, when I solve for y^2, do I do modulus to each x term, or do I only do modulus to the entire equation? Doesn't matter, both are equivalent. So you should probably modulus whenever you get a number larger than 10. a(mod11) + b(mod11) = (a+b) (mod11) And my guess would indeed be to simply get all the possible solutions for both sides of the equations (Try 0-10), and see which numbers are both. But there might be another, smarter way to do this. | ||
Battleship789
United States415 Posts
On April 28 2019 08:42 travis wrote: It's that time of year where my procrastination catches up with me and it starts getting near finals and I realize I don't understand anything about any of my classes. So this thread will probably get flooded with questions from yours truly. Let's start it off with some question from my crypto class. It says, Determine the points on the elliptic curve E : y^2 = x^3 + 2x + 1 over Z_11 How many points are on this curve So, I have never quite done something like this before. Does this mean that both y, and x need to be in Z_11? Yes. You are solving the given algebraic equation, but the algebraic structure you are working with is Z_11 instead of the real or complex numbers. Luckily, Z_11 is a field so it shouldn't be too annoying to solve the equation. And thus, if x^3 + 2x + 1 is not a perfect square, then the corresponding point will not be on the curve...? A perfect square in Z_11, to be precise (which may or may not correspond to perfect squares in the reals.) But yes, that is correct. So do I need to simply solve for y^2 for x=0 to 10, and only keep the ones that are perfect squares and then solve for y? Yep! There might be an quicker way to solve it (I can't think of any off the top of my head), but that will certainly get the job done. Furthermore, when I solve for y^2, do I do modulus to each x term, or do I only do modulus to the entire equation? Thanks! It shouldn't matter if you take the modulus for each term individually or over the entire equation because modular arithmetic is defined by using representatives: [x]+[y] = [x+y] and [x]*[y] = [x*y] | ||
Deleted User 3420
24492 Posts
here is another problem from crypto class. maybe you guys can just help me understand what the question is actually asking. it says Can the following be solved in polynomial time? Given a prime p, a value x in Z*_(p-1), and y := g^x (mod p) where g is a uniform value from Z*_(p-1), find g, ie, compute y^(1/x) (mod p). I am not really understanding this problem because it sounds like we are given p, x, y. So then we can compute the answer in constant time.... by just plugging in the numbers... What is it actually asking? lol | ||
mahrgell
Germany3854 Posts
Just take some random 3 digit prime, and pick x,y somehow randomly. Let's just say p, = 197, x = 146, y = 123. If you can just plug in the numbers, this should take you maximum 20 seconds to solve. (I didn't check the solution.) | ||
Deleted User 3420
24492 Posts
but i def do think this is polynomial time solvable so i guess i will get to work you are saying that i likely am interpreting the problem correctly then,. though? edit: so, as an actual answer to the question, can't we literally just check every prime g, and then do g^x mod p? it's awful but that would be polynomial.. But maybe the assumption is we don't know how big our set of primes is, and we don't have a list of primes edit2: ok now i think it isn't always solvable in polynomial time and is analogous to the discrete logarithm problem | ||
mahrgell
Germany3854 Posts
On April 29 2019 07:39 travis wrote: you are saying that i likely am interpreting the problem correctly then,. though? I was pointing you at the fact, that your initial interpretation doesn't survive any random example. (and that it would probably not asked too much to at least try it once...) | ||
Acrofales
Spain17187 Posts
On April 29 2019 07:39 travis wrote: ok so constant time was hyperbole and no im not actually sure but i def do think this is polynomial time solvable so i guess i will get to work you are saying that i likely am interpreting the problem correctly then,. though? edit: so, as an actual answer to the question, can't we literally just check every prime g, and then do g^x mod p? it's awful but that would be polynomial.. But maybe the assumption is we don't know how big our set of primes is, and we don't have a list of primes edit2: ok now i think it isn't always solvable in polynomial time and is analogous to the discrete logarithm problem Seems to me you can do this in polynomial time and your initial edit is correct. You know p, y and x. So even if there is no constant time algorithm for finding the root in modular arithmetic, you can definitely do it in polynomial time: Just run through all values i \in Z*_(p-1) and see if i^x = y (mod p). The check is constant time, so your algorithm overall is O(p). So why the edit2? | ||
Deleted User 3420
24492 Posts
On April 29 2019 17:28 Acrofales wrote: Seems to me you can do this in polynomial time and your initial edit is correct. You know p, y and x. So even if there is no constant time algorithm for finding the root in modular arithmetic, you can definitely do it in polynomial time: Just run through all values i \in Z*_(p-1) and see if i^x = y (mod p). The check is constant time, so your algorithm overall is O(p). So why the edit2? Honestly it didn't seem right to just say "check every prime", im worried this isn't what they want as the solution.... but I suppose it is polynomial to verify a value is prime as well, so it's still polynomial, so i'll go for it On April 29 2019 14:19 mahrgell wrote: I was pointing you at the fact, that your initial interpretation doesn't survive any random example. (and that it would probably not asked too much to at least try it once...) Well in fairness, one would need to come up with an example that has primes and an integer solution, which your random example didn't. but your point was valid anyways | ||
Deleted User 3420
24492 Posts
edited the post above this now | ||
Simberto
Germany11032 Posts
| ||
Deleted User 3420
24492 Posts
| ||
Acrofales
Spain17187 Posts
On April 29 2019 21:46 travis wrote: Honestly it didn't seem right to just say "check every prime", im worried this isn't what they want as the solution.... but I suppose it is polynomial to verify a value is prime as well, so it's still polynomial, so i'll go for it Well in fairness, one would need to come up with an example that has primes and an integer solution, which your random example didn't. but your point was valid anyways Maybe I'm missing something, but you don't have to check primes? You're given the prime, right? So lets say you are given: p=29 y=6 x=2 Now the assignment is to find g, with g^2 = 6 (mod 29). Right? So we don't care about primes: we have the one we need. We just need to find g. So lets define f(x) = x^2 (mod 29) we start: i=1 f(i) = 1 i = 2 f(i) = 4 i = 3 f(i) = 9 ... i = 8 f(i) = 6. Hurrah! Worst case, you get to i = p - 1 (in this case 28) before you find g. So complexity class is O(p). E: btw, I am not claiming this is the fastest algorithm to do it. There may actually be faster ones: my modular arithmetic is very rusty. I'm just showing an upper bound of linear time. There may be a constant time algorithm for finding the modular root and I just don't know it. | ||
Deleted User 3420
24492 Posts
| ||
Oshuy
Netherlands529 Posts
On April 29 2019 23:33 Acrofales wrote: Maybe I'm missing something, but you don't have to check primes? You're given the prime, right? So lets say you are given: p=29 y=6 x=2 Now the assignment is to find g, with g^2 = 6 (mod 29). Right? So we don't care about primes: we have the one we need. We just need to find g. So lets define f(x) = x^2 (mod 29) we start: i=1 f(i) = 1 i = 2 f(i) = 4 i = 3 f(i) = 9 ... i = 8 f(i) = 6. Hurrah! Worst case, you get to i = p - 1 (in this case 28) before you find g. So complexity class is O(p). E: btw, I am not claiming this is the fastest algorithm to do it. There may actually be faster ones: my modular arithmetic is very rusty. I'm just showing an upper bound of linear time. There may be a constant time algorithm for finding the modular root and I just don't know it. You should take the complexity of the modular exponentiation (f(x)) into account, but of course it remains polynomial. | ||
Deleted User 3420
24492 Posts
so here comes a wave of questions. please help me understand how to do this stuff first question says: let n >= 5. It can be shown that the only normal subgroups of S_n are {(1)}, A_n, and S_n a.) for each normal subgroup N of S_n above, describe what the quotient group S_n / N is isomorphic to. So first, the extent of my understanding: A normal subgroup H of S_n is a subgroup of S_n in which gH = Hg (left cosets and right cosets are the same) for g in S_n A quotient group is a normal subgroup... but that's about as far as I understand it I see a rule (aN)(bN) = (abN) Is it the case here that a,b are cosets of G, and then the quotient group is abN which arises from the product of the group operation between a and b? So then back to the question of {(1)}, A_n, and S_n in S_n I don't really know how to solve what these quotient groups are isomorphic to What kind of steps do I take? I do have guesses though, I think for (1) the answer is S_n, for A_n the answer is Z_2, and for S_n the answer is the identity | ||
Mafe
Germany5917 Posts
On May 01 2019 05:20 travis wrote: alright, im a bit behind in my abstract algebra class and now im lost as heck so here comes a wave of questions. please help me understand how to do this stuff first question says: So first, the extent of my understanding: A normal subgroup H of S_n is a subgroup of S_n in which gH = Hg (left cosets and right cosets are the same) for g in S_n A quotient group is a normal subgroup... but that's about as far as I understand it I see a rule (aN)(bN) = (abN) Is it the case here that a,b are cosets of G, and then the quotient group is abN which arises from the product of the group operation between a and b? So then back to the question of {(1)}, A_n, and S_n in S_n I don't really know how to solve what these quotient groups are isomorphic to What kind of steps do I take? I do have guesses though, I think for (1) the answer is S_n, for A_n the answer is Z_2, and for S_n the answer is the identity It's been a while, but here's what I recall: -Iirc there is a rather trivial way to answer this question by calculating the number of elements of S_n / N, though this does not really provide any further understanding. -I don think it makes sense to say that a "quotient subgroups is a normal subgroup". I mean, a quotient G/H generally isnt even a subset of G (though often it can be identified with one, but I would not expect that this identification automatically come with a group structure). | ||
Acrofales
Spain17187 Posts
On May 01 2019 05:20 travis wrote: alright, im a bit behind in my abstract algebra class and now im lost as heck so here comes a wave of questions. please help me understand how to do this stuff first question says: So first, the extent of my understanding: A normal subgroup H of S_n is a subgroup of S_n in which gH = Hg (left cosets and right cosets are the same) for g in S_n A quotient group is a normal subgroup... but that's about as far as I understand it I see a rule (aN)(bN) = (abN) Is it the case here that a,b are cosets of G, and then the quotient group is abN which arises from the product of the group operation between a and b? So then back to the question of {(1)}, A_n, and S_n in S_n I don't really know how to solve what these quotient groups are isomorphic to What kind of steps do I take? I do have guesses though, I think for (1) the answer is S_n, for A_n the answer is Z_2, and for S_n the answer is the identity Not quite sure on the algebra, but any question of "prove that for all n > something..." invites a proof through induction, so prove it for n=5 and then assume for n and prove for n+1. | ||
| ||