Message from @YourFundamentalTheorum

Discord ID: 503832804757602314


2018-10-22 06:56:33 UTC  

that is an isomorphism phi: F[x]/f1(x) -> F[x]/f2(x) where F[x] is the field of polynomials with coefficients in Z_q and f1(x) and f2(x) are irreducible polynomials in F[x]

2018-10-22 07:18:25 UTC  

@YourFundamentalTheorum by F[x]/f1(x) do you mean a quotient group? If so, what is the group you are doing F[x] modulo with? f1 doesn't generate a group unless I am missing something

2018-10-22 07:18:42 UTC  

@ThisIsChris quotient field

2018-10-22 07:19:06 UTC  

and F[x] is a field of polynomials in x with coefficients in Z_q

2018-10-22 07:24:17 UTC  

@YourFundamentalTheorum thanks. How about for an element of F[x]/f1 called G, take a representative g, phi(G) = the coset of g*f2/f1 . Need to prove that the coset is independent of the choice of representative g

2018-10-22 07:26:20 UTC  

the last part is a given.

2018-10-22 07:26:24 UTC  

On the right hand side I mean g times f2 divided by f1 in the normal sense for poly nomials

2018-10-22 07:26:44 UTC  

F[x]/f1(x) is usually represented by all the polynomials """"less than""""" f1(x)

2018-10-22 07:26:51 UTC  

a lesser degree than f1(x) that is

2018-10-22 07:27:59 UTC  

Hm, what happens in the three cases where f2 is higher, equal, or lesser degree than f1?

2018-10-22 07:28:10 UTC  

assume f1 and f2 are of the same degree

2018-10-22 07:28:16 UTC  

otherwise you don't have the same cardinalities

2018-10-22 07:28:20 UTC  

which means they can't be isomorphic

2018-10-22 07:28:42 UTC  

the Galois fields can't be isomorphic that is

2018-10-22 07:29:51 UTC  

Hm I think you can actually prove it if the degrees mismatch too. Since you assume the rep g has degree strictly less than f1, then g*f2/f1 should have degree strictly less than f2

2018-10-22 07:30:43 UTC  

yes you can prove that

2018-10-22 07:30:46 UTC  

it's quite easy actually

2018-10-22 07:31:14 UTC  

the degrees part htat is

2018-10-22 07:31:28 UTC  

we know the exact # of elements in F[x]/f1(x)

2018-10-22 07:31:35 UTC  

it's going to be q^n

2018-10-22 07:31:41 UTC  

i'm assuming q is prime btw

2018-10-22 07:32:18 UTC  

Sure since it's irreducible. Otherwise, hm...

2018-10-22 07:32:58 UTC  

If a polynomial has a non-prime degree, to guarantee reducibility you need to allow complex coefficients, right?

2018-10-22 07:33:48 UTC  

i don't think it matters what the degree of the polynomial is

2018-10-22 07:33:58 UTC  

like if it's prime or not

2018-10-22 07:34:06 UTC  

i think what matters are the coefficients

2018-10-22 07:34:20 UTC  

if you don't have prime coefficients, your polynomials stop being a field

2018-10-22 07:34:42 UTC  

the reason why F[x] is a field is because Z_q is a field when q is prime

2018-10-22 07:34:48 UTC  

if q is not prime, Z_q is not a field

2018-10-22 07:35:01 UTC  

and therefore F[x] is not guaranteed to be a field

2018-10-22 07:35:24 UTC  

Why is Z_q not a field when q is, say, 4?

2018-10-22 07:35:27 UTC  

the very basic example is that say if you have Z_4, the polynomial "2" does not have a multiplicative inverse

2018-10-22 07:35:48 UTC  

Ohh

2018-10-22 07:35:53 UTC  

Neat

2018-10-22 07:35:54 UTC  

Z_4 is not a field because 2 does not have a multiplicative inverse

2018-10-22 07:36:10 UTC  

Yeah haha been a while

2018-10-22 07:36:12 UTC  

and since Z_q is a subfield of F_q[x]

2018-10-22 07:36:26 UTC  

yeah I've literally pullen out my abstract alg. book out today

2018-10-22 07:36:32 UTC  

i need some cryptography knowledge from it

2018-10-22 07:36:43 UTC  

i learned all of this again today 😛

2018-10-22 07:39:45 UTC  

That's neat. I enjoyed abstract algebra but mostly only needed the linear algebra part since then (11 years ago). Rotation groups and some other stuff relevant to geometry, but not much more. Cryptography seems interesting, we did cover RSA at some point, I only remember the main idea, that factoring is hard 😁