Design Decisions for Mathematical Software: How High Can You Go?

Prof. George T. Heineman
Computer Science Department, WPI

September 10, 2004
11 a.m. - 12 noon
Fuller Labs 320

Abstract

In August of 2002, the team of Manindra Agrawal, Neeraj Kayal, and Nitin Saxena electrified the computer science community with their publication simply entitled, "PRIMES is in P" (www.cse.iitk.ac.in/primality.pdf). Algorithms are considered to be efficient if they can be proven to belong to the polynomial class P. For quite some time (perhaps 2,400 years) the question of determining whether a given integer N is prime has eluded attempts to determine whether it can be solved by an efficient algorithm. While the algorithm offers a convincing proof, one naturally asks... How can this algorithm be implemented? And while the algorithm has been proven to run in time O(n^12), where n is the number of bits to be tested, the constant 'c' is unknown. What design tradeoffs can one make to improve the efficiency of the algorithm? What numerical representation is required given the large size of the numbers being checked? Can one identify an architecture to parallelize substeps of the algorithm? This presentation takes a critical software engineering viewpoint of an important, elegant algorithm.

Host

Neil T. Heffernan
Refreshments will be served.

Maintained by webmaster@wpi.edu
Last modified: Sep 27, 2006, 16:05 EDT