ARITHMETIC ALGORITHMS

COMPSCI 812

Course Description

Survey of algorithms and design paradigms for exact arithmetic, as used in public-key cryptography, computer algebra, and pseudo-random number generation. Topics include primality testing, factorization of integers and polynomials, discrete logarithms, and (optionally) elliptic curves and integer lattices. Students are strongly encourage to have knowledge of basic abstract algebra (e.g.,MATH 541), and intermediate programming ability (e.g., COMP SCI 367 orCOMP SCI 300).

Prerequisties

Graduate/professional standing

Satisfies

This course does not satisfy any prerequisites.

Credits

Not Reported

Offered

Not Reported

Grade Point Average

3.29

-3.5% from Historical

Completion Rate

92.86%

-2.5% from Historical

A Rate

57.14%

-5.26% from Historical

Class Size

33.33% from Historical

Cumulative Grade Distribution

Instructors (2025 Fall)

Sorted by ratings from Rate My Professors

Similar Courses

INTEGER OPTIMIZATION

COMPSCI/ISYE/MATH 728

Introduces optimization problems over integers, and surveys the theory behind the algorithms used in state-of-the-art methods for solving such problems. Special attention is given to the polyhedral formulations of these problems, and to their algebraic and geometric properties. Applicability of Integer Optimization is highlighted with applications in combinatorial optimization. Key topics include: formulations, relaxations, polyhedral theory, cutting planes, decomposition, enumeration. Students are strongly encouraged to have knowledge of Linear Programming (e.g.,MATH/COMP SCI/I SY E/STAT 525), including algorithms, duality and polyhedral theory.

INTRODUCTION TO ALGORITHMS

COMPSCI 577

Basic paradigms for the design and analysis of efficient algorithms: greed, divide-and-conquer, dynamic programming, reductions, and the use of randomness. Computational intractability including typical NP-complete problems and ways to deal with them.

INTRODUCTION TO THEORY OF COMPUTING

COMPSCI 520

Basics about the notion, capabilities, and limitations of computation: elements of finite automata and regular languages, computability theory, and computational complexity theory. Additional topics include context-free grammars and languages, and complexity-theoretic cryptography.

ADVANCED ALGORITHMS

COMPSCI 787

Advanced paradigms for the design and analysis of efficient algorithms, including the use of randomness, linear programming, and semi-definite programming. Applications to data structures, approximating NP-hard optimization problems, learning, on-line and distributed problems. Students are strongly encouraged to have introductory knowledge of algorithms (e.g.,COMP SCI 577)

TOPICS IN THEORETICAL COMPUTER SCIENCE

COMPSCI 880

Advanced topics in algorithms, complexity, and cryptography. The exact topic varies.