Skip to main content

Guided Lab: Integer Arithmetic

Download the lab. Extract it, open integer-arithmetic, and read its README. Use Python 3.10+ with no third-party packages; on Windows py -3 can replace python3.

  1. Run python3 check.py starter. The unfinished starter should fail with NotImplementedError.
  2. Implement gcd and extended gcd. Trace the coefficient update by hand before testing. Inspect identities, not a particular coefficient pair.
  3. Implement inverse and all linear-congruence solutions. Test zero coefficients, negative values, invalid moduli, no-solution cases and several-solution cases.
  4. Implement repeated squaring and trial-division primality. Include exponent zero, modulus one, n below 2 and prime squares.
  5. Run the supplied checks and add one case not covered by the small exhaustive domains. Explain what it tests.
  6. Run python3 run.py starter 12 8 20 and repeat with target 7. Explain the returned list, not just its printed verification flag.
  7. Complete the cycle project and assessment.

The check program compares gcd with the standard library, solves small congruences by brute-force enumeration, checks powers against an independent built-in implementation and checks primes by exhaustive trial. Implementations must not call those oracles internally. The reference solution is for calibration after your attempt; record assistance.

The CLI limits slots to 10,000 to keep displayed output bounded. The API's explicit list can still have m solutions, so a claim of logarithmic total output time would be false. Proofs and complexity need review beyond the checker.