Homework

Homework#

There are ten homework sets written for this book. Each one is a Jupyter notebook that should run with a Sage kernel.

Each problem contains four to five problems where the reader can implement and test some of the concepts introduced in the text. In most of the problems the reader is required to write functions to perform some task or computation. In most cases there are tests for each function to try to validate the code, although it should be observed that these tests have limitations and incorrect or incomplete code might still pass all tests. In some cases comparisons of different methods are also present.

These start relatively easy, but do get a little more involved towards the end.

Note

It should be observed that in many examples the reader will implement functions that are already available in Sage, e.g., computations of the greatest common divisor, Legendre symbol, different primality tests, etc. Of course, our goal is to reinforce the ideas behind the algorithms, and not create new tools and we hope that the ones attempting these problems will keep that in mind.

Below is a description of each set. Each section will contain a link for the corresponding assignment, but here is a link for all homework sets (ZIP file).

Homework 1#

Download Link: Homework 1

This set contains five problems:

  1. Naive GCD: Compute the GCD (greates common divisor) by testing divisors (using no “advanced” Sage function).

  2. GCD Using divisors: Compute the GCD using Sage’s divisors function.

  3. Euclidean Algorithm: Implement the Euclidean Algorithm for computations of the GCD.

  4. Extended Euclidean Algorithm: Implement the Extended Euclidean Algorithm.

  5. Selecting a Solution for the Extended Euclidean Algorithm: Given integers \(u\) and \(v\) such that \(au + bv = \gcd(a, b)\), find integers \(u_0\), \(v_0\) such that \(u_0\) is the smallest positive integer such that \(au_0 + bv_0 = \gcd(a, b)\). (This done using Theorem 3.3.)

Homework 2#

Download Link: Homework 2

This set contains four problems:

  1. Factorization of Integers: Give the prime factorization of an integer \(n\).

  2. Representation in Base \(b\): Given an integer \(n\), compute its representation in a given base.

  3. Fast Exponentiation Modulo \(m\): Compute powers modulo \(m\) quickly using the Fast Powering Algorithm.

  4. Euler Phi Function: Compute the \(\varphi(n)\), where \(\varphi\) is the Euler Phi Function.

Homework 3#

Download Link: Homework 3

This set contains five problems:

  1. Computer Order of an Element: Given an unit in \(\mathbb{Z}/m\mathbb{Z}\), compute its order.

  2. Find all Primitive Roots: Given a prime \(p\), find all primitive roots of \(\mathbb{Z}/p\mathbb{Z}\).

  3. Proportion of Elements of Order \(q\): Given primes \(p\) and \(q\), with \(q \mid (p-1)\), compute the proportion of elements of order \(q\) in \(\mathbb{F}_p^{\times}\).

  4. Find Random Element of Order \(q\): Given primes \(p\) and \(q\), with \(q \mid (p-1)\), find a random element of order \(q\) in \(\mathbb{F}_p^{\times}\).

  5. Find Primitive Roots (Special Case): Given a prime \(p\) such that \(q = (p-1)/2\) is also prime, find a primitive root of \(\mathbb{F}_p^{\times}\).

Homework 4#

Download Link: Homework 4

This set contains four problems:

  1. Random \(k\)-bit Prime: Given a positive integer \(k\), find a random \(k\)-bit prime.

  2. Naive Discrete Log: Given \(g\) and \(h\) in \(\mathbb{F}_p^{\times}\), find, if possible, the discrete log \(\log_g(h)\) by “brute force”.

  3. ElGamal Cryptosystem: Write functions to encrypt and decrypt messages using the ElGamal Cryptosystem.

  4. Baby-Step/Giant-Step Algorithm: Implement the Baby-Step/Giant-Step Algorithm for computations of discrete logs.

Homework 5#

Download Link: Homework 5

This set contains four problems:

  1. Chinese Remainder Theorem: Use the Chinese Remainder Theorem (CRT) to find solutions of systems of congruences.

  2. Extended Euclidean Algorithm for Many Integers: Use the Generalized Extended Euclidean Algorithm to write the GCD of an arbitrary number of integers as a linear combination of those integers.

  3. Pohlig-Hellman Algorithm: Implement the Pohlig-Hellman Algorithm for computations of discrete logs, by reducing the computations to discrete logs whose bases are powers of a prime.

  4. Reduce the DLP to Order Prime Only: Given some \(g\) of order power of prime \(p^n\), compute discrete logs base \(b\) by computing discrete logs with bases of order \(p\).

Homework 6#

Download Link: Homework 6

This set contains five problems:

  1. RSA Encryption/Decryption: Write functions for encryption, decryption, and key generation for the RSA Cryptosystem.

  2. Carmichael Numbers: Given an integer \(n \geq 2\), decide if it is composite or either Carmichael Number or prime.

  3. Miller-Rabin Test: Given integers \(a\) and \(n\), use the Miller-Rabin Test to see if \(a\) is a witness for the compositeness of \(n\).

  4. Miller-Rabin Witness: Given some integer \(n\), compute how many Miller-Rabin witnesses it has.

  5. Probabilistic Primality Test: Use the Miller-Rabin test to produce a probabilistic primality test.

Homework 7#

Download Link: Homework 7

This set contains four problems:

  1. Finding Random Primes: Use the method described earlier to find a random prime of given number of bits.

  2. Pollard’s \(p-1\) Factorization: Implement Pollard's factorization algorithm.

  3. Relation Building for Difference of Squares Factorization: Implement the second part of the Relation Building step for the Difference of Squares Factorization Algorithm.

  4. Elimination for Difference of Squares Factorization: Implement the Elimination step for the Difference of Squares Factorization Algorithm.

Homework 8#

Download Link: Homework 8

This set contains four problems:

  1. Square Roots Modulo \(p\): Given some integer \(a\) and prime \(p\), compute the square root of \(a\) modulo \(p\) if it exists.

  2. Square Roots Modulo \(p^n\): Given some integer \(a\), prime \(p\), some power \(n\), and \(b\) a square root modulo \(p\), compute the square root of \(a\) modulo \(p^n\).

  3. Quadratic Reciprocity: Given some integer \(a\) and prime \(p\), use Quadratic Reciprocity to decide if \(a\) is a square modulo \(p\).

  4. Quadratic Sieve (Relation Building): Use the Quadratic Sieve to implement the first part of the Relation Building step for the Difference of Squares Factorization Algorithm.

Homework 9#

Download Link: Homework 9

This set contains four problems:

  1. Index Calculus: Implement (parts of) the Index Calculus method for computations of the discrete log (in \(\mathbb{F}_p^{\times}\)).

  2. RSA Digital Signature: Implement functions for signing and verifying documents using the RSA Digital Signature.

  3. ElGamal Digital Signature: Implement functions for generating keys and for signing and verifying documents using the ElGamal Digital Signature.

  4. Digital Signature Algorithm (DSA): Implement functions for generating keys and for signing and verifying documents using the Digital Signature Algorithm (DSA).

Homework 10#

Download Link: Homework 10

This set contains four problems:

  1. Adding Points on Elliptic Curves: Given an elliptic curve and two of its points, give the sum of these two points.

  2. Ternary Expansion: Given a positive integer \(n\), give its ternary expansion.

  3. Menezes-Vanstone Elliptic Curve ElGamal: Write function for encryption and decryption using the Menezes-Vanstone Elliptic Curve ElGamal Cryptosystem.

  4. Elliptic Curve DSA (ECDSA): Write functions for singing and verifying documents using the Elliptic Curve DSA (ECDSA)

Contents