# Description of the Proposed Projects

Project 1 (Rational function reconstruction in MAPLE)   A rational number can be reduced modulo a prime to an element , provided that does not divide . Similarly, given a field , a rational function , where , can be reduced to modulo an irreducible polynomial that does not divide . The question is how to retrieve ? The algorithm is described in Section 5.7 of [GG99]. The goal of this project is to implement this algorithm in MAPLE and realize benchmarks with and .

Project 2 (Rational function reconstruction in AXIOM)   Similar to Project 1, but with an implementation in AXIOM.

Project 3 (FFT-based multiplication in in AXIOM)   The goal of this project is to implement in AXIOM the algorithms of the course for FFT-based multiplication in . Benchmarks versus the Karatsuba and classical quadratic multiplication algorithms are needed for .

Project 4 (Fast Interpolation in MAPLE)   We have seen during the course how to perform interpolation with more than two moduli. Section 10.2 in [GG99] propose an elegant divide-and-conquer strategy to improve the performances of the interpolation Algorithm. The goal of this project is to implementation this algorithm in MAPLE and realize benchmarks with and .

Project 5 (Fast Chinese Remaindering in MAPLE)   We have seen during the course how to perform Chinese Remaindering with more than two moduli. Section 10.3 in [GG99] propose an elegant divide-and-conquer strategy to improve the performances of the Chinese Remaindering Algorithm. The goal of this project is to implementation this algorithm in MAPLE and realize benchmarks with or .

Project 6 (Fast Interpolation in AXIOM)   Similar to Project 4, but with an implementation in AXIOM.

Project 7 (Fast Chinese Remaindering in AXIOM)   Similar to Project 5, but with an implementation in AXIOM.

Project 8 (Project of your choice in MAPLE or AXIOM)   During your reading of [GG99], you may have been seduced or puzzled by an algorithm. Please discuss it with the instrutor, to determine if it can be turned into a project.

Marc Moreno Maza
2008-01-07