CS475 Lab 0: Managing C Projects

Goal:

This lab reviews the fundamentals of project management in C including compiling, debugging, and testing programs.
The projects in this class are difficult. Practicing these fundamentals will save you valuable time and effort when facing harder tasks.

References:

• Makefiles
• Bash

Source:

Background:

Fermat's Little Theorem (FLT) is an axiom in number theory. It states that if p is prime and x is not a multiple of p, then x^(p-1) % p = 1.
Conversely, when a number n is not prime there (usually) exists some witness w (which is not a multiple of n) where w^(n-1) % n /= 1.

What this means is that we can use FLT as a primality test. Let's say we want to determine if a number n is prime.
If we can find a witness w (which is not a multiple of n) where w^(n-1) % n /= 1 then we know for certain that n is not prime.

Task:

Use the function power_mod as a primality test to identify the composite (not prime) numbers in the file nums. Do this without modifying the file FLT.c, or by writting any additional C files.

Hint: 2 is a witness for all of the composite numbers in the file nums.

Steps:

1. Add a target FLT_DEBUG to the Makefile which enables the debug message in FLT.c.
2. Create a Bash script which accepts a list of numbers as input and outputs only the composite numbers from the original list.
   Use FLT or FLT_DEBUG with a base of 2 to test if numbers are prime according Fermat's Little Theorem.
3. As an extra challenge write two bash scripts which use FLT and FLT_DEBUG respectively.

Hints:

To complete this lab you will likely need to know how to do the following

1. Write Makefile rules
2. Pass environment variables to gcc
3. Write for loops (or while loops) in Bash
4. Use grep (I found the flags -o and -v helpful)
5. Route stderr to stdout in Bash

Created by William Scarbro 1/11/2023