The Math Thread - Page 28

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?

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?

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!

On April 29 2019 07:39 travis wrote:
you are saying that i likely am interpreting the problem correctly then,. though?

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

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?

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...)

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

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.

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.

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

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