Notes that I had made from the Computational algebra and number theory course given by Piyush sir.
All mistakes my own. Corrections very much appreciated.
Moreover, there's still a lot of formatting to fix.
Modern Computer Algebra (3e) - Joachim von zur Gathen, Jürgen Gerhard
Ideals, varieties, and algorithms - David Cox, John Little, Daniel O'Shea
Abstract algebra: Theory and applications - Thomas W. Judson, Stephen F.
Finite fields and applications - Gary L. Mullen, Carl Mummert
Handbook of finite fields - Gary L. Mullen, Daniel Panario
Contemporary abstract algebra (7e) - Joseph A. Gallian
Fundamentals of error-correcting codes - W. Cary Huffman, Vera Pless
Error control coding: fundamentals and applications - Daniel J. Costello, Shu Lin
Inorder for inverse to exist:
Eg:
⎡3 4⎤
⎣6 8⎦
doesn't have inverse as its determinant is zero.
Matrices with determinant zero are known as singular matrices.
If A is:
⎡a b⎤
⎣c d⎦
A⁻¹, if it exists, is
1 ⎡ d -b⎤
─── ⎢ ⎥
|A| ⎣-c a⎦
Ref: https://www.mathsisfun.com/algebra/matrix-inverse.html
Flow: Minors -> Cofactors -> Adjugate -> Inverse
Ref: https://www.mathsisfun.com/algebra/matrix-inverse-minors-cofactors-adjugate.html
ie, cube root of 1: ∛1
Has three roots:
where
-1 + i√3
ω = ──────────
2
-1 - i√3
ω² = ──────────
2
Derivation:
a = ∛1
=> a³ = 1
=> a³-1 = 0
=> (a-1)(a²+a+1) = 0
Finding roots of the second term:
a²+a+1 = 0
-1 ± √(1²-4*1*1)
a = ──────────────────
2*1*1
-1 ± √(-3)
= ────────────
2
-1 ± i√3
= ────────────
2
https://www.cuemath.com/algebra/cube-root-of-unity/
Normal subgroup => left and right cosets are the same.
From here:
rings ⊃ integral domains ⊃ UFD ⊃ PID ⊃ Euclidean domain ⊃ fields
gcd(x²+7x+6, x²-5x-6)
x²+7x+6 = (x²-5x-6)(1) + (12x)
x²-5x-6 = (12x)(
gcd(x⁵+2x⁴-x²+1, x⁴-1)
gcd(x^5+2*x^4-x^2+1, x^4-1)
x⁵+2x⁴-x²+1 = (x⁴-1)(x+2) + (-x²-x+3)
x⁴-1 = (-x²-x+3)(-x²-x-4) + (7x+11)
-x²-x+3 = (-7x+6)
sage: R.<x>=PolynomialRing(ZZ)
sage: gcd(x^2+7*x+6, x^2-5*x-6)
x + 1
sage: gcd(x^5+2*x^4-x^2+1, x^4-1)
1DBT:
Like rings. But the additive operation needn't have inverse.
Like groups, but doesn't need additive inverses or identity.
ie, Semigroup + inverses + identity = group
Given:
F is a finite fieldK is a subfield of F|K| = qThen:
F can be viewed as a vector space of dimension m over K|F| = qᵐGiven:
m is degree of F over prime subfield of FThen:
α: GF(p) → GF(pⁿ)
—
We can say that:
p!
pCi = ───────────
(p-i)! i!
p.(p-1).(p-i+1)
= ────────────────
i!
and since i<p, i! has no factor of p.
∴ p | pCi.
—
Binomial theorem tells us that:
p
(a + b)ᵖ = Σ pCᵢ.aⁱ.bᵖ⁻ⁱ
i=0
Since all multiples of p become 0 in Fₚ,
(a + b)ᵖ = aᵖ + bᵖ
Frobenius map is an automorphim (ie, isomorphic endomorphism) in Fₚ.
—
Field automorphisms (ie, the set of functions from a field to itself), form a group under function composition.
σ: Fₚ → Fₚ
Frobenius map is the only automorphism possible within a field??
σ(a) = aᵖ
aka Frobenius automorphism.
Given:
f of degree nFind:
Xᴹ mod f in O(n.logM)ᶜ some constant cIf M is a power of 2,
Xᵏ for some k>M.Xᵏ mod f
X to less than or equal to n-1.If M is not a power of 2, we can use binary representation of M.
A use of repeated squaring: We can do distinct degree factorization of polynomials.
Looks pretty much like the 'normal derivative'..
Eg:
Some properties:
Another property:
If
f(x)=f₁(x)ᵃ¹.f₂(x)ᵃ²....fₙ(x)ᵃⁿ
where a1,..,an are positive integers and the fᵢ(x) are distinct and irreducible over Fₚ, then
f(x)
────────────────── = f₁(x).f₂(x)....fₙ(x)
gcd(f(x), f'(x))
This property means that if f(x) and f'(x) are co-prime, f(x) has no repeated irreducible factors (ie, square-free??)
Also, xⁿ-1 has no repeated irreducible roots over GF(p) only if n and p are relatively prime.
Polynomials of the form Xʳ-1
Roots are r-th roots of unity.
# https://doc.sagemath.org/html/en/reference/number_fields/sage/rings/number_field/number_field_ideal.html
sage: K.<a> = NumberField(x^2-5)
sage: K
Number Field in a with defining polynomial x^2 - 5
sage: type(K)
<class 'sage.rings.number_field.number_field.NumberField_quadratic_with_category'>
sage: type(a)
<class 'sage.rings.number_field.number_field_element_quadratic.NumberFieldElement_quadratic_sqrt'>
# https://doc.sagemath.org/pdf/en/reference/rings/rings.pdf
# 𝔽{5⁴}/𝔽{5²}
sage: GF(5^4).over(GF(5^2))
Field in z4 with defining polynomial x^2 + (4*z2 + 3)*x + z2 over its base
Elements of (ring of) Integers are uniquely factorizable. But not all rings have this property.
Eg: In the polynomial ring with ℤ₈ coefficients,
X²-1 can be factorized in more than one way:
(X+1)(X-1)(X+3)(X-3) (∵ 9 ≡ 0 mod 8)(X+5)(X-5) (∵ 25 ≡ 0 mod 8)(X+7)(X-7) (∵ 49 ≡ 0 mod 8)sage: z8x = z8[x]
sage: z8x
Univariate Polynomial Ring in x over Ring of integers modulo 8
sage: aaa = x^2 - 1
sage: aaa.factor()
(x + 1)*(x - 1)But, of course, ℤ₈ is not an integral domain.
(∵ 4∈ℤ₈ and 2∈ℤ₈, 4⋅2 = 0. Yet 4≠0 and 2≠0.)
Means all polynomials with ℝ coefficients. That means any degree.
For example, all of the following are elements in ℝ[X]:
ℤ/7ℤ is a field with 7 elements.
ie, ℤ/7ℤ ≃ GF(7)
f = X³-1 f' = 3X²
gcd(f, f') =
ℤ/7ℤ = {0,1,2,3,4,5,6}
Substitute each of these elements in X³-1 and see if it ends up being 0.
So roots are: {1,2,4}
Euclid's algorithm only gives the gcd.
gcd(a,0) = a
gcd(a,b) = gcd(b, a mod b)
where remainders are kept but quotients are merely discarded.
Extended Euclid's algorithms finds Bezout's coefficients x and y in addition to the gcd such that
xa + yb = gcd(a, b)
Aim:
Solution:
aᵢ₊₂ = aᵢ % aᵢ₊₁ till 0.log n steps. ie, input size (as number of bits needed to represent n) halves at every step.
Proof involves 2 cases:
in each case we got to prove that
The algorithm needs at most 2.logn % operations. TODO: Comment?
An example from here done in sage:
sage: a,b = 1398,324
sage: g,s,r = xgcd(a,b)
sage: g,s,r
(6, -19, 82)
sage: s*a + r*b
6
sage: s*a + r*b == g
TrueGiven:
To prove:
xa + yb = dLet's see an algorithm to calculate x and y.
Recall Euclid's algorithm:
Let qᵢ be the quotient upon aᵢ/aᵢ₊₁. Then,
aᵢ₊₂ = aᵢ % aᵢ₊₁
=> aᵢ = qᵢ.aᵢ₊₁ % aᵢ₊₂
ie, in matrix form:
⎡aᵢ ⎤ = ⎡qᵢ 1⎤ * ⎡aᵢ₊₁⎤
⎣aᵢ₊₁⎦ = ⎣1 0⎦ ⎣aᵢ₊₂⎦
| |
└──┬──┘
↓
Let this be Qᵢ
determinant(Qᵢ) is 1 ≠ 0.
∴ Invertible.
Inverse would be:
⎡ 0 -1⎤
⎣-1 qᵢ⎦
which is also an ℤ matrix.
Coming back:
⎡aᵢ ⎤ = ⎡qᵢ 1⎤ * ⎡aᵢ₊₁⎤ -------- (B)
⎣aᵢ₊₁⎦ = ⎣1 0⎦ ⎣aᵢ₊₂⎦
I guess what we are really interested in is the first row of result.
∵ that would give
⎡aᵢ ⎤ = ⎡qᵢ 1⎤ * ⎡aᵢ₊₁⎤
⎣aᵢ₊₁⎦ = ⎣1 0⎦ ⎣aᵢ₊₂⎦
Anyway, using the earlier formula (B),
⎡a⎤ = ⎡a₀⎤
⎣b⎦ ⎣a1⎦
= Q₀ * ⎡a1⎤
⎣a2⎦
= Q₀.Q₁ * ⎡a2⎤
⎣a3⎦
....
....
= Q₀.Q₁..Qᵣ₋₁ * ⎡aᵣ ⎤
⎣aᵣ₊₁⎦
Adjust r such that:
ie,
⎡a⎤ = Q₀.Q₁ .. Qᵣ₋₁ * ⎡aᵣ ⎤
⎣b⎦ ⎣aᵣ₊₁⎦
would become
⎡a⎤ = Q₀.Q₁ .. Qᵣ₋₁ * ⎡d⎤
⎣b⎦ ⎣0⎦
where d = gcd(a,b)
Multiplying both sides by appropriate inverses,
⎡ d ⎤ = Q₀⁻¹.Q₁⁻¹ .. Qᵣ₋₁⁻¹ * ⎡ a ⎤
⎣ 0 ⎦ ⎣ b ⎦
All the inverses are ℤ 2x2 matrices.
∴ its product will also be an ℤ 2x2 matrix. Let it be Q.
Q₀⁻¹.Q₁⁻¹ .. Qᵣ₋₁⁻¹ = Q = ⎡q11 q12⎤
⎣q21 q22⎦
in which case we would have
ie,
Q = ⎡x y ⎤
⎣q21 q22⎦
All the Qᵢ matrices ∈ SL₂(ℤ).
TODO: How can we be sure about that?
A joke made by our instructor:
Mathematicians don't care about signs (because it just[?] changes with order?)
Computer scientists don't care about constants (think big-O)
We are interested in the lower bound of the computation needed to calculate x and y (the Bezout's coefficients).
Since x and y can be found from Q, the problem reduces to finding lower bound on calculation of Q.
i
Pᵢ = Π Qᵣ₋ₖ
k=0
Λᵢ biggest entry in Pᵢ
Pi₊₁ = Pi . Qᵣ₋₁-k
Λ maximum possible entry among all Qᵢ Λ ≥ a₀
Λᵢ₊₁ ≤ 2.Λᵢ.Λ
Then,
Λᵢ ≤ 2.Λᵢ₋₁.Λ
=> 2.[2Λᵢ₋₂.Λ.Λ]
4.[Λᵢ₋₂.Λ²]
2².[Λᵢ₋₂.Λ²]
...
...
2ᵏ[Λᵢ₋ₖ.Λᵏ]
Taking log₂,
Λᵣ ≤ 2ʳ.Λʳ.Λ
r + r.logΛ ≤
r + r.logΛ + logΛ
loga + loga*loga
=> 𝑂(log²a)
Polynomial in logn
Size here => number of bits required to represent it.
Efficient algorithm => P Number of steps required by algorithms shouldn't blow up. Should remain small number of steps.
What can we say about relation between x and y?
Whatever you say, make sure you can prove it.
x and y are called Bezout's coefficients.
Bezout identity.
We had seen that Euclid's gcd(a,b) algo takes 𝑂(log |a|²) bit operations.
Extended Euclid's algorithms tells us that: xa + yb = gcd(a,b)
This runs in polynomial time as well: 𝑂(log a) DBT: Comment?
x and y should be small:
size => number of bits needed to represent the number.
⎡aᵢ ⎤ = ⎡qᵢ 1⎤ * ⎡aᵢ₊₁⎤
⎣aᵢ₊₁⎦ = ⎣1 0⎦ ⎣aᵢ₊₂⎦
| |
+----+
|
Qi
| Qi | = -1 |
∴ Qi is invertible with ℤ-coefficients (ie, an ℤ-matrix).
Qi⁻¹ = adj Qi
──────
|Qi|
⎡ 0 -1⎤
⎣-1 qᵢ⎦
Anyway,
⎡a⎤ = Q₀.Q₁ .. Qᵣ₋₁ * ⎡d⎤
⎣b⎦ ⎣0⎦
where d = gcd(a,b)
So,
⎡a⎤ .Q₀⁻¹.Q₁⁻¹ .. Qᵣ₋₁⁻¹ = ⎡d⎤
⎣b⎦ ⎣0⎦
Q is:
⎡q11 q12⎤
⎣q21 q22⎦
where q11=x, q12=y
We need to have a bound on all the sizes of all the intermediate values as well.
It should be small enough, sizewise. 𝑂(log a)?? At most a. In the case of matrix, size of each element in it.
Ring is an abelian group under + with an additional binary operation called multiplication · such that²:
ie,
a,b ∈ G means a·b ∈ Aa·(b·c) = (a·b)·c∃1 ∈ G such that ∀a ∈ G, a·1 = 1·a = aa·(b+c) = (a·b)+(a·c) and (a·b)+c = (a·c)+(b·c)(Abelian group => group whose operation is commutative as well.)
Multiplicative inverse of x => x⋅i=1 Additive inverse of x => x⋅i=0
Eg: A ring on ℤ:
(ℤ, +, ·, 0, 1)
This is a ring-with-1 (ie, ring with (multiplicative) identity).
Rings without identity requirement are sometimes called rng (ie, rings without the 'i').
rng ⊂ ring ⊂ commutative ring
—
Unity / identity:
unit:
A field is a commutative division ring.
—
If G is a ring, then:
—
Group: (G,⋅,0)
— Careful about the inverses. Works generally only if ⋅ is commutative.
x⋅y = z
=> (x⋅y)⋅y⁻¹ = z⋅y⁻¹
=> x⋅(y⋅y⁻¹) = z⋅y⁻¹
=> x⋅e = z⋅y⁻¹
=> x = z⋅y⁻¹
—
ℤ is a ring.
(𝔹, xor, ∧, true, false) is a ring. (ℤ/nℤ, mod n,
If R1 and R2 are rings, then R1⨯R2 is a ring (via cartesian product). This is a product ring.
—
Consider another ring:
(ℤ/2ℤ, +, ·, 0, 1)
where ℤ/2ℤ is set of integers modulo 2.
Here, addition is modulo 2.
(Hence the name ring..)
—
Residue classes:
Remark: Equivalence class and congruence class are apparently the same.
Application of extended Euclid's algorithm.
ℤ/2ℤ is the set of residue classes on division on ℤ by 2. Only two (equivalence?) classes: odd and even. All elements in the same residue class considered the same.
5 ≡ 7 mod 2 means 5 and 7 considered same.
Eg: 2 * 3 is same as 0 * 1 = 1
This is quotienting. All elements in the same class considered same.
This is the simplest example of a quotient ring.
Equivalence classes. a ~ b
:DBT: Difference: residue and equivlaence classes.
Consider (ℤ/3ℤ, +, *, 0, 1)
Eg: 1 + 2 = 0
In general, we can talk about ℤ/aℤ where a ∈ ℕ₁
ℤ/aℤ = {0, 1, 2, …, a-1}
Additive inverse of ℤ/aℤ?
ℤ/3ℤ: a-3 a-2 is 1.
Given:
Then, we can find a unique x such that:
x ≡ x1 mod a
x ≡ x2 mod b
Also could say??
Eg:
x ≡ 2 (mod 3) | x ≡ r1 (mod m1)
x ≡ 3 (mod 5) | x ≡ r2 (mod m2)
x ≡ 2 (mod 7) | x ≡ r3 (mod m3)
where the rᵢ are residues and mᵢ are the moduli.
sage: x = crt([2, 3, 2], # residues
....: [3, 5, 7]) # moduli
sage: x
23
sage: x%3, x%5, x%7
(2, 3, 2)
sage: (x%3, x%5, x%7) == (2,3,2)
Truea and b are coprime. => gcd(a,b) = 1
∴ from Bezout's identity, αa + βb = 1 where α β ∈ ℤ
Find u and v such that
Use of this u and v is that:
x = x1.u + x2.v Taking moda on both sides,
x.moda = x1.u.moda + x2.v.moda => x.moda = x1(u.moda) + x2(v.moda) => x.moda = x1(u.moda) + 0
Now let's say:
αa + βb = 1
| | | |
+--+ +--+
u v
x can act like a secret.
Computation is efficient ∵ it's 𝑂(loga)
ℤ/abℤ =~ ℤ/aℤ ⨯ ℤ/bℤ
These two are the same ring ∵ there's is an isomorphism between them.
Map from ℤ/aℤ ⨯ ℤ/bℤ is the Chinese remainder theorem. It's inverse of the morphism in the other direction.
(u,v) where u∈ℤ/aℤ and v∈ℤ/bℤ
(u1, v1) + (u2,v2) = (u1+u2, v1+v2) (u1, v1) * (u2,v2) = (u1+u2, v1+v2)
ℤ/15ℤ =~ ℤ/5ℤ ⨯ ℤ/3ℤ
Multiplicative inverse of 7. Not in 15. (the inverse may not always exist)
So map it to other side by taking mod.
7 ——-> (7mod5, 7mod3) (2, 1)
7
Taking inverse,
2*3 is 6 and 6mod5 is 1. 1mod3 is 1.
So,
(2,1) —-> (1,1) (1mod5, 1mod3)
Identity is 1. So inverse aims at it.
Going back with CRT,
91mod15 is 1.
13 is inverse of 7mod15 (found this by own. But CRT can do it.)
We did the arithmetic in terms of the components. Instead of doing it on the bigger ring,
Additive inverse = negative Multiplicative inverse = inverse
take mod
+------>----+
| |
ℤ/abℤ =~ ℤ/aℤ ⨯ ℤ/bℤ
| |
+------<----+
CRT
Find inverse of 53 in ℤ/210ℤ
ℤ/210ℤ =~ ℤ/2ℤ * ℤ/3ℤ * ℤ/5ℤ * ℤ/7ℤ
Taking 53 to smaller rings:
(1, 2, 3, 4)
Taking multiplicative inverses:
(1, 2, 2, 2)
Now we can bring this back to ℤ/210ℤ via CRT.
Given:
Then,
ℤ/a1.a2…arℤ =~ ℤ/a1 * ℤ/a2 * … * ℤ/ar
Induction on r.
ui = 1 mod ai vi = 0 mod aj, j≠i
a = ai
b = Π aj j≠i
αai + βb = 1
αai + β Π aj = 1 j≠i
Taking mod???
Π aj becomes 0 (by definition) j≠i
après: Guassian elimination for finding determinant:
Soln: CRT => entries won't blow up
Additive inverses (negatives) exist. But multiplicative inverses (inverses) needn't. 0 never has inverse 1's inverse is itself.
Inverse exists only if number is coprime with n.
Residue classes of ℤ/nℤ = {0, 1, 2, … n-1}
Eg: ℤ/nℤ = {0, 1, 2, … n-1}
Consider ℤ/6ℤ. This ring has no inverse for 2.
∵ if 2 had an inverse,
2x ≃ 1
=> 6x ≃ 1
=> 6x (mod 6) ≃ 1 (mod 6)
=> 0 ≃ 1
which is not true.
So 2 is not invertible in ℤ/6ℤ.
Among the residue classes of ℤ/6ℤ, only those value which are coprime with 6 have inverses.
{0, 1, 2, 3, 4, 5}
✗ ✗ ✗
- 0 can't have an inverse.
- 1 is its own inverse.
- inv(5) is 5
+ 25mod6 ≡ 1
- gcd(6,2) = 2
- gcd(6,3) = 3
- gcd(6,4) = 2
Extended Euclid also
αx + βn =1 1 mod n????
u ~ v => u and v are in the same residue class.
or u ≡ v (mod a)
ie, both u and v give same remainder when divided by a.
a / (u-v) (ie, u-v divides a completely).
Revisiting the last proof of the previous class:
Find e1 and e2 such that
e1 ≡ 1 moda e1 ≡ 0 modb e2 ≡ 0 moda e2 ≡ 1 modb
Find α and β such that
e2 e1
α.a + β.b = 1
Taking moda on both sides,
0 + βb(mod a) = 1
Let a₁,.. aₖ be a set of pairwise coprime integers.
Then solve:
x ≡ x₁ mod a₁ x ≡ x₂ mod a₂ … … x ≡ xₖ mod aₖ
Let a = a₁ b = a₂.a₃…aₖ
a and b are coprime. So,
ei ≡ 1 mod aj, j≠i ei ≡ 0 mod ai
e1 ≡ 1 mod a e1 ≡ 0 mod b
Consider ℤ/abℤ
2 ∈ ℤ/15ℤ
Here, 2 represents the residue class in which 2 lies.
17 and 2 are same with respect to ℤ/15ℤ.
∵ 2 ≡ 17(mod 15)
Addition => add and the result's residue class is the actual result.
Ring => Addition always commutative. So commutativity in ring => commutativity wrt the multiplication operation
In this course, unless specified otherwise all rings are commutative.
CRT says the LHS and RHS of the following are identical:
ℤ/abℤ ≅ ℤ/abℤ ⨯ ℤ/abℤ
Ring homomorphism: A map that preserves ring operations.
Invertible homomorphism => isomorphism
Homomorphism: may be 1-way Isomorphism: definitely 2-way
Advantage: A problem may be difficult in one ring. If it's easier in another ring with which there is an isomorphism, do it!
Gaussian elimination to find determinant of a matrix had these disadvantages:
Let's try for a better way using CRT.
Λ max possible value, which needs logΛ space.
For an nxn matrix, we need n².logΛ space.
We need a bound on the size of the result determinant in terms of n and logΛ (n.logΛ)
Sign part of determinant may be ignored as we are just interested in the size.
(a,b) => use b instead of a and vice versa.
odd number of transposition => sign = -1 else 1.
Permutations. ∵ that's how things are done in Gaussian elimination, I suppose.
log(n!) = n.logn
n Π aᵢ i=1
size(det) ≤ n(logn + logΛ)
Then the value of the det would be
-2nlogn + nlogΛ ≤ det ≤ 2nlogn + nlogΛ -B ≤ det ≤ B
Let N > 2B+1
Find det (mod N) and then you get the whole thing between 0 and N.
Bigprime method: Choose a number p > 2B+1
Smallprime method: Pick the first k prime numbers such that
k
Π pᵢ ≥ 2B+1
i=1
det ≡ x₁ mod p₁
det ≡ x₁ mod p₁
...
det ≡ xₖ mod pₖ
where xᵢ is the determinant of the matrix (ie, M mod pᵢ).
prime number theorem?? number of primes <= k is k /logₑx
Eg:
A = ⎡5 4⎤
⎣2 3⎦
Largest number = N = 5
Small prime method.
Primes ≤N are: 2,3,5
A(mod 2) = │⎡1 0⎤│ = 1 = x1
│⎣0 1⎦│
A(mod 3) = │⎡2 1⎤│ = -2 = x2
│⎣2 0⎦│
A(mod 5) = │⎡0 4⎤│ = -8 = x3
│⎣2 3⎦│
det(A) ≡ x1 (mod p1) = 1 (mod 2) = 1 (mod 2)
≡ x2 (mod p2) = -2 (mod 3) = 1 (mod 3)
≡ x3 (mod p3) = -8 (mod 5) = 2 (mod 5)
ie,
det(A) ≡ 1 (mod 2)
≡ 1 (mod 3)
≡ 2 (mod 5)
The only value of det(A) that satisfies this set of equations is 7.
∴ det(A) = 7.
We wanted to find det(A) where A is an nxn ℤ matrix.
We wish to find an upper bound on size of det(A). We would like this bound to be small. ie, polynomial over size(A).
ie, at most n.max(aᵢⱼ) where i,j ∈ [1,n].
Find first k prime numbers such that
k Π pᵢ ≥ 2.2size(detA) i=1
≥ 2B + 1
detA < B
det A = D if D < N else (N-D)
f(x1,..xn) ∈ ℤ[x1,…,xn] polynomial on ℤ??
For a large N, if we know λmodN then we can find λ provied 2|λ| + 1 < N.
Prime number theorem. Number of primes < n is bounded by x/logx
π(x)
Rndomly pick 1/logx probabilyt.
We want k such that p1…pk ≥ B Obvisouly, 2ᵏ < p1..pk` 2ᵏ < B k < logB
Eg: In 2ᵏ < p1..pk` Take k = B.
x = (2logB.loglogB) / (loglogB+ logloglogB +1)
Power of modular arithmetic.
Split the big computation into several small ones and tehn we can put it back together. We can let smaller computer do the small work and combine the results to make the big result which would've been difficult to for a single computer to do.
⎡ 5 10 ⎤
⎣ 200 135 ⎦
det(A mod 2) is 1
⎡1 0⎤
⎣0 1⎦
det(A mod 3) is -2
⎡2 1⎤
⎣2 0⎦
det(A mod 5) is 0
⎡0 0⎤
⎣0 0⎦
det(A mod 7) is -2
⎡5 3⎤
⎣4 2⎦
det(A mod 11) is -5
⎡5 10⎤
⎣2 3⎦
det(A) (mod 2) ≡ 1
det(A) (mod 3) ≡ -2 = 3
det(A) (mod 5) ≡ 0
det(A) (mod 7) ≡ -2 = 5
det(A) (mod 11) ≡ -5 = 6
We stopped at 11, but we stop based on the bound that we already infer.
200 was largeset number
|A| = Σ sign(σ)
n.Λⁿ
The prime p values are very small with respect to other numbers.
We had seen that
ℤ/nℤ =~ ℤ/p1ℤ ⨯ … ⨯ ℤ/pₖℤ
if n = p₁ * …. * pₖ
Ring isomorphic: "Same ring under different attire"
HW: is 𝔹 forming a ring.
nxn matrix over any commutative ring form a ring but is a non-commutative ring.
If R is a commutative ring, R[x] is the ring of polynomials in x over the coefficient ring R.
U. : symbol for disjoint union
R U R2 U … U Rⁿ
(a0,…,an) = a0 + a1X + a2X² + … + anXⁿ
Not the function associated with the polynomial. Think of the polynomial itself. As a formal object.
Could think of polynomial as infinite sequences which after some time coefficients are all zero. Only finitely many coefficients are non-zero.
Addition
Product:
Σ aᵢbⱼ Xⁱ⁺ʲ
i j
Bivariant polynomial is the ring of univariant polynomials over the ring osf univarieant polynomials.
If the ring is suitably good, CRT is applicable there as well.
Bivariant => may not have unique factorization. Polynomial rings => always have unique factorization.
ℤ[√-5] ring doesn't have unique factorization. ∵. ∈ ℂ.
—
Ring homomorphism: structure preserving map from one ring to another ring.
Ring isomorphism if the transformation done by this map is isomorphic with respect to the rings, in which case the rings are said to be isomorphic to each other.
Monic polynomial: Univariate polynomial (ie, polynomial of only single variable) whose leading coefficient (ie, coefficient of largest degree term) is 1. Eg: x² + 3x
Square-free polynomial: No repeated roots
Zero polynomial assumed to have degree -∞.
—
aᵢXᵢ + bᵢXᵢ = (aᵢ+bᵢ)Xᵢ
aᵢXᵢ ⋅ bᵢXᵢ = (aᵢ⋅bᵢ)Xᵢ
Think of polynomails not as functions but as 'standalone' objects that we can manipulate. But we can evaluate a polynomial at points of our choice.
Integral domain: Rings with an additional property: if product of 2 elements is 0, one of them is zero.
A commutative ring is an integral domain if:
ie,
a⋅b = 0 → a=0 ∨ b=0
Eg: ℤ (surprise, surprise!)
Non-example: ℤ/6ℤ
∵ 2,3 ∈ ℤ/6ℤ yet 2⋅3 is 0.
A non-zero element a in a ring is a zero-divisor if there is a non-zero element b such that a⋅b=0. In the case of ℤ/6ℤ, 2 and 3 are zero-divisors.
Another example: In ℤ/12ℤ, 4⋅3=0. So 4 and 3 are zero-divisors.
ℤ/nℤ is always a non-integral domain if n is a composite number but is an integral domain if n is prime.
ab = 0 in ℤ/pℤ means p divides one of a or b in which case a (mod p) = 0 or b(mod p) = 0.
Eg: ℚ, ℂ, ℝ, ℤ/pℤ (where p is a prime).
If R is a ring, then R* is the multiplicative group of units in R.
—
unit: R*
a⁻¹
Field if R* \ {0} is a unit.
xa+yp=1 => x is inverse of a
Fermat's little theorem may also be used.
aᵖ⁻¹ ≡ 1 mod p
=> aᵖ⁻².a ≡ 1 mod p
ie, aᵖ⁻² is inverse of a.
p=2 => manually verify. Otherwise little theorem could help.
len[(ℤ/pℤ)*] is p-1
<a> ⊆ ℤ/pℤ
where <a> is subgroup
In ℤ/nℤ, a ~ b if n/(a-b). ie, a and b are in the same residual class wrt n.
First introduced by Kummer.
Ideal numbers.
Was used to prove Fermat's last theorem.
We can kind of quotient a ring with ideals like we did with residual classes.
In the case of residue classes, [a] + [b] ≜ [a+b] [a] * [b] ≜ [a*b]
(where ≜ means congreunce.)
Well defined definition.
An ideal of a ring is a subset of that ring. An ideal can be used to construct a quotient ring. For any ideal, every element of R can be written as xI.
:HW: Chinese remainder theorem can be generalized to ideals.
Subring: S is a subring of R (ie, S ⊂ R) if:³
Ideal: 'Sub-objects' of rings³.
I ⊆ R is an ideal if
ie,
I ⊆ R
Ideals needn't be rings? But must be subset of a ring.
Ideal vs subring: Multplication closure for subrings is only for elements within the subring. But for ideals it's for elements in the parent ring as well.
Lemma: R itself and {0} are ideals for any ring R.
—
—
Statement: ℤ ⊂ ℝ but ℤ is not an ideal of ℝ.
∴ ℤ is a subring of ℝ
But, π∈ℝ ∧ 1∈ℤ still π⋅1∉ℤ
∴ ℤ is not an ideal of ℝ.
Proof by contradiction.
—
Principal ideals of a commutative ring R:
If a∈R, then the principal ideal of R generated by a is:
<a> = {x⋅a | x ∈ R}
Eg: In the ring of polynomials with real coefficients (ie, R[X]), the principal ideal generated by x²+1 is:
<x²+1> = {f(x)⋅(x²+1) | f(x) ∈ R[X]}
which ends up being the set of all R[X] elements which are multiples of x²+1.
—
Quotient rings:
:DBT: How are ideals used to construct quotient rings. :DBT: Quotienting means just the parition into 'residue-class'-like partitions?
:DBT: Rings where unique factorization failed —
Eg:
a-b ∈ I => same class.
[a] + [b] = [a+b]
[a+i1] + [b+i2] = a + i1 + b + i2 = a+b i1 + b + i2
[a]⋅[b] = [a⋅b] [a+i1]⋅[b+i2] = ab i1b i2a i1i2
———- ∈ I
ℝ quotient I: ℝ/I = {a+I | a∈ℝ}
ℝ/I is also a (commutative) ring.
Motivation for ℂ:
—
Starting ring: ℝ[x] ie, polynomial ring over ℝ (ie, coefficients are in ℝ).
This polynomial f in ℝ[x] has no solution:
x² + 1 =0
∵ x² + 1 can't be factorized. ie, this polynomial is irreducible.
But if a solution did exists for this, let it be a.
Then,
f(a) = 0 then
(x-a).g(x) = f(x)
(We get this courtesy of Euclid's algorithm.
f(x) = q(x-a) +r
f(a) in our case is 0. q(x-a) )
Principal ideal: ideals that can be generated by a single element of the ring
aℝ
A quotienting:
ℝ[x] / (x²+1).ℝ[x]
ie, neglect all multiples of x2+1.
ie, polynomial mod (x²+1)
ie, x2 can be replaced with -1.
Elements (non-neglected) will look lke: (a₀ + xa₁)
Ultimately it's just linear polynomials in this case. Degree is always < 2.
This is just ℂ-arithmetic.
sage: RR[x].quotient(x^2+1)
Univariate Quotient Polynomial Ring in a over Real Field with 53 bits of precision with modulus x^2 + 1.00000000000000:DBT: But how?
Addn:
(a₀+a₁x) + (b₀+b₁x)
= a₀+b₀+(a₁+b₁)x
Multn:
(a₀+a₁x) * (b₀+b₁x)
= a₀b₀ + (a₀b₁+a₁b₀)x + a₁b₁x²
= a₀b₀ + (a₀b₁+a₁b₀)x + (a₁b₁)(-1)
= (a₀b₀ - a₁b₁) + (a₀b₁+a₁b₀)x
Again, this is just ℂ-arithmetic. Think of the x as the imaginary number i.
If a polynomail F is irreducable, we can 'attach a solution' by this kind of quotienting.
ℚ[x]/(x²-2)ℚ[x]
Here, we got ℂ from ℝ by quotienting: ie, modulo the ideal (x²+1)ℝ[x]
A domain where Euclidean algorithm works.
R/I is the quotient ring with respect to the ideal I.
R/I consists of equiv classes for the eq relation a ~ b => a-b ∈ I
Principal ideal of a ring R: Ideal generated by a single element of R multiplied with every other element of the ring.
pℤ is a principal ideal in ℤ/pℤ
:TODO: Fields are integral domains with an additional property (sth related to zero…)
Fields ⊂ Integral domains
Euclidean domain:
Eg: let d(x):ℤ→ℕ = |x| Eg: In ℂ[X] (ie, polynomials with ℂ coeff) let d(x):ℂ→ℕ = deg
ℂ[X]* = ℂ (an abuse of notation to indicate that ℂ is made by 'injecting' into polynomials. const polynomials)
d(g) = degree(g)+1 This is the 'measure'.
Polynomial division of 2 polynomials a and b. Stop when d(a) < d(b).
+------------------------------
bₙXⁿ + ... + b₀ | aₘXᵐ + aₘ₋₁Xᵐ⁻¹ + ..... + a₀
CRT holds for all Euclidean domains.
Principal ideal domain: A domain in which all ideals are principal ideals.
All Euclidean domains are principal ideal domains. ie, ideal looks like aR. ie, just the multiples of a given n???
For example, ℤ is a Euclidean domain. How would we prove that all its ideals look like nℤ?
Take an aribritrariy ideal a∈I.
We know that aℤ ⊆ I
Pick n = min(|a| such that a∈I) ie, element for which degree is minimum. here, we made degree as absolute value.
Assume n ∉ I. a ∈ I \ nℤ.
a = nq+r r = a - nq ∈ I
ie, contradiction.
So all ideals are principals.
Same proof applicable for all Euclidean domains. Just plug in the appropriate degree function.
a|b => unique q and r such that a = qb + r if r is zero, then a divides b.
n terms of ideals,
Principal ideals aR will contain principal ideals bR
ie, a|b => aR ⊇ bR
2 ideals I and J
<I union J> = ideal generated by taking I U J Smallest ideal containing I and J
Iterate? I and J
Top down view: do all and then do their intersection Bottom up view: do one by one and then do their union till ∞
I ∪ J gcd(a,b) Largest ideal contained in both I and J
/ \
/ \
aI Jb
\ /
\ /
I ∩ J lcm(a,b) multiples of both and b
'Language' of ideals can be converted to ….
Largest possible ideal = Ring itslef Smallest ideal = 0
When can ideal be ring itself? units of the ring
Probably wrong: ℂ (and any field) only 2 ideals?? 0 and ring itself. ∵ invertible => 1 ∈ ideal if 1 is in ideal every is in ideal??
zero (of ring) gives zero ideal.
Prime factorization theorem upto reordring and multiplication by units. Units were just 1 nad -1 so sort of ignroed.
ℂ[x] => entire ℂ are units.
Any polynomial f(x) can be written as
f(x) = g1(x) ….. gn(x)
Now we got lcm and gcd in the language of ideals.
Can we show that gcd(a,b) = gcd(b, a rem b) in the language of ideals.
In the language of ideals, this would look like:
aR ∪ bR
First show that
aR ∪ bR ⊇ R
Computation of the remainder better be effective.
I is an ideal of R a∈I such that d(a) is min I = aR b∈I b=qa+r d(r)<d(a) then r=0
When will we say that I and J are coprime?
R together with a fucntion d:R→ℕ
d(0) - 0, d(x) > 0
degree function.
d:
Prinicipal ideal domain:
aRunique factorization over R. a = p1p2p3…
essentially uniquely ∵ p.ε.p.ε⁻¹ where ε is a unity
Maximal ideals are irreducible.
ℤ/pℤ is a field if p is prime. field => all elements except 0 are invertible. Eg: ℚ, ℝ, ℂ, ℤ/pℤ Non-eg: ℤ/6ℤ (try 3⋅2)
F = a field
F[X] ring over F => Both Euclidean algorithm and an integral domain.
Next up:
For efficiency analysis, we need to figure out how to represent finite fields and polynomials over it.
Ring over any field is a Euclidean domain.
What's true for finite fields is not necessarily true for fields in general.
Ring: R,+,⋅,1,0
A ring is a field if every element except 0 are invertible. ie, R \ {0} is invertible.
Start with 1. 2 = 1 + 1 3 = 1 + 1 + 1 n = 1 + 1 + 1 + … (n times)
Finitie field: after some time the numbers will repeat (much like a ring. How's this different from a field again?).
Characteristic of a ring is n:
ℤ/6ℤ => 6 ℤ/20ℤ[X] => 20
char of ℚ,ℤ is called zero (not ∞)
finite char for finite ring??
Char of a finite field is a prime.
Lemma: Characterstic of a finite field is prime.
What we are driving at: finite fields are only of certain classes. One is R/pR.
Supporse cardinality of a field is a prime p. is hter any other filed of size p other than Z/pZ
If there is another field F, then there should be maps between teh tow fields. An isomorphsim.
Structure preserving map => morphism.
That means they are essentially the same ring. 'Differen names'
∴ there is only one field with characterstic(or size??) p.
Every finite field should haeve a finite characteristic. And that should be a prime??
:DBT: Characteristic zero => non-finite field??
Field of size 2: F₂ The uField of size p: Fₚ
Every odd degree polynmial on ℝ has a solution in ℝ (ie, closed in ℝ).
—
Remember ℝ[X]/(X²+1)ℝ[X]
x²+1 is a prime. non-factorizable. irreducible. no soln
ℝ[X]/(X²+1)ℝ[X]
is a field. Complex numbers. A field extension of ℝ. A field contained in ℝ.
Can we find an exntesnion of F₂? x²+1 is not a prime ∵ x²+1 = (x+1)² = x2+2x+1 = x2+1
But x2+x+1 is irreducible.
F₂[X]/(X²+X+1)F₂[X]
is {a0+a1X | a0 a1 ∈ F₂} ∴ 2 possibilities, 2 variables => 4 elements.
Size of finite fields are powers of primes. Charactersitci of this feild is 2.
-1 is same as +1 in F₂.
Addition:
(a0+a1x)+(b0+b1x)
(a0+b0) + (a1+b1)x
Okay, it's just pairwise addition.
Let's try multiplication:
(a0+a1x)(b0+b1x)
a0b0 + (a0b1+a1b0)x + a1b1x2
a0b0 + (a0b1+a1b0)x + a1b1(x+1)
—
Try F₃.
Sounds like x2+1 is irredicible. 9 elements in F₃ then.
—
Try F₁₃.
Quadratic irreducible polynomial => 13² is size.
—
Fₚ, irreducible degree k polynomial
THer's a unique extension of size k.
—
ℚ(√2) is extension of ℚ[X]/x2-2
ℚ(√3) is extension of ℚ[X]/x2-3
—
All degree-k extension of a filed are equivalent.
Algorihtm to factor polynomials fover a finite field.
prime ideal.
R/m is a filed R/p is integral domain
A field E is an extension of another field F if F is a subfield of E. In which case, F is the base field, written as F ⊂ E.
E/F means the field E is an extension of the field F.
Eg:
F = ℚ(√2)
= ℚ[X]/(X²-2)ℚ[X]
= {a + √2b | a,b∈ ℚ }
is an extension of the field of ℚ.
∵ (1,√2) can serve as the basis.
So, degree is 2.
Put b=0 and we get all rational numbers => ℚ ⊂ ℚ(√2)
---
Q(√2, √3)
= ℚ(√2)(√3)
= {a+√3b | a,b∈ℚ(√2)}
= {(x+√2y) + √3(p+√2q) | x,y,p,q∈ℚ}
= {x + √2y + √3p + √6q | x,y,p,q∈ℚ}
Here, the basis is (1,√2,√3,√6).
Degree is 4.
Degree of a field extension: Dimension of the vector space of the extension
:DBT: When we quotient, we are dividing what's already there, right? Then how do we end up with new elements?
A commutative ring (with identity) where all elements other than 0 are units.
Eg:
ℤ is not a field.
3 ∈ ℤ, but 3⁻¹ is 1/3 ∉ ℤ
1 and -1 are the only elements of ℤ with multiplicative inverses in ℤ (themselves).
---
Under addition and multiplication, ℚ,ℝ,ℂ are fields.
prime subfield:
Eg: Prime field of GF(3³) is GF(3)
sage: a=GF(3^3)
sage: a
Finite Field in z3 of size 3^3
sage: a.prime_subfield()
Finite Field of size 3Eg: Lattice of subfields of GF(2²⁴): (from Pless book)
GF(2²⁴)
/ \
/ \
F2⁸ F2¹²
\ /\
\ / \
F2⁴ Fq2⁶
\ /\
\ / \
F2² Fq2³
\ /
\/
Fq2
Irreducible polynomial: polynomial that cannot be factorized further.
In F/X²+1 where X²+1 is some polynomial, the polynomial has to be irreducible in R. Otherwise the quotient won't be a field.
Quotient is a set. Consists of cosets.
char(R).Smallest number of times multiplicative identity (ie, 1) should be added up to get the additive identity.
ie,
1 + 1 + 1 + ...... + 1 = 0
| |
+--------------------+
|
|
Number of '1's here = char(R)
Eg:
ℤ/2ℤ:
1 + 1 = 0
∴ char(ℤ/2ℤ) = 2
---
ℤ/6ℤ:
1 + 1 + 1 + 1 + 1 + 1 = 0
∴ char(ℤ/2ℤ) = 6
---
(ℚ,+,⋅,0,1) is a ring.
But no matter how many 1-s we add up, it won't reach 0.o
So, char(ℚ) = 0
In the case of fields:
Prime ideal: An ideal I is prime if whenever ab∈I, a∈I or b∈I.
Eg:
I = {0,2,4,6,8,10} is a prime ideal of ℤ₁₂.
∵ for any a,b∈I, ab∈I means a∈I or b∈I
Eg: 2*4 ∈ I, and 2∈I.
Eg: In the ℤ ring, set of even numbers is a prime ideal.
Our goal for the next few lectures: characterize all possible finite fields.
Interested in polynomial factorization over all fnite fields.
Representation of elements in finite fields.
char(ℝ) = char(ℚ) = 0 (not ∞) ∵ 'infinite' characteristic.
Finite characteristic => char(R) ≠ 0 Finite characteristic doesn't mean finite ring.
char(ℤ/nℤ[X]) is n but here ring isn't finite. char(ℤ/nℤ) is n and ring is finite.
Characteristic of any field is either a prime number or 0: char(R) is the smallest such n. if char(R)=n was composite, ab=0 => a=0∨b=0 (zero divisors. but they shouldn't be possible) which violates the condition that n is the smallest such number.
Q by iteslf not part of R unless we do an embedding
Finite field => char(F) ≠ 0. Why?
ℝ could be said to be an extesnon of ℚ ℂ extension of ℝ
Any finite field has to be an extension of some finite field Fₚ=ℤ/pℤ where p is a prime.
Note: Functions which doesn't preserve structure => forgetful maps. We don't bother about that here.
So the question is: What are the kinds of such extensions that can be done? Aim: Completely characterize extensions (finite) of Fₚ where p is prime.
Remember: char(ℤ/pℤ) = p
Irreducible polynomial in the F => we get an extension if we do quotienting.
Fₚ/μ[X] where μ[X] is an irreducible polynomial in Fₚ.
Every extension of the field Fₚ should be of cardinality pᵏ where k∈ℕ\{0} (ie, a positive power of p). => every finite field has cardinality as a power of a prime p.
sage: GF(36)
ValueError: the order of a finite field must be a prime power
sage: GF(1)
ValueError: the order of a finite field must be at least 2Consider,
(ℂ,+,ℝ⋅, )
where ℝ⋅ means multiplication only be with real. ie, ℝ⋅ℂ only.
Degree of a field extension.
Fun fact: Complex plane is a vector space. X: ℝ, Y-axis: 𝑖.ℝ ie, ℂ ≃ ℝ²
[ℂ:ℝ] is 2.
ie, [ℂ:ℝ] is the degree of the extension ℂ/ℝ.
Abstract vector space. It's something other than ℝ². Like a vector space over a field K.
it's an additive abelian group: (V,+,0) Scalar multiplication is a function: ⋅: k⨯V → V Scalar multiplication distributes over addition: α(a+b)=αa+αb α(βα) = (αβ)α
(Velocity, acceleration => the field is ℝ.)
Additive abelian group => normal abelian group where operation is writen as + and identity is 0.
Any field extension can be seen as a vector space over the base field.
L/K where L is an extension over K, degree of L is cardinality L can be thought of a vector space over K.
Think of ⋅: K⨯L→L.
Linear algebra stuff:
Consider S ⊆ V.
Linear dependence => There exists uᵢ∈S where i∈n and aᵢ∈K such that
Σaᵢuᵢ = 0
Basis B of a vector space V: Subset of the vector space such that any element of the space can be written as a linear combination of the elements of the basis.
ie,
Span of V:
Operations like vector addition and scalar multiplication are defined only for two elements. So infinite sums don't make sense.
Dimension of a vector space = cardinality of the basis of V.
A vector space is finite dimensional if it has finite basis.
:DBT: Do all basis of a vector space have to be of the same dimension????
Fun fact: Infinite dimension vector space it's tricky.
Eg of finite dimesnional vector space: 3D space?? Eg of finite dimesnional vector space: polynomals. A basis for a polynomial ring could like [1,x,x²,….]
A lemma: Any two basis of a vector space V should be of the same cardinality (which is the dimension of that vector space).
Proof is easier for finite dimensional vector space.
degree of ℂ/ℝ is 2. ∵ [a, ib] ??
—
F₂/(X²+X+1) can be thought of as F₂(ω)
where ω is cube root of unity.
ω = X mod (X²+X+1) ω = X³ mod (X²+X+1) = X(X+1) - X²+X = 1
(ω²)³ = X²
F₂(ω)/F₂ is of degree 2.
—
What is the degree of ℝ/ℚ?
It's not a finte extension???
π is not an algebraic sth. It's a transcendental number. Cannot be the solution of a polynomial.
ℚ(π) B = {1, π, π², .. } is linearly independent. Since π is transcendental, a linear combination of it never results in zero.
—
ℚ(√2)/ℚ
Degree 2 ∵ (a+√2b) is a basis.
—
We know that Fₚ[X] is the polynomials over the finite field Fₚ.
Fₚ(x) is the set of rational 'functions' over Fₚ.
f(x) = —— g(x)
infinite => need an infintele linearly independent set.
1,x,x²,…
We would be dealing with fiinite extension. This was just a though provoker.
HW: L/Fₚ is finite. How to find the cardinality of L? Find the degree of L first, I guess.
Finite degree exension of Fₚ. First show that degree is finite.
—
ℚ, ℝ, and ℂ are fields. But they are infinite fields.
Adjoin:
Every finite field 𝔽 has a prime number as characteristic. F/Fₚ (F over Fₚ) is a field extension.
General extensions: L/K (L is an extension of K)
[L:K] is the degree of L/K
L/K means L can be thought of as a vector space over K.
That means:
[L:K] is the dimension of the vector space over K.
Eg:
Infinite degree not that interesting (for us, at least).
Given,
g(X) is irreducible. K[X] is a Euclidean domain => g(x)K[X] is a maximal ideal.
:REM: Euclidean domain => all ideals are principal ideals.
Irreducible polynomial gives a maximal ideal.
Ring qutoitened with maximal idea => a field.
Ideals of R/a are ideals of R itself but that contain a.
In quadratic extensions (like that for ℂ), we got all roots when we attached other roots as well. ∵ other root is also linear.
But this won't happen for all kinds of extensions.
Eg:
Given:
X³-2 ∈ ℚ[X]
It was in ℂ[X],
(X-∛2)(X-∛2ω)(X-∛2ω²)
Back to ℚ[X], X³-2 has no roots in ℚ[X]. ∵ ∛2 is irrational.
sage: Rational(real_nth_root(2,3))
TypeError: unable to convert 2^(1/3) to a rationalAttaching ∛2 to this won't get the other roots.
ℚ(∛2) ≅ ℚ[X]/X³-2
sage: QQ[real_nth_root(2,3)]
Number Field in a with defining polynomial x^3 - 2 with a = 1.259921049894873?
# 1.259921049894873? is ∛2ℚ(∛2) means smallest field containing ℚ and ∛2.
X³-2 does not split in ℚ(∛2). ie, not a splitting field.
—
We chose smallest field earlier. Why? What happens if the field had a subfield.
Consider a field L which contains one of the roots of an irreducible polynomail. L/K
:DBT: kernel of a map
Algebraically no difference, analysis might be able to (à la Cauchy or something).
:DBT: Splitting field. Field with all roots??
—
What is the degree of ℚ[X]/X³-2 / ℚ
L: ℚ[X]/X³-2 Q: ℚ
What is the degree? ie, [L:Q]
A basis: {1, X, X²} So, [L:Q] is 2.
X³ is 2. So X³ is linearly dependent on the others.
NB: Degree is degree the quotienting term.
Basis terms not linearly independent => we get a smaller polynomial. And we had started out saying irreducible??
L = K[X]/g(X)
gcd(g(Y), h(Y)) = h' then g(X) is no longer irreducible.
Finite field => attach 1 root => other roots follow binomial theorem is easier there. Proofs are simpler. Just follow the definition.
g(x) ∈ K[X] is an irreducible polynomial in K[X]. Then K[X]/g(x) is the smallest extension of K that contains a root of g(x).
Splitting field of a polynomial: smallest field containing all the roots of that polynomial.
In general, K[X]/g(x) will not be the splitting field of g(x).
Lemma: Let g(x) ∈ Fₚ[X] (a finite field) be an irreducible poly. Then g(Y) completely splits in Fₚ[X]/g(x).
ie, unlike in the case of rationals, we get all roots.
Frobenius automorphism. σ: L → L σ(α) = αᵖ σFₚ = id (σ fixes everything in the field F₆)
pCr is definitely divisible by p (provided p is prime??).
Let's prove the 'forward part'.
σ(a+b) = σ(a) + σ(b) (a+b)ᵖ = aᵖ + pC1.aᵖ⁻¹b + …. + bᵖ = aᵖ + bᵖ
Binomail theorem: σ preserves addition. σ preserved mult as well, obviously.
∴ σ is homomorpism.
So:
σ(g(x)) = g(σ(x))
provided g(x) ∈ Fₚ[X]
g(α) = a₀ + a₁.α + … + aₙαⁿ =
Apply and you can get another root. Apply that and you get next root (someimtes same root though)
it doesn't matter if you first eval the poly and apply α or the other way. ∵ eval only involves addn and mult, which are preserved by σ.
automorphism => homomorphism from a field to itself.
Fermat's little theorem: αᵖ ≡ α (mod p)
Fₚ* = units of Fₚ \ {0}
We know that X mod g(X) is a root of g(Y).
Last class, we saw that:
Degree of g(x) = n
[L : Fₚ[X]] = n
βᵢ where i∈
Linear combination of bases.
Cardinality of L: #L is pⁿ
Number of possible linear combinations with basis elements.
∵ finite field.
Units of a finite field F = F \ {0} ∵ every element other than 0 are invertible.
F* = F \ {0}
| F* | = pⁿ-1 |
Finite filed => char is finite infinite basis => field has ∞ elements => non-finite field => contradiction
—
Claim: β∈L, βⁿ - β = 0 βⁿ⁻¹ = 1
where n = |L|
This can heaooen only if it's a automorphism
g(x) irreducible poly of dgeree n
L is an exension of degree n L = Fₚ[X]/g(x)
#L is pⁿ = k
β ∈ L βᵏ - β = 0
–
roots of polynomial are exactly the elmenets of L.
T(Y) = Yᵏ-Y T(β) = βᵏ-β = 0
Completely splits => splitting field.
gcd(g(x), Xᵏ-X) = h(x) but g is ireeducible. So, h(x) is g(x). ∴ all roots of g are in L.
Unlike in the case of ℚ[x], finite field => attach one root => we get all roots.
αpr = αps σʳpr = σˢps => αp - α = 0
Any finite field of size q can be seen a splitting field of the polynomial Xq - X
:HW:
k
┬─┬ ┬─┬
│ │ │ │ g(x) = X^{pⁿ} - X
d|n g∈Irr(d,X)
where g is irreducible. d|n => d divides n.
Irr(d, X) = {g(x) ∈ Fₚ[X] where g is irreducible of degree d}
We can count how many irreducible poly of degree d are there. using mobius inversion.
Fpⁿ
Fpᵈ
Fp
Fermat little theorem: αᵖ=α Legrange's theorem implies αᵖ⁻¹=1
Fixed polynomial, then all finite field extensions are essentially isomorphic??
In quiz, X²-1=0 in ℤ/15ℤ. has 4 roots. 4,11,1,-1 — Let g1(x) and g2(x) be irreducible polynomials over Fp.
[L1:Fp] is same as degree of the polynomial. ie, d [L2:Fp] is same as degree of the polynomial. ie, d
Then, #L1 = #L2 = pᵈ
Then that means they are the same field. Splitting fields of Xq-X.
This is not the case in ℚ. ∵ there the polynomial matters. Eg: X²-1 and X³-1
But in our case (ie, finite fields), we can attach a root of g1(x) and still get roots of g2(x) as the remaining roots. ∵ of isomorphism.
Xq-X factorizes over Fp. How do we know that (:DBT:)
How to arrive at a splitting field?
Lesson: Any degree d extension is the same.
For each field Fₚ, there is a unique field extension GF(pᵈ).
L = GF(pⁿ)
│
│
K = GF(pᵈ)
│
│
M = GF(p)
n|d. Why?
Let, [L:K] = d1 and [K:M] = d2
(tower of extensions: L/K/M)
[L:M] = [L:K] * [K:M]
b1, b2,.. bd1 such that j1, j2,.. jd2 such that
n Σ i=0
Claim: {biji} is an M-basis for L
:DBT: How to show that a set of vectors are linearly independent.
Roots of Xpⁿ - X is precisely the elements of GF(pⁿ)
Consequence:
┬─┬ ┬─┬
X^{pⁿ} - X = │ │ │ │ f(X)
d|n f∈H
where H is the set of all irreducible polynomials in Fₚ of degree d
Not all UFDs are PIDs, but all PIDs are UFDs.
Show RHS=LHS and LHS=RHS both apprcaches
Next up: Equal degree factoring
How to find all linear factors of f(X)=Fₚ[X]?
Repeated roots (ie, multiplicity>1) can be taken care of by taking derivitative??
Find a g(x) for which gcd(f,g) is non-trivial. Find gcd (Euclid's algo is fast). Keep repeating. That g(x) is Xpᵈ-X where d is the desired degree.
But degree p polynomail. and p is probhibityely large. Not a great soln. we can take time logp.
Well, how about
gcd(Xᵖ-X remainder f(x), f(x))
but won't get individual roots. Porquoi? :DBT:
:DBT: Repeated squaring. Binary exponentiation??
Calcing Xᵖ rem f(x): p=a0+a1.2+a2.2²+….
Find X, X², X⁴ sepretaly mod f(x)
and somehow on prends cette:
k Π X² = Xᵖ i=0
Donc, how to find quadratic roots (we're builidng towards a way to find roots of any degree):
One could write f(x) = f1(x) * f2(x) * …
where fi(x) are the product of degree i factors of f(x)
distinct degree factorization algorithm
Splitting field and Xᵖ-X is what helped us arrive at it.
These algo all require only polynomial time ∵ it involves just gcd computation.
Formal derivative non-zero => no multiple roots.
h(x) = f/(all factors taken care of so far)
Product of polynomails will be the rsult. Consists of irreducible factors of the same degree.
next class:
A polynomial over a field that doesn't have the square of a non-constant polynomial as a factor.
Every non-zero polynomial admits a square-free factorization, which is unique upto multiplication and division of factors by a non-zero constant.
Square-free polynomial is easier to calculate than complete factorization of the polynomial.
Example:
x²+3x+2 is square free.
x²+3x+2 = (x+1)(x+2)
but x³-x²+1 isn't:
x³-x²+1 = (x-1)²(x+1)
Note that the square-free polynomials factors aren't evident from its appearance. Factorization should to find the factors. We could tell (at least in the case of univariate polynomials) that there are no repeating roots if the polynomial is square-free.
Process of converting polynomial to square-free form: square-free decomposition ⁿ.
From here:
| Polynomial | Square-free | Irreducible |
|---|---|---|
| x²+3x+1 | ✓ | ✓ |
| x²+3x+2 = (x+1)(x+2) | ✓ | ✗ |
| x²+2x+1 = (x+1)(x+1) | ✗ | ✗ |
sage: R.<x>=PolynomialRing(ZZ)
sage: factor(x^2+3*x+1)
x^2 + 3*x + 1
sage: factor(x^2+3*x+2)
(x + 1) * (x + 2)
sage: factor(x^2+2*x+1)
(x + 1)^2
sage: factor(x^2+7*x+6)
(x + 1) * (x + 6)
# Square-free
sage: factor(x^5+2*x^4-x^2+1)
x^5 + 2*x^4 - x^2 + 1
# Irreducible..Input: A square-free polynomial f whose irreducible polynomial factors are all of the same degree.
Output: Either that f is irreducible or a non-trivial factor of it (can be applied again and again to get all factors).
How can we know that they are all of same degree though? Got to do distinct degree factoring.
f is defined over a finite field GF(p).
Input size: n.log|p|
To make f square-free, we define formal derivative of a polynomial. Which is kinda like the 'usual' derivative.
Xⁿ ↦ nXⁿ⁻¹
For any ring, n is defined.
:DBT: Are there infinite rings?
Proof of product rule of formal derivative:
(uv)' = uv' + u'v'
u = Σuᵢxⁱ
v = Σvᵢxⁱ
uv = Σuᵢvⱼxⁱ⁺ʲ
(uv)' = Σ(i+j)uᵢvⱼXⁱ⁺ʲ⁻¹
= ΣiuᵢvⱼXⁱ⁺ʲ⁻¹ + ΣjuᵢvⱼXⁱ⁺ʲ⁻¹
QED
We make it square-free ∵ otherwise gcd() is readily an uninteresting value.??? What if f' is 0????
f = Σaⁱxⁱᵖ = Σ(aᵢxᵢ)ᵖ
factrorize => find something else (without resoriting to factorization) that has a non-trivial gcd with f. C'est le stratégie.
—
Equal degree factorization
We made it square-free. Now let's make the factors? of same degree.
Let's say f is:
f = f1 + f2 + … + fn
where all fᵢ are of degree i.
Repeated squaring. Xpᵏ mod n find x, x², x⁴ mod n
— Is a polynomial is rreducible (like checking if a num is prime):
gcd(f,f') non-trivial => irreducible
find all gcd. all 1 => irreducible.
— How to check whether it has a root? No need to find the root (it's as difficult as factoring). Has a root => has a linear factor.
— :DBT: Square-free. Whevenever there is a square => problem. Why? —
Now we got all factors to be of the same degree ???
f = Π gᵢ i=0
We know the degree of each irreducible factor. We know how many of them are there??
What if splits completely? All irreducible are linear factors? x-a * x-b * x-c …
Turns out that factoring is equaivalent to finding roots.
The algo we gonna see is not deterministic algo (like for fdining irreduciblity), but a rnadomized algo.
—
f = g1 * g2 * …. * gn
(all the gi are irreducible)
CRT means,
GF(p)[X]/f =~ GF(p)[X]/g1 * GF(p)[X]/g2 * … * GF(p)[X]/gn
(Computatiion is in LHS, but analyais is in RHS)
At this point we don't know what gi are.
(apᵈ-1 is 1.)
Assume p is odd. p even case is an exercise.
—
non-invertible => do gcd and we got a factor???
Find 'non-trivial' square root of 1 in the LHS ring and we're done. (How??)
gcd(α-x) ???
det algo if 𝑂(np) time randized algo if 𝑂(n.logp) time
We made the polynomial:
We know that n=dl ∵ it's a polynomial. But we don't know the gi Remember RHS for just analysis for our sake.
GF(p)[X]/f(x) -~ GF(p)[X]/f1(x) ⨯ GF(p)[X]/f2(x) ⨯ .. ⨯ GF(p)[X]/fl(x)
Corresponding relation should?? hold in the unit rings as well.
zero divisor => we got a factor ✓. Iteration over. Otherwise we got to do ore work.
forall α ∈ GF(p)[X]/f(x). Randomly pick an α. (that's why Cantor-Zassenhaus is a randomized algorithm)
We can tell that (how??): αpᵈ-1 = 1
then for d=odd,
β = α(pᵈ-1)/2 is a square root of unity. (calced by repeated squaring => P time)
We know of 2 square roots of 1: 1 and -1
it's a ring can have more roots unlike felds.
trivial square root of 1: 1 and -1 We are interested in non-trivial roots.
if β is neither 1 nor -1 in GF(p)[X]/f(x), β-1 is a zero divisor.
Analysis: ∀k.
Let's say k = (pᵈ-1)/2
G = GF(p)[X]/f(x)* with multplication as operation.
φ: G → G φ(x) = xᵏ
φ is a homomorphism. ie, φ(x.
:DBT: Kernel of a map Ker(φ) = {x∈G | φ(x)=1}
Ker is a subgroup. Proof?
Our 'bad' events are when α ∈ {1,-1} Let's forget about -1 for now. α picked outside the kernel with at least 1/2 probability => we're cool.
Non-trivial kernel: means kernel is not the entire group.
+------------+ +------------+
| | | |
| +------+ | | |
| | Ker |--------------------1 |
| +------+ | | |
| | | |
+------------+ +------------+
Sub-group's order divides the size of the group.
Let's now consider one compoenent.
GF(pᵈ)
elements of which which are roots?? of X^{p^d} - 1 which are pᵈth roots of unity.
Primitive nth orots of unity generator in ℂ. ζ=e2πi/n ???
n divisble p => not gonna work out too well but pd stuff means that won't happen???
Lemma: GF(pᵈ)* is a cyclic group of order pᵈ-1. There exists a ζ such that every element of GF(pᵈ)* are generated by ζ. ie, every element of GF(pᵈ)* is a power of ζ.
at least with 0.5 probab we won't get all 1 ??? (whatever that means??)
Bad event=> fall inside the kernel of our chosen map.
—
Earlier we had ignored the -1 part. Now let's take care of that.
Kernel is half actually?? (Why??) Kernel is codomain 1. the rest is codomain 1.
a function ψ:G→H get one elem such that ψ(xₕ) ∈ H => mult with coset? ?????
Okay, kerenel is exact half (of the group??)
bad event => all 1 or all -1 got l components Choices 1/-1 Probability of bad events = 2 * 1/2l => Probability of good events = 1 - 2 * 1/2l = 1 - (1/2(l-1))
if l≥2, then probability 0.5
—
:HW: taking Trace polynomial of α ℂ beng a cyclic group clear from the way they are constructed.
—
Next class:
Cantor-Zassenhaus was like all factors same degree and we knew that degree. q?? is 1 or -1 with equal probability. So we knew it would end up as either 0 or -2=2.
DBT: What makes non-squarefreeness a problem?
Input:
Output:
f can be written as:
f = f1.f2…..fm
where each fi is a distinct irreducible factor of f.
Note that we don't know what the fi-s are. Unlike in the case of Cantor-Zassenhaus.
Then from CRT, we can say that
GF(p)[X]/f = GF(p)[X]/f1 . GF(p)[X]/f2 ….. GF(p)[X]/fm
GF(pd1) . ….
Common sub-field is GF(p) ie, Fₚ.
Now see what is there in CRT that looks like Fₚ ⨯ Fₚ ⨯ .. ⨯ Fₚ
Let di be the degree of fi.
Let n be the degree of f.
n = d1.d2…dm
In a field, binomial theorem tells us that:
(X+Y)ᵖ = Xᵖ+Yᵖ
∵ all other terms are multiple of p which turns out to be 0 since it's a ring till p.
Berlekamp sub-algebra = B: is the subset of R that maps to Fₚ ⨯ Fₚ ⨯ .. ⨯ Fₚ from CRT.
Find basis for B. :DBT: mais porqoui.
power it p
Assume p is odd prime Not interested in 1 and -1. in B??
gcd(α⁽ᵖ⁻¹⁾/2
Quite similar to Cantor-Zassenhaus except that α is randomly chosen from the Berlekamp sub-algebra B.
If f completely splits in B, B is R itself. Completely split => all factors are linear. But this is a special case.
We need a way to get hold of the Berlekamp subalgebra B. I want the basis of B.
We got something like
GF(p)[X]/f(X) = GF(pd1) ⨯ GF(pd2) ⨯ … ⨯ GF(pdm)
But how would we represent a field extension? Field together with a basis? Give an irreducible polynomial. But of what degree?? If GF(pᵈ) is to be made from GF(p) we give a irreducible poly of degree d.
Structure constants aother way to specify field extension.
In the end what we care about are the filed operations: addn, multn, etc
Given vector space's basis: βᵢ
∀i,j βᵢ.βⱼ = ΣCᵢⱼₖβₖ
where Cᵢⱼₖ ∈
Okay, how do we compute B?
:DBT: Subspace?? Means sub-vector space
Catoegry theory: forgetful structures???
:DBT: Ignore mult and ering is a vector space???
Is B a sub-space?
We're interested in the bad guys. Bad people gve interesing sotriesn bgood people give boring stories.
Addn of B continues to be in B. What about multn?
:DBT: Is GF(p) ⊂ GF(pd) ?? They are isomorphic for sure though.
B is a vectorspace.
Then to get hold of B, we need to find its basis.
What could be dimension of B? m because we just said it's like Fₚ ⨯ Fₚ ⨯ .. ⨯ Fₚ in the setting of CRT.
So we got find m values which are linearly independent to find basis for B.
We just need random elements of Berlekamp sub-algebra in our quest to factorize the original f.
Tip: Get familiar with the definitions of this course. Everything else would flow naturally.
To take random elements in B, it's sufficient to have the basis of B. :DBT: Why??
Dimension of R is d1 + d2 + .. + dm A basis for R?? : 1 + X + X² + … Xⁿ⁻¹
Getting the basis can also produce a sampling procedure. I guess we can make a sampling procedure if we know the basis.
Computing the basis of B is usually the costliest operatioin here?? :SIRWONDERING: Could there be another way?
:SIRWONDERING: Why should all commutative rings over GF(p) be polynomials???
We need a way to characterize B in a way other than using CRT. Because the CRT version is good only for analysis??.
—
Suppose we are given structure constnats (as a representation of Fₚ).
roots of Xp-X are the elements of Fₚ.
Finite fields => THere is only one map: Frobenius map Think of it as acting on vector space coreresponding to field and then we can say it's a linear map. σ(α) = σᵖ σ(α+β) = σᵖ + βᵖ
Info: Ker(Frobenius map) contains only 0.
Berlekamp subalgebra is the kernel of (σ-I) where σ is the Frobenius map. No it's a linear alebra problem Make matrix. find null space?? Gaussian elim. Compute basis for kernel.
ie, computing B is a linear algebra problem.
Next class:
:DBT: B is a sub-algebra of R. R is a ring => B is a sub-ring??
α ∈ᵣ Fₚ ⨯ Fₚ ⨯ .. ⨯ Fₚ
αᵖ⁻¹ = 1 ie, αᵖ = α ie, αᵖ - α = 0 Looks familiar, right? :) ie, Fₚ
Now we got to find a basis for B.
B 'sits insdie' R.
Think of R as a vector space over B.
We can show that B is a subspace.
Frobenius map is a linear map (in some sense). It's Fₚ-linear. ie, wehn we tjoml pf R as a vector space over __?
We can say that B is kernel of (σ-I) where I is identity.
If there is a map T between two vector spaces V and U, T:V→U that means we know the bases of both V and U??
Trivial => things that are to be expected. 1 and -1 are trivial square roots of 1.
V: basis of lenght n U: basis of lenght m m < n => non-trival kernel for sure Linear map T exists means there coeff tᵢⱼ such that
m T vᵢ = Σ tᵢⱼuⱼ j=1
⎡ _ _ .. _ ⎤ ⎡ X₁ ⎤ ⎡ 0 ⎤ ⎢ _ _ .. _ ⎥ ⎢ X₁ ⎥ = ⎢ 0 ⎥ ⎢ _ _ .. _ ⎥ ⎢ X₁ ⎥ ⎢ 0 ⎥ ⎣ _ _ .. _ ⎦ ⎣ X₁ ⎦ ⎣ 0 ⎦
⎡ _ _ .. _ ⎤ ⎡ X₁ ⎤ ⎡ 0 ⎤ ⎢ _ _ .. _ ⎥ ⎢ X₁ ⎥ = ⎢ 0 ⎥ ⎢ _ _ .. _ ⎥ ⎢ X₁ ⎥ ⎢ 0 ⎥ ⎣ _ _ .. _ ⎦ ⎣ X₁ ⎦ ⎣ 0 ⎦
to find the kernel.
:FINDOUT: Gauss-Jordan elimination ⎡ 1 0 a ⎤⎡ X₁ ⎤ ⎡0⎤ ⎢ 0 0 b ⎥⎢ X₂ ⎥ = ⎢0⎥ ⎣ 0 0 0 ⎦⎣ X₃ ⎦ ⎣0⎦
⎡ 1 0 a ⎤⎡ 0 ⎤ ⎡0⎤ ⎢ 0 0 b ⎥⎢ 1 ⎥ = ⎢0⎥ ⎣ 0 0 0 ⎦⎣ 0 ⎦ ⎣0⎦
So [0 1 0]ᵀ is in kernel of this linear map.
Nullity determinaton Rank=2 => dimension=1 ?? Rank+nullity = total dimension nullity = total dim - rank
Point is, it reduces to linear equation solution problem.
Computing kernel => find k many linear indep non-trivial solutions.
Convert linear map to its matrix equiv. Then we can use linear algebra.
V = R = Fₚ[X]/f(X) = U
So the map σ is from R to R.
Basis: 1 + X + X² + … Xⁿ⁻¹
n=deg(f)
Got to find the matrix transofrmation of σ.
We got to find the tᵢⱼ such that
σ(1) = 1ᵖ = 1
So t₁ⱼ = 0 unless j=1 where it's 1.
xmodp as a polynomial: coeff are tᵢⱼ Xᵖmod f where Xᵖ is found by repeated squaring.
n-1 Xᵖmod f = Σ aᵣXʳ r=0
these aᵣ are t₂ⱼ
For t₃ⱼ likiwise do
n-1 (X²)ᵖmod f = Σ aᵣXʳ r=0
We eventually find the basis for B. So that we can now find random elements of B as value of α. Picked uniformly at random.
b₁,b₂,..,bₘ = basis of B
a₁,a₂,..,aₘ ∈ᵣ Fₚ
α = aᵢbᵢ
Non-trivial zero divisors always mean factors.
All non-zero => all invertible => invertible overall. Some zero, some non-zero = interesting case
nth root of unity. And the ζ.
:FINDOUT: Cyclotomic polynomial.
π(x-ζ) ∈ ℂ[X]
can be shown sth in ℤ[X] take modp polynomial => finite field Fₚ polynomial??
ζ corresponds to 2π/n other primitive? roots of unity are 2πk/n where k and n are coprimes.
(This is a special e^(2πik/n) case of with i=1)
Cicle anology.
commo=> primitive n/dth sth..
ζ primitive nth orot of unit ζⁿ = 1 ζᵈ = 1 means d divides n.
algebra is a ring that's also a vector space.
:HW: Write a prog to print nth cyclotomic polynomial
We now come to direct applications of things that we have been discussing.
Let's start with cyclic codes.
Decoded No
+---------+ +---------+ msg +---------------+ err
Sender ->-| Encoder | | Decoder |---->----| Err detection |--->--- Receiver
+---------+ +---------+ +---------------+ |
| | | |
Encoded | | V Error Λ
message | Λ | |
V | +----------------+ |
| +----------+ | Err correction |---->----+
+-->----| Channel | +----------------+
+----------+ |
Λ V
| Discard
|
Noise
Noise can creep and data can get corrupt.
We need two things:
One way to achieve these two goals is to add redundancy.
For example, instead of 0 and 1, we may send 000 and 111. Receiver examines the data and chooses the majority value.
This is a repetition code.
Advantage:
Disadvantages:
:DBT: Authenticity of message doesn't matter? What if corrupt message end up being a codeword? Eg: John becomes Joan?
Let's look at the 'Hamming way' of doing things.
Alphabet: Σ
Relevant paramaters of a code:
A code word ∈ Σⁿ
Block codes.
Block length: n
Words of length n:
Code: of size n ⊆ Σⁿ
Each message being sent is an element of C
In the repetition code above:
Sender will only send one of the values in C. No random code words. That's agreed between sender and receiver.
lg => log₂
Here, lg(#C) is 1.
With this code, I can communicate one bit of info at a time. ie, by sending one of the code-words.
| Info | Communicated size |
|---|---|
| 000 | 0 bits |
| number ends with 1 | 2 bits |
| 100 is gonna win | 3 bits |
So, lg(#C) is the 'size' of info that was actually communicated.
Rate = info communicated by sending n bits = lg(#C)
Actually sending n bits, but its effect is only lg(#C). We get only that much info. This is the η of the code.
C is just one word => rate = 0. We are no more wiser by receiving that code. No clarity improvement. It's as good as we didn't get that message. Doesn't clear anything up.
BCH code:
Hamming distance = d d(C) = Minimum distance between two words x and y in the code
d(x,y) = number of locations in which x and y differ
d(x,x) = 0 d(x,y) ≤ n
Now we gonna look at how many bits got corrupt in a transmission.
Suppose channel can corrupt atmost t bits.
d(x,y) ≤ t
When is it possible to detect error?
We are faced with two possibilites:
Detect errors: d-1 errors Correct errors: (2t+1) ≤ d
d-1 errors easily provable. ∵ distance = d what the receiver gets won't be a code word.
Now to the 2t+1≤d case:
Remember that d(x,y) is a metric. ie,
Hamming sphere. With code blocks in it.
B(x,t) B(y,t)
/\ ≤t / \ ≤t / \
—— 2t
Take the received code word and find the nearest neighbour. That is the error correction. Nearest neighbourhood decoding.
The sphere = possible words that are to be mapped to the code word at the centre of the sphere. 2t+1 ≤ d mean no intersection. This follows from the fact that d is a metric space.
This is inefficient. Polynomial length of code instead of the info being sent. ie, linear to size of code (instead of size of info being sent). It should've scaled to lg(#C)
(Figuring out suitable codewords given a d is a challenge.)
We need to find more structured sets (not sure what that means..).
Σ = Fₚ (usually F₂) Inseado of arbitrary subs-set ,, we;re gonna take sub-spaces (meaning vector spaces??) of GF(pⁿ)
sub=space is V dim(V) = k k ≤ n dimension is k => cardinality pᵏ
Rate of code lg pᵏ = k (if p=2)
rate = k/n
Hamming weight = w(x) = d(x,0) = {i | i≠0}
d(x,y) = w(x-y) xᵢ and yᵢ same => x-y = 0 otherwise non-zero.
x,y∈V => x-y∈V
All elements in V are code words
0 is also a cod word.
Linear code.
d(V) = min{(d(x,y) | x,y∈V and x≠y}
= min{w(x) | x≠0, x∈V}
Very fast algorithm to detect errors.
Can define V with n-k different vector equations?? Instead of giving the basis.
n
h₁(x) = Σ h₁ᵢxᵢ
i=0
n
h₂(x) = Σ h₂ᵢxᵢ
i=0
...
...
n
hₙ₋ₖ(x) = Σ hₙ₋ₖᵢxᵢ
i=0
where hᵢ-s are linearly independent??
Such that all these n-k equations are zero when x∈V.
Could think of this as a matrix (n-k ⨯ n matrix??).
This is the parity check matrix.
If all these are zero for an x, then it's a code word.
So error detection is as simple as applying the parity check matrix.
Unlike in ℝₙ where orthognal means only 0, finite fields there are other ways.
Eg: two 1 elements in a vector => inner product 0 => vector is orthogonal to itself.
Parity check matrix is the basis for the orthognal fields of sth????
Correction is difficult (unachievalbe) even for linear codes… Next class we'll look further.
Recap..
Linear code
Code is t-correctable. ie, can correct errors of at-most t-bits. Original message = xᵢ (where i∈[1,k]) Basis of the linear code C = bᵢ Encoded message is y=Σxᵢbᵢ which will be a code word in C Receiver gets y and checks if H⋅y is 0
Error vector = e = y - x weight of e = w(e) ≤ t (as we assume that there is at most t errors) Sent x, but got x+e
H⋅(x+e) = H⋅x + H⋅e
∵ scalar multiplication of a matrix is distributive over addition. ¹¹ ie, M(a+b) = M⋅a + M⋅b
Now we know that H⋅x=0 since x is definitely a code word of C. So,
H⋅(x+e) = 0 + H⋅e H⋅(x+e) = H⋅e
This H⋅e is known as the syndrome.
But to find e, we need to know x. That's not generally easy. But easier with BCH, I guess. We'll see.
A linear code such that if (w0, w1, …, wn-1) are code words, then so is (wn-1, w0, w1, …, wn-2).
'the space of code words is invariant under cyclic shifts'. ¹²
From Fundamentals of error-correcting codes:
A linear code C of lenght n over Fₚ is cyclic provided that for each vector c=c0…cn-2.cn-1 ∈ C, the vector cn01.c0..cn-2 obtained from c by the cyclic shift of coordiantes i↦i+1(mod n) is also in C.
Codewords in cyclic codes are usually represented as polynomials.
As in c = c0.c1….cn-2.cn-1 becoming c(x) = c0 + c0x + c1x² + … + cn-2xⁿ⁻¹.
Cyclic code invariant under such shifts means that: if c(x) ∈ C, then x.c(x) ∈ C provided we multiply by mod (xⁿ-1).
That is, the residue class ring Rₙ = Fₚ[X] / (Xⁿ-1) becomes relevant.
The c∈C → xc∈C property suggests that cyclic codes are ideals of the ring Rₙ = Fₚ[X] / (Xⁿ-1).
∴ for getting at cyclic codes of GF(p)ⁿ, we can examine the ideals of Rₙ.
For this we need to have a way for factoring Xⁿ-1.
:DBT: Why?
ie, find all irreducible factors of Xⁿ-1 over Fₚ.
Note: Xⁿ-1 has no repeated factors over Fₚ if p and n are co-prime to each other.
Facts:
Advantage:
Can detect upto d(C)-1 errors, where d(C) is the distance of the code C. If 2t-1≤d(C) then we can correct upto t errors.
:DBT: Prove why first algo linear in #C??
Σ = Fₚ Linear code of length n is a sub-space of GF(pⁿ)
Can be defined in two ways: One of which is
d(x,y) = w(x-y)
Looking at linear code ∵ detecting algo is polynomial in cardinality of code???
#C = pᵏ k = logₚ(#C)
Rate = k/n
encode decode
k comps -------> n comps --------> k comps
Forms a vector space.
:DBT: Linear forms (V*) of a vector space
Dim(C) = k Dim(C⊥) = n-k
C⊥ is the set of all vectors that vanishes at C.
n-k⨯n matrix.
⎡h11 h12 ... h1n ⎤
⎢h21 h22 ... h2n ⎥
⎢ .... ⎥
⎢ .... ⎥
⎣hn-k1 hm2 ... hn-kn ⎦
Syndrome ∵ it's like a symptom telling
Polynomial in time.
:LOOKUP: Inner product :FINDOUT: bilinear map. Linear on two components. :FINDOUT: Linear forms of a vector space :FINDOUT: Full rank matrix?? V** isomorphic to V
Linear code correction is NP-hard. :DBT: Why?
BCH code: Gives more structure to the code.
Cyclic shift of a code word is still a code word for all code words in C.
n and p are coprime.
zero space: code space with just 0. Entire GF(pⁿ) space is a cyclic code.
More structure.
Treat code words as polynomials (instead of as strings or vectors).
c(X) = c0 + c1X + c2X² + …. + Cn-1Xⁿ⁻¹ X.c(X) = Xc0 + c1X² + c2X³ + …. + Cn-1Xⁿ
Cyclic shift is equiv to mult by X. when mod (Xⁿ-1)
Cyclotomic ring. n and p are coprime => square free
n-lenght words => Fₚ[X]/Xⁿ-1
f(x) = Xⁿ-1 f'(x) = nXⁿ⁻¹ gcd(f,f') = 1
—
Code words are elements of the ring Rₙ = Fₚ[X]/Xⁿ-1
a ∈ C => x.a ∈ C
Cyclic codes are precisely the ideals of the R (message ring).
But how to find the ideals of R?
CRT to the rescue:
GF(p)[X]/Xⁿ-1 =~ GF(p)[X]/g1 * GF(p)[X]/g2 * … * GF(p)[X]/gn
:DBT: One of them is x-1. Why?
Because x-1 always divides xⁿ-1:
sage: f=x^6-1
sage: g=x-1
sage: f.maxima_methods().divide(g)
[x^5 + x^4 + x^3 + x^2 + x + 1, 0]
sage: f=x^17-1
sage: f.maxima_methods().divide(g)
[x^16 + x^15 + x^14 + x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1,
0]
Fields as well on RHS. Field => ideals are either entire field or just zero.
zero stuff => factors
There are polynomials gᵢ(X) dividing Xⁿ-1 such that.
:FINDOUT: Fourier transform is like CRT
Ideals are multiples of roots??
Cyclic codes are the (principal) ideals of Rₙ.
g(x) = Generator polynomial = product of all gᵢ(x) which gave 0 under CRT.
Distance inversely prop to dimension.
:FINDOUT: BCH special case: Reed-Solomon code
Error-correcting code: Data is represented with some redundancy so that message can be retried even when a degree of error creeps in.
From here:
From a theoretical point of view, the checksum is a terrible code
:DBT: Why is CRC checksum bad?
Error-correcting codes needed when re-transmission is not a viable option.
Applications of error-correcting codes:
Message
(k-bits)
|
V
Encoded msg
(n-bits)
Encoding adds some redundancy, decoding removes errors.
Minimizing redundacy and maximising error correction are orthogonal goals. Error correction needs redundancy.
:FINDOUT: Wedderbern Structure Theorems
Cyclic code: keywords are multiples of a polynomial called the generator polynomial.
Idempotent in a ring: An element e of the ring such that e²=e. Weddernburn Structures Theorems => each cyclic code contain a unique idempotent (due to n and p being coprime for Rₙ).
BCH code:
—
We're looking at cyclic codes where:
One way of looking at elements of GF(p)ⁿ is to think of them as polynomials of the form
a(X) = a0 + a1X + a2X² + …. + an-1Xⁿ⁻¹
C is a cyclic code over Rₙ iff C is an ideal of Rₙ.
Code word ∈ Rₙ = Fₚ[X]/(Xⁿ-1)
For every cyclic code C in Rₙ, there is a polynomial g(x) such that: C = g(x).Rₙ
Field => only possible ideas = Field itself or zero.
CRT projections on to components.
Non-zero components => coprime to g(x)
=> Generator polynomial is product of components where ideal is zero.
GF(p)[X]/Xⁿ-1 =~ GF(p)[X]/g1 * GF(p)[X]/g2 * … * GF(p)[X]/gn
CRT project components. Ideal of LHS =
—
Our task is to design a code of distance d.
Of course, d≤n because dimension is only n.
Primitive nth root of unity:
Pick small factor of Xⁿ-1 over Fₚ[X] which has b, b², b³,…bᵈ as roots. Resulting cyclic code will have distance at least d (not exactly).
smallest ∵ we wanna increase something. :DBT: mais quoi?
Let g(x) be a factor of Xⁿ-1 such that g(b)=g(b²)=…=g(bᵈ)=0.
Every code word is a multiple of g(x).
d(C) = weight(C)
⎡ 1 β (β) ... (β)ⁿ ⎤ ⎡ a0 ⎤ ⎡ a(β) ⎤
⎢ 1 β² (β²) ... (β²)ⁿ⎥ ⎢ a1 ⎥ ⎢ a(β²) ⎥
⎢ .... ... ⎥ ⎢ .. ⎥ = ⎢ ... ⎥ = 0
⎢ .... ... ⎥ ⎢ .. ⎥ ⎢ ... ⎥
⎣ 1 βᵈ (βᵈ) ... (βᵈ)ⁿ⎦ ⎣ an-1 ⎦ ⎣ a(βᵈ) ⎦
dxn matrix.
ai-s is the codeword.
Suppose weight(a) is less than d. Après quoi?
Look at ai where ai=0. Drop corrsponding column in the dxn matrix as well.
First matrix can become Vandermonde matrix, whic is a non-singular matrix.
(Rank of any sub-matrix is d.)
Non-singular matrix * vector = 0 => every element of the vector = 0.
⎡ ……. ⎤ ⎡ .. ⎤ ⎢ ……. ⎥ ⎢ .. ⎥ ⎢ ……. ⎥ ⎢ .. ⎥ = 0 ⎢ ……. ⎥ ⎢ .. ⎥ ⎣ ……. ⎦ ⎣ .. ⎦
This can happen only if distance ≥ d.
The largest degree of polynomial, smaller the n. So we prefer smallest factor.
Finding the distnace of a linear code is an np-hard problem. Why??
Yet this is a way to get code which is designed to have distance at lest d. This is the designed distance. Code may be of larger distance though.
Can correct upto t errors. where d = 2t+1 ??
—
Now let's see how can decode codewords in such codes. Decoding algorithms.
c(x) ->--------->-- r(x) = c(x) + e(x)
Sent codeword = C(x) Received codeword is R(x) = C(x) + e(x)
We know only R(x).
C(β) = 0 ∀i≤d, C(βⁱ) = 0
e(β) = c(β) + e(β) ∵ c(β) is zero
ie,
e(βⁱ) = c(βⁱ) + e(βⁱ) = Y(βⁱ)
Two auxiliary polynomials.
Error locator polynomial: U(Y)
M = { i | eᵢ ≠ 0} #M ≤ t
U(Y) = Π (1-βⁱY) j∈M
U(0) = 1
Error corrector polynomial: V(Y)
V(Y) = Σ eᵢβⁱY ( Π (1-βⁱY) i∈M (j∈M
Y(0) = 0
Both U(Y) and V(Y) have degree #M.
V(Y) eᵢβⁱY —— = Σ ——— U(Y) i∈M (1-βⁱY)
Gonna do a power series expansion.
V(Y) —— = Σ eᵢβⁱY Σ (βⁱY)ᵏ U(Y) i∈M k≥0
= Σ eᵢ Σ (βⁱY)ᵏ i∈M k≥1
= Σ Σ eᵢ(βᵏ)ⁱ Yᵏ k≥1 i∈M
= e(β)Y + e(β²)Y² + ….. + e(βᵈ)Yᵈ + O(Yᵈ⁺)
(Could be a sort of approximation? ∵ we ignore terms of degree?? greater than d.)
(V₁Y + V₂Y² + … VₘYᵐ) = (1 + U₁Y + U₂Y² + … UₘYᵐ) * (e(β)Y + e(β²)Y² + … e(βᵈ)Yᵈ)
Now compare coefficients:
V1 = e(β) V2 = e(β²) + u1.e(β) V3 = e(β³) + u1.e(β²) + u2.e(β) V4 = .. .. Vm = ..
Don't stop at m. We stop only at d.
d equations. 2m variables. 2m+1<d
Solve this system. And we get both U and V.
U'(Y) is:
Σ -βⁱ Π (1-βʲY) i∈M j∈M j≠i
Find error locations by factorizing M over the field. ie, finding roots. Okay, but which field? Not Fₚ. But on the extension field??
V(β⁻ⁱ) =
= Σ eᵢβⁱβ⁻ⁱ Π (1-βʲ⁻ⁱ) i∈M j∈M
= Σ eᵢ Π (1-βʲ⁻ⁱ) i∈M j∈M
U(β⁻ⁱ) =
-βⁱ.
Σ -βⁱ Π (1-βʲ⁻ⁱ) i∈M j∈M j≠i
V(β⁻ⁱ) ——- = eᵢ U(β⁻ⁱ)
F₂ => ei no need to compute?? It's 1??
For a cyclic polynomail there is a generator polynomial. CRT can show that.
Input: 2 polynomials a(x) and b(x) over some ring R of degree n each Output: a(x).b(x)
We can do some arithmetic over R to arrive at the output. We are told how to multiplication and addition over R.
a(x) = a0 + a1x + a2x2 + …. + anxn b(x) = b0 + b1x + b2x2 + …. + bnxn a.b =
Σ (ai.bi) Xᵏ i+j=k
a.b has degree 2n. => 2n+1 coefficients.
cₖ = Σ (ai.bi) Xᵏ i+j=k
What's the cost? 𝑂(n²). Basic operations were addn and multn.
This was the naïve algorithm.
Can we do better?
—
What about integer multiplication?
n-bit numbers.
a = a0 + a1.2 + a2.22 + …. + an2n b = b0 + b1.2 + b2.22 + …. + bn2n
We want a.b
Basic operations are the bit operations. => Cost / complexity.
(basic ops = ring arithmetic??)
—
Karastuba's algorithm.
These two problems are similar in some ways. I guess we'll find out how soon…
Let N = 2ⁿ⁺¹ for some n be the degree of the polynomials.
Divided the polynomial into upper and lower halves.
a = A0 + X2n.A1 b = B0 + X2n.B1 a.b = A0.B0 + X2(A1B0+A0B1) + A1.B1.X((2n)+1)
linear term │ │ T(n) = 4.T(n/2) + n
= 4[4.T(n/4) + n/2] + n = 4[4.T(n/4) + n/2] + n = 4².T(n/4) + 2n + n = 4².T(n/4) + (n + 2n) = 4²[4.T(n/8) + n/4] + (n+2n) = 4³.T(n/8) + (n+2n+4n)
k-1 = 4ᵏ.T(n/2ᵏ) + n. Σ 2ⁱ i=0
if k = log₂N,
2(2.logN) . T(n/2logN) + 2logN N 2(2.logN) . T(1) + 2logN N N² + N²
Subtrn (ie, addn) could be made instead of mutliplication => saved cost => better complexity
T(N) = 3.T(N/2) + N
A0B1 + A1B0 = T1 - T0 - T2 T0 = A0B0 T1 = (A0+A1)(B0+B1) T2 = A1B1
Let's expand the recurrence relation:
T(N) = 3.T(N/2) + N = 3.[3T(N/6) + N/2] + N = 3².[T(N/6) + 3N/2] + N = 3².T(N/6) + N(1 + 3/2)
k = logN means
3logN . (3/2)logN . N
3logN ~~ 2(logN)log3
𝑂(nlog₂3)
log₂3 = 1.5849625007211563
a = a0 + a1.2 + a2.22 + …. + an2n
Careful! integer addn/multn?? carry over
— Something even better on the way!
express a in base 2ᵏ. by chunking up into pieces. Chunks of size k each.
Number is represented in a base which is a power of 2.
a = a0 + a12
The resultant polynomial evaluated at 2ᵏ, you get the number back.
Compute c(x)=a(x).b(x) Then evalute c(x) at 2ᵏ to get the product number. Evaluating at c(x) is O(N) time. Shift-and-add that's it.
But this complexity is on ring operations. Not bit ops. So we got to make the ring operations efficient.
Polynomial mult done by doing integer multn on smaller bits ??
Base ring of unity must have roots of unity. WHY? Fourier transform. convoluton. point-wise multipliaton.
ℂ means some approximation needed?? You cannot multiply complex numbers??? finite fields
Schonhage-Strassen 1970/1971 Fürer 2007 uses ℂ sbody 2008 uses finite fields ℤ/pᵏℤ => less complex error analysis N.logN 2019 again on ℂ => error analysis needed
Next up: Fourier transform
N.logN. loglogN. logloglogN. algorithm will be seen at a later class.
Open research problem??: Multiplying compelxity of multiplying poly in finite fields.
Assumptions:
Roots are in R[x]/xᴺ-1
For our polys, N got to be N≥2M+1
Reminder of a(x) when a(x) is divided by (x-
—
We evaluate at the primitive roots of unity.
Primitive N-th root of unity. ζ = exp(2πi/N)
—
Discrete Fourier Transfrom (DFT) is just the discrete form of Chinese remaindering.
C[X]/(XN)-1 =~ C[X]/X-1 * C[X]/X-ζ * … * C[X]/X-ζ(N-1)
Inverse DFT is also a DFT, but we use 1/ζ as the starting primitive root of unity ζ̅.
DFT: Coeff repr to CRT form (ē: time to ν domain) IDFT: CRT form to coeffs
1 a^i = a(ζⁱ) = —- aⱼ(ζij) √N
Double summation => order can be swapped if discrete. cont domain => not as easy
Σ(Σ aₖ.ζ(jk))ζ(-ij) j k
Σ aₖ.(Σ ζ(j(k-i))) k j
—
We need a fast way to do FT => FFT (Fast FT) Fast n.logn.
Given a(x), b(x).
Steps 1 and 3 use FFT.
Total cost: 3n.logn + n => O(n.logn)
—
a^i = Σ 0≤j≤N
N = 2M N FT => odd even parts => Two M FTs
Recurrence relation for FFT:
T(n) = 2.T(n/2) + O(n) => O(n.logn)
Polynomial multiplication using FFT.
Complexity:
nlogn. log²n. log³n. ....
Or more concisely
nlog*n
where log*n is a notation meaning keep doing log till value becomes 1.
Liven deep number thoery Dirichlet Fourier probably stumbled on the Z/pZ method but found that he couldn't improve complexity of sieving and went
Multivariable polynomial multiplication! Hensel lifting
a(x) = a0 + a1x + a2x2 + …. + anxn b(x) = b0 + b1x + b2x2 + …. + bnxn
Given polynomials f(x) and g(x) ∈ F[x], find quotient and remainder.
f(x) = q(x).g(x) + r(x)
We are told that:
+-------------------------------------
|
| f(x) = fnXn + fn-1Xn-1 + .... + f0
|
Normally this is a O(n²) algorithm. Can we do better?
We'll show that div is as difficult as poly multn. O(n.logn)
This is starting of Hensel lifting…
Find f(1/x). No computing, just symbolic subst.
Multiply xn to this. ie,
xn.f(1/x) xn[f0 + f1/x + …. fn/xn] f0.xn + fxn-1 + …. fn
which is f(x) in 'reverse order'
ie, revₙ(f)
Let F(x) be the Laurent polynomials in X. They start with some -ve power of x. F(x) = a₋ₙx-n + ….
Xn.f(1/x) = [x(n-m).q(1/x). xm.g(1/x)] + x(n-m+1).x(m-1).r(1/x) revₙ(f) = revₙ₋ₘ(q).revₘ(g) + x(n-m+1)revₘ₋₁(r)
Find q first. Then finding r is straightforward.
q degree is n-m. If we can get q modulo n-m+1, we got q precisely.
g is monic. So revₘ(g) has constant term coeff 1.
Find inverse of revₘ(g) modulo x(n-m+1)
h.revₘ(g) = 1 x(n-m+1)
Multiplying with h on what we had been doing,
revₙ(f) = revₙ₋ₘ(q).revₘ(g) + x(n-m+1)revₘ₋₁(r) h.revₙ(f) = revₙ₋ₘ(q) mod x(n-m+1)
—
if constant term coeff is 1, we can compute inverse modulo xn for any n. ???
—
For a if constant term coeff is 1, we can compute b(x) such that a(x).b(x) = 1 mod x(2i)
ab=1
Let's say (without proof),
a - 1/b = 0
Let φ = a - 1/b
Solve for φ(b)=0 mod x2ⁱ
Suppose α is the soln.
suppose that αₙ is an approximate soln for φ(b)=0 (ie, without the mod)
Taylor series expansion.
Suppose αₙ is a very close to α. Then we can ignore quadratic terms as they are too small.
δ = φ(αₙ) / φ'(αₙ)
Approximation. mod x(2ⁱ). Higher the i, more closer is the approximation to actual value.
αₙ₊₁ = αₙ - [φ(αₙ) / φ'(αₙ)]
Our starting solution (ie, at mod X) is 1. We imporve accuracy as we go to higher powers of X. ∵ mod xn means the first n coeffs would be the same.
α₀ = b₀ = 1
bₗ - [a - 1/bₗ]/(1/bₗ²) ~~ bₗ - [bₗ²a - bₗ] =
Blindly following à la newton Rhapson. It will somehow turn out to be okay. Proof by induction.
—
Lemma: Let a(x) be a polynomial such that a(0)=1 and let bₗ be a polynomial such that a.bₗ=1 mod X(2ˡ). Then, bₗ₊₁ = 2.bₗ - bₗ²a is such that
—
bₗ₊₁ = 2bₗ - bₗ.bₗ.a
= 2bₗ - bₗ.1 (∵ assumption)
= bₗ
Inverse does exists but it is a power series not a polynomial.
Lifting..
Division at the complexity of mult.
We arrived at this formula by taking a 'leap of faith' and going along with newton-Rhapson approximation.
—-
a(0) = 1 then a = 1 - a₀(x).x
1/a = 1/1-xa0
Here we need l steps. Newton-Rhapson needed only logl???
Hensel lifting recap
Efficient in the sense that we can do division at the complexity of mult.
Given a monic polynomial g(x), find its inverse h(x) such that
h(x).g(x) = 1 mod X(2ˡ)
monic poly mod X => only constant term remains: which is 1. ie, h0 = 1
φ(h) = g - (1/h)
h(l+1) = hl mod X(2l)
ie, initial terms of both h here would be same. h(l+1) is more precise.
—
f(x) ∈ ℤ[x], f(x) modp ∈
f(α0+h) = f(α0) + h.f'(α0) + h²
h = -f(α0) / f'(α0)
Finding root of a polynomial from its root mod p
Next up factorization.. Fun fact: Root finding is a special case of factorization.
—
formal derivative => no need of function being continous ??
1 + 2 + 22 + 23 + … is -1 ??
1/(1-2i) ???
p-adics
—
In ℤ[√-5], 21 can be written as both (1+2√-5)(1-2√-5) and seven*3
Factorization makes sense only in UFD. Like ℤ. — UFD, PID, ED Ideal, principal ideal —
Factoring bivariate polynomials.
f = gh . mod Y sg + th = 1 mod Y (g and h aare comprime)
Factoring bivariate polynomials Base field: K
f(x,y) ∈ K[X,Y]
Could think of them as univariant polynomials with coefficient themselves being functions: K(X)[Y]
The ring K[X,Y] is a UFD. ∵ there's a lemma showing that if R is UFD, then so is R[x]
Root finding is a special case of factorization.
For root-finding we could use Hensel lifting.
We could adapt that for factorization.
Start with an 'approximate' factorization of f.
Find one factor, then rinse and repeat to get the other factors.
What does it even mean for a multivariant polynomial to divide another? We had a clear definition in the case of univariant polynomial.
One way to give meaning is linear algebra..
Polynomials: f and g if g|f (divides).
If degX of any of f and g become 0, it's simply univariant stuff?? So, we say:
degX g > 0 and degX f > 0
—
f(x,y) mod y
Bivariate factoring.
a = Y(2k) (or did he mean m instead of a here???)
This was the starting approximation.
From this find a better approximation. ie, compute
g' = g mod m s' = s mod m
(∵ we are refining here)
Let
e = (f - gh) mod m²
Silvester matrix of polynomials f and g. ('shifting' involved.)
non-trivial gcd => gcd!=1
Determinaent of sylverton matrix = resultant(f,g)