Anki Deck Changes

Commit: 897fa4d8 - finish cards for dm chapter 5

Author: obrhubr <obrhubr@gmail.com>

Date: 2025-12-22T10:22:31+01:00

Changes: 21 note(s) changed (19 added, 2 modified, 0 deleted)

ℹ️ Cosmetic Changes Hidden: 1 note(s) had formatting-only changes and are not shown below

Note 1: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: E3nG0q}H>n
modified

Before

Front

ETH::1._Semester::DiskMat::5._Algebra::8._Finite_Fields::1._The_Ring_F[x]ₘ₍ₓ₎

Is \(F[x]_{m(x)}\) a monoid, group, ring, field?

Back

ETH::1._Semester::DiskMat::5._Algebra::8._Finite_Fields::1._The_Ring_F[x]ₘ₍ₓ₎

Is \(F[x]_{m(x)}\) a monoid, group, ring, field?

Lemma 5.35: \(F[x]_{m(x)}\) is a ring with respect to addition and multiplication modulo \(m(x)\).

After

Front

ETH::1._Semester::DiskMat::5._Algebra::8._Finite_Fields::1._The_Ring_F[x]ₘ₍ₓ₎

Is \(F[x]_{m(x)}\) a monoid, group, ring, field?

Back

ETH::1._Semester::DiskMat::5._Algebra::8._Finite_Fields::1._The_Ring_F[x]ₘ₍ₓ₎

Is \(F[x]_{m(x)}\) a monoid, group, ring, field?

Lemma 5.35: \(F[x]_{m(x)}\) is a commutative ring with respect to addition and multiplication modulo \(m(x)\).

Field-by-field Comparison
Field Before After
Back <p><strong>Lemma 5.35</strong>: \(F[x]_{m(x)}\) is a <strong>ring</strong> with respect to addition and multiplication modulo \(m(x)\).</p> <p><b>Lemma 5.35</b>: \(F[x]_{m(x)}\) is a <b>commutative ring</b> with respect to addition and multiplication modulo \(m(x)\).</p>
Tags: ETH::1._Semester::DiskMat::5._Algebra::8._Finite_Fields::1._The_Ring_F[x]ₘ₍ₓ₎

Note 2: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: LM9=
added

Previous

Note did not exist

New Note

Front

ETH::1._Semester::DiskMat::4._Number_Theory::6._Application:_Diffie-Hellman_Key-Agreement
DHKE selects two public values:
  1. a large prime \(p\)
  2. basis \(g\) which is then exponentiated

Back

ETH::1._Semester::DiskMat::4._Number_Theory::6._Application:_Diffie-Hellman_Key-Agreement
DHKE selects two public values:
  1. a large prime \(p\)
  2. basis \(g\) which is then exponentiated
Field-by-field Comparison
Field Before After
Text DHKE selects two public values:<br><ol><li>{{c1:: a large prime&nbsp;\(p\)}}</li><li>{{c2:: basis&nbsp;\(g\)&nbsp;which is then exponentiated}}</li></ol>
Tags: ETH::1._Semester::DiskMat::4._Number_Theory::6._Application:_Diffie-Hellman_Key-Agreement

Note 3: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: uK|j,XZw5[
added

Previous

Note did not exist

New Note

Front

ETH::1._Semester::DiskMat::4._Number_Theory::6._Application:_Diffie-Hellman_Key-Agreement
For DHKE, both Alice and Bob choose \(x_A, x_B\) (their private keys) at random.
They then compute {{c2:: \(y_A := R_p(g^{x_A})\) and with \(y_B\)analogously, which are their public keys}} which is sent over the network to their partner.
The other {{c3:: then exponentiates by their private key to get the shared key \(k_{AB} \equiv_p y_B^{x_A} \equiv_p g^{x_B \cdot x_A} \equiv_p y_A^{x_B}\)}}.

Back

ETH::1._Semester::DiskMat::4._Number_Theory::6._Application:_Diffie-Hellman_Key-Agreement
For DHKE, both Alice and Bob choose \(x_A, x_B\) (their private keys) at random.
They then compute {{c2:: \(y_A := R_p(g^{x_A})\) and with \(y_B\)analogously, which are their public keys}} which is sent over the network to their partner.
The other {{c3:: then exponentiates by their private key to get the shared key \(k_{AB} \equiv_p y_B^{x_A} \equiv_p g^{x_B \cdot x_A} \equiv_p y_A^{x_B}\)}}.
Field-by-field Comparison
Field Before After
Text For DHKE, both Alice and Bob {{c1:: choose&nbsp;\(x_A, x_B\)&nbsp;(their private keys) at random}}.<br>They then compute {{c2::&nbsp;\(y_A := R_p(g^{x_A})\)&nbsp;and with&nbsp;\(y_B\)analogously, which are their public keys}} which is {{c2:: sent over the network to their partner}}.<br>The other {{c3:: then exponentiates by their private key to get the shared key&nbsp;\(k_{AB} \equiv_p y_B^{x_A} \equiv_p g^{x_B \cdot x_A} \equiv_p y_A^{x_B}\)}}.
Tags: ETH::1._Semester::DiskMat::4._Number_Theory::6._Application:_Diffie-Hellman_Key-Agreement

Note 4: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: tuHe#n^N^#
added

Previous

Note did not exist

New Note

Front

ETH::1._Semester::DiskMat::4._Number_Theory::6._Application:_Diffie-Hellman_Key-Agreement
DHKE works because?

Back

ETH::1._Semester::DiskMat::4._Number_Theory::6._Application:_Diffie-Hellman_Key-Agreement
DHKE works because?
The discrete logarithm problem is hard!

That is, it's hard to find \(x_A\) from \(g^{x_A} \mod p\), knowing \(g\).
Field-by-field Comparison
Field Before After
Front DHKE works because?
Back The&nbsp;<b>discrete logarithm</b>&nbsp;problem is hard!<br><br>That is, it's hard to find&nbsp;\(x_A\)&nbsp;from&nbsp;\(g^{x_A} \mod p\), knowing&nbsp;\(g\).
Tags: ETH::1._Semester::DiskMat::4._Number_Theory::6._Application:_Diffie-Hellman_Key-Agreement

Note 5: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: oKjV}w*z+.
added

Previous

Note did not exist

New Note

Front

ETH::1._Semester::DiskMat::5._Algebra::4._Application:_RSA_Public-Key_Encryption::1._eth_Roots
In a finite group the function \(x \rightarrow x^e\) is a bijection if  \(e\) coprime to \(|G|\).
For \(x^e = y\), the inverse of \(y\) is the unique \(e\)th root \(x = y^d\).

Back

ETH::1._Semester::DiskMat::5._Algebra::4._Application:_RSA_Public-Key_Encryption::1._eth_Roots
In a finite group the function \(x \rightarrow x^e\) is a bijection if  \(e\) coprime to \(|G|\).
For \(x^e = y\), the inverse of \(y\) is the unique \(e\)th root \(x = y^d\).
Field-by-field Comparison
Field Before After
Text In a finite group the function&nbsp;\(x \rightarrow x^e\)&nbsp;is {{c1:: a bijection}} if {{c2::&nbsp;\(e\)&nbsp;coprime to&nbsp;\(|G|\)}}.<br>For&nbsp;\(x^e = y\), the inverse of&nbsp;\(y\)&nbsp;is {{c3:: the <b>unique</b>&nbsp;\(e\)th root&nbsp;\(x = y^d\)}}.
Tags: ETH::1._Semester::DiskMat::5._Algebra::4._Application:_RSA_Public-Key_Encryption::1._eth_Roots

Note 6: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: g)zJH(^4f3
added

Previous

Note did not exist

New Note

Front

ETH::1._Semester::DiskMat::5._Algebra::4._Application:_RSA_Public-Key_Encryption::1._eth_Roots
In a finite group of order \(|G|\), for \(x^e = y\), \(d\) is the inverse such that \(y^d = x\) iff:

Back

ETH::1._Semester::DiskMat::5._Algebra::4._Application:_RSA_Public-Key_Encryption::1._eth_Roots
In a finite group of order \(|G|\), for \(x^e = y\), \(d\) is the inverse such that \(y^d = x\) iff:
\(ed \equiv_{|G|} 1\), i.e. \(d\) is the multiplicative inverse of \(e\) modulo \(|G|\).

Proof
  1. \(ed = k \cdot |G| + 1\) (multiplicative inverse)
  2. \((x^e)^d = x^{ed} = x^{k\cdot |G| + 1}\)
  3. \((x^{|G|})^k \cdot x = 1^k \cdot x = x\)
Thus this returns \(x\).
Field-by-field Comparison
Field Before After
Front In a finite group of order&nbsp;\(|G|\), for&nbsp;\(x^e = y\),&nbsp;\(d\)&nbsp;is the inverse such that&nbsp;\(y^d = x\)&nbsp;iff:
Back \(ed \equiv_{|G|} 1\), i.e.&nbsp;\(d\)&nbsp;is the multiplicative inverse of&nbsp;\(e\)&nbsp;modulo&nbsp;\(|G|\).<br><br><b>Proof</b><br><ol><li>\(ed = k \cdot |G| + 1\)&nbsp;(multiplicative inverse)</li><li>\((x^e)^d = x^{ed} = x^{k\cdot |G| + 1}\)</li><li>\((x^{|G|})^k \cdot x = 1^k \cdot x = x\)</li></ol><div>Thus this returns \(x\).</div>
Tags: ETH::1._Semester::DiskMat::5._Algebra::4._Application:_RSA_Public-Key_Encryption::1._eth_Roots

Note 7: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: kJ1TdT+N(|
added

Previous

Note did not exist

New Note

Front

ETH::1._Semester::DiskMat::5._Algebra::4._Application:_RSA_Public-Key_Encryption::1._eth_Roots
Why does RSA work, i.e. why can't we break it?

Back

ETH::1._Semester::DiskMat::5._Algebra::4._Application:_RSA_Public-Key_Encryption::1._eth_Roots
Why does RSA work, i.e. why can't we break it?
Finding the \(e\)-th root is a hard problem (we have to try all possibilities) as long as we don't know the group order \(|G|\).

If we do, we can find d using the extended euclidean algorithm.
Field-by-field Comparison
Field Before After
Front Why does RSA work, i.e. why can't we break it?
Back Finding the&nbsp;\(e\)-th root is a hard problem (we have to try all possibilities)&nbsp;<b>as long as we don't know the group order&nbsp;</b>\(|G|\).<br><br>If we do, we can find d using the extended euclidean algorithm.
Tags: ETH::1._Semester::DiskMat::5._Algebra::4._Application:_RSA_Public-Key_Encryption::1._eth_Roots

Note 8: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: B7%
added

Previous

Note did not exist

New Note

Front

ETH::1._Semester::DiskMat::5._Algebra::4._Application:_RSA_Public-Key_Encryption::2._Description_of_RSA
Describe the RSA protocol:
  1. Alice generates primes \(p\) and \(q\)
  2. Set \(n = pq\) and \(f = \varphi(n) = (p - 1)(q - 1)\) 
  3. {{c3:: Select \(e\): \(d \equiv_f e^{-1}\) the modular inverse (decryption)}}
  4. Send \(n\) and \(e\) to Bob
  5. {{c5:: Bob encrypts the plaintext \(m \in \{1, \dots, n -1 \}\) (unique modulo \(n\)) \(c = R_n(m^e)\) and sends it}}
  6. Alice decrypts using \(m = R_n(c^d)\) 

Back

ETH::1._Semester::DiskMat::5._Algebra::4._Application:_RSA_Public-Key_Encryption::2._Description_of_RSA
Describe the RSA protocol:
  1. Alice generates primes \(p\) and \(q\)
  2. Set \(n = pq\) and \(f = \varphi(n) = (p - 1)(q - 1)\) 
  3. {{c3:: Select \(e\): \(d \equiv_f e^{-1}\) the modular inverse (decryption)}}
  4. Send \(n\) and \(e\) to Bob
  5. {{c5:: Bob encrypts the plaintext \(m \in \{1, \dots, n -1 \}\) (unique modulo \(n\)) \(c = R_n(m^e)\) and sends it}}
  6. Alice decrypts using \(m = R_n(c^d)\) 
Field-by-field Comparison
Field Before After
Text Describe the RSA protocol:<br><ol><li>{{c1:: Alice generates primes&nbsp;\(p\)&nbsp;and&nbsp;\(q\)}}</li><li>{{c2:: Set&nbsp;\(n = pq\)&nbsp;and&nbsp;\(f = \varphi(n) = (p - 1)(q - 1)\)&nbsp;}}</li><li>{{c3:: Select&nbsp;\(e\):&nbsp;\(d \equiv_f e^{-1}\)&nbsp;the modular inverse (decryption)}}</li><li>{{c4:: Send&nbsp;\(n\)&nbsp;and&nbsp;\(e\)&nbsp;to Bob}}</li><li>{{c5:: Bob encrypts the plaintext&nbsp;\(m \in \{1, \dots, n -1 \}\)&nbsp;(unique modulo \(n\))&nbsp;\(c = R_n(m^e)\)&nbsp;and sends it}}</li><li>{{c6:: Alice decrypts using&nbsp;\(m = R_n(c^d)\)}}&nbsp;</li></ol>
Tags: ETH::1._Semester::DiskMat::5._Algebra::4._Application:_RSA_Public-Key_Encryption::2._Description_of_RSA

Note 9: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: i
added

Previous

Note did not exist

New Note

Front

ETH::1._Semester::DiskMat::5._Algebra::2._Monoids_and_Groups
A monoid has the following properties:

Back

ETH::1._Semester::DiskMat::5._Algebra::2._Monoids_and_Groups
A monoid has the following properties:
  • closure
  • associativity
  • identity
Field-by-field Comparison
Field Before After
Front A&nbsp;<b>monoid</b>&nbsp;has the following properties:
Back <ul><li>closure</li><li>associativity</li><li>identity</li></ul>
Tags: ETH::1._Semester::DiskMat::5._Algebra::2._Monoids_and_Groups

Note 10: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: rI[60?4iFu
added

Previous

Note did not exist

New Note

Front

ETH::1._Semester::DiskMat::5._Algebra::2._Monoids_and_Groups
A group has the following properties:

Back

ETH::1._Semester::DiskMat::5._Algebra::2._Monoids_and_Groups
A group has the following properties:
  • closure
  • associativity
  • identity
  • inverse
Field-by-field Comparison
Field Before After
Front A&nbsp;<b>group</b>&nbsp;has the following properties:
Back <ul><li>closure</li><li>associativity</li><li>identity</li><li>inverse</li></ul>
Tags: ETH::1._Semester::DiskMat::5._Algebra::2._Monoids_and_Groups

Note 11: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: s?tB!9azRK
added

Previous

Note did not exist

New Note

Front

ETH::1._Semester::DiskMat::5._Algebra::2._Monoids_and_Groups
An abelian group has the following properties:

Back

ETH::1._Semester::DiskMat::5._Algebra::2._Monoids_and_Groups
An abelian group has the following properties:
  • closure
  • associativity
  • identity
  • inverse
  • commutative
Field-by-field Comparison
Field Before After
Front An <b>abelian group</b>&nbsp;has the following properties:
Back <ul><li>closure</li><li>associativity</li><li>identity</li><li>inverse</li><li>commutative</li></ul>
Tags: ETH::1._Semester::DiskMat::5._Algebra::2._Monoids_and_Groups

Note 12: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: EOU=o(/Tm!
added

Previous

Note did not exist

New Note

Front

ETH::1._Semester::DiskMat::5._Algebra::5._Rings_and_Fields
A ring has the following properties:

Back

ETH::1._Semester::DiskMat::5._Algebra::5._Rings_and_Fields
A ring has the following properties:
Additive Group:
  • closure
  • associativity
  • identity
  • inverse
Multiplicative group:
  • closure
  • associativity
  • distributivity
Field-by-field Comparison
Field Before After
Front A&nbsp;<b>ring</b> has the following properties:
Back Additive Group:<br><ul><li>closure</li><li>associativity</li><li>identity</li><li>inverse</li></ul><div>Multiplicative group:</div><div></div><ul><li>closure</li><li>associativity</li><li>distributivity</li></ul>
Tags: ETH::1._Semester::DiskMat::5._Algebra::5._Rings_and_Fields

Note 13: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: Jyob1i~-v!
added

Previous

Note did not exist

New Note

Front

ETH::1._Semester::DiskMat::5._Algebra::5._Rings_and_Fields
A commutative ring has the following properties:

Back

ETH::1._Semester::DiskMat::5._Algebra::5._Rings_and_Fields
A commutative ring has the following properties:
Additive Group:
  • closure
  • associativity
  • identity
  • inverse
Multiplicative group:
  • closure
  • associativity
  • distributivity
  • commutative
Field-by-field Comparison
Field Before After
Front A&nbsp;<b>commutative ring</b>&nbsp;has the following properties:
Back Additive Group:<br><ul><li>closure</li><li>associativity</li><li>identity</li><li>inverse</li></ul><div>Multiplicative group:</div><div></div><ul><li>closure</li><li>associativity</li><li>distributivity</li><li>commutative</li></ul>
Tags: ETH::1._Semester::DiskMat::5._Algebra::5._Rings_and_Fields

Note 14: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: y|z>._M[it
added

Previous

Note did not exist

New Note

Front

ETH::1._Semester::DiskMat::5._Algebra::5._Rings_and_Fields
An integral domain has the following properties:

Back

ETH::1._Semester::DiskMat::5._Algebra::5._Rings_and_Fields
An integral domain has the following properties:
Additive Group:
  • closure
  • associativity
  • identity
  • inverse
Multiplicative group:
  • closure
  • associativity
  • distributivity
  • identity
  • no zero-divisors
Field-by-field Comparison
Field Before After
Front An&nbsp;<b>integral domain</b>&nbsp;has the following properties:
Back Additive Group:<br><ul><li>closure</li><li>associativity</li><li>identity</li><li>inverse</li></ul><div>Multiplicative group:</div><div></div><ul><li>closure</li><li>associativity</li><li>distributivity</li><li>identity</li><li>no zero-divisors</li></ul>
Tags: ETH::1._Semester::DiskMat::5._Algebra::5._Rings_and_Fields

Note 15: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: uFE6t!4Hr%
added

Previous

Note did not exist

New Note

Front

ETH::1._Semester::DiskMat::5._Algebra::5._Rings_and_Fields
A field has the following properties:

Back

ETH::1._Semester::DiskMat::5._Algebra::5._Rings_and_Fields
A field has the following properties:
Additive Group:
  • closure
  • associativity
  • identity
  • inverse
Multiplicative group:
  • closure
  • associativity
  • distributivity
  • identity
  • no zero-divisor
  • inverse
Field-by-field Comparison
Field Before After
Front A&nbsp;<b>field</b>&nbsp;has the following properties:
Back Additive Group:<br><ul><li>closure</li><li>associativity</li><li>identity</li><li>inverse</li></ul><div>Multiplicative group:</div><div></div><ul><li>closure</li><li>associativity</li><li>distributivity</li><li>identity</li><li>no zero-divisor</li><li>inverse</li></ul>
Tags: ETH::1._Semester::DiskMat::5._Algebra::5._Rings_and_Fields

Note 16: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: F6#_)#wBbP
added

Previous

Note did not exist

New Note

Front

ETH::1._Semester::DiskMat::5._Algebra::6._Polynomials_over_a_Field
For a field \(F\), the polynomial extension \(F[x]\) is an integral domain (name most constrained property).

Back

ETH::1._Semester::DiskMat::5._Algebra::6._Polynomials_over_a_Field
For a field \(F\), the polynomial extension \(F[x]\) is an integral domain (name most constrained property).
Field-by-field Comparison
Field Before After
Text For a field&nbsp;\(F\), the polynomial extension&nbsp;\(F[x]\)&nbsp;is {{c1:: an integral domain}} (name most constrained property).
Tags: ETH::1._Semester::DiskMat::5._Algebra::6._Polynomials_over_a_Field

Note 17: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: wJPBh5aLN<
added

Previous

Note did not exist

New Note

Front

ETH::1._Semester::DiskMat::5._Algebra::6._Polynomials_over_a_Field
\(F[x]^*_{(m(x))}\) is a field.

Back

ETH::1._Semester::DiskMat::5._Algebra::6._Polynomials_over_a_Field
\(F[x]^*_{(m(x))}\) is a field.
Field-by-field Comparison
Field Before After
Text \(F[x]^*_{(m(x))}\)&nbsp;is {{c1:: a field}}.
Tags: ETH::1._Semester::DiskMat::5._Algebra::6._Polynomials_over_a_Field

Note 18: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: tz7t=t1v7n
added

Previous

Note did not exist

New Note

Front

ETH::1._Semester::DiskMat::5._Algebra::6._Polynomials_over_a_Field
 \(F[x]\) is an integral domain.

Back

ETH::1._Semester::DiskMat::5._Algebra::6._Polynomials_over_a_Field
 \(F[x]\) is an integral domain.
Field-by-field Comparison
Field Before After
Text &nbsp;\(F[x]\)&nbsp;is {{c1:: an integral domain}}.
Tags: ETH::1._Semester::DiskMat::5._Algebra::6._Polynomials_over_a_Field

Note 19: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: gY:3x2q3Co
added

Previous

Note did not exist

New Note

Front

ETH::1._Semester::DiskMat::5._Algebra::5._Rings_and_Fields::4._Zerodivisors_and_Integral_Domains
For \(D\) integral domain, \(D[x]\) is an integral domain.

Back

ETH::1._Semester::DiskMat::5._Algebra::5._Rings_and_Fields::4._Zerodivisors_and_Integral_Domains
For \(D\) integral domain, \(D[x]\) is an integral domain.
Field-by-field Comparison
Field Before After
Text For&nbsp;\(D\)&nbsp;integral domain,&nbsp;\(D[x]\)&nbsp;is {{c1:: an integral domain}}.
Tags: ETH::1._Semester::DiskMat::5._Algebra::5._Rings_and_Fields::4._Zerodivisors_and_Integral_Domains

Note 20: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: I*>`1t?wD%
added

Previous

Note did not exist

New Note

Front

ETH::1._Semester::DiskMat::5._Algebra::5._Rings_and_Fields::5._Polynomial_Rings
For a commutative ring \(R\), \(R[x]\) is a commutative ring.

Back

ETH::1._Semester::DiskMat::5._Algebra::5._Rings_and_Fields::5._Polynomial_Rings
For a commutative ring \(R\), \(R[x]\) is a commutative ring.
Field-by-field Comparison
Field Before After
Text For a commutative ring&nbsp;\(R\),&nbsp;\(R[x]\)&nbsp;is {{c1:: a commutative ring}}.
Tags: ETH::1._Semester::DiskMat::5._Algebra::5._Rings_and_Fields::5._Polynomial_Rings
↑ Top