Assignment, Week 7

Solutions

Reading in Silverman

Ch 17, Computing Roots Modulo m
Ch 18, Powers, Roots, and "Unbreakable" Codes

Problems

A Problems

First Edition: 16.1, A16.1, 17.1
Second Edition: 16.1, 16.2, 17.1

B Problems

Write a program to check if a number n is composite or probably prime as follows. Choose 10 random numbers a₁, a₂, ... a₁₀, between 2 and n-1 and compute a_i^n-1 mod n for each a_i. If the result is not congruent to 1 mod n for any a_i, return the message " n is composite." In the result is congruent to 1 for all of the a_i, return the message "n is probably prime."