Design and Analysis of Algorithms · Unit 7 · 5 hrs
Number Theoretic Algorithms
Exam-focused notes for Number Theoretic Algorithms (Design and Analysis of Algorithms, CSC325): what the TU syllabus asks and how it has actually been tested, with 4 solved past questions from this unit.
What this unit covers
- Number Theoretic Notations, Euclid's and Extended Euclid's Algorithms and their Analysis
- Solving Modular Linear Equations, Chinese Remainder Theorem, Primility Testing: Miller-Rabin Randomized Primility Test and their Analysis
Number Theoretic Notations, Euclid's and Extended Euclid's Algorithms and their Analysis
Using Extended Euclidean Algorithm, find the GCD of 12 and 16. [5]
- First integer: $a = 16$ (larger) - Second integer: $b = 12$ Goal: Find $\gcd(16, 12)$ and integers $x, y$ such that $16x + 12y = \gcd(16,12)$. --- Step Division Quotient $q$ Remainder $r$ --------------------------------------------- 1 $16 = 12 \times 1 +...
Full solved answer →Why extended euclidean algorithm is used? Write down its algorithm and analyze its complexity. [5]
The Extended Euclidean Algorithm is used to find not only the Greatest Common Divisor (GCD) of two integers a and b, but also the integer coefficients x and y such that: ax + by = gcd(a, b) This is based on Bezout's Identity. It is widely used in: - Computi...
Full solved answer →Solving Modular Linear Equations, Chinese Remainder Theorem, Primility Testing
Solve the following linear equation using Chinese Remainder Theorem. x = 1 MOD 3,x = 2 MOD 5,x = 0 MOD 7 [5]
$$x \equiv 1 \pmod{3}, \quad x \equiv 2 \pmod{5}, \quad x \equiv 0 \pmod{7}$$ $i$ remainder $ai$ modulus $mi$ --------- 1 1 3 2 2 5 3 0 7 Check coprimality: $\gcd(3,5)=\gcd(5,7)=\gcd(3,7)=1$. Moduli are pairwise coprime, so CRT gives a unique solution mod $...
Full solved answer →Solve the following linear congruences using Chinese Remainder Theorem.x≡1(mod2),x≡3(mod5),x≡6(mod7)x \equiv 1 \pmod{2},\quad x \equiv 3 \pmod{5},\quad x \equiv 6 \pmod{7}x≡1(mod2),x≡3(mod5),x≡6(mod7) [5]
$$x \equiv 1 \pmod{2}, \quad x \equiv 3 \pmod{5}, \quad x \equiv 6 \pmod{7}$$ Residues: $a1 = 1,\ a2 = 3,\ a3 = 6$ Moduli: $m1 = 2,\ m2 = 5,\ m3 = 7$ The moduli are pairwise coprime, so a unique solution exists modulo their product. --- $$M = 2 \times 5 \ti...
Full solved answer →Make Unit 7 stick
Practice CSC325 with flashcards & quizzes