Current

The seminar is held on Tuesdays from 10 to 11 and is organized by Fredrik Johansson and Aurel Page. When on site, it takes place in room 2 at IMB. To get announcements, you can subscribe to the lfant-seminar mailing list.

• 2022-06-28
  10:00
  Salle 2
  Andreas Enge (Inria/IMB)
  Implementing fastECPP in CM

  FastECPP is currently the fastest approach to prove the primality of general numbers, and has the additional benefit of creating certificates that can be checked independently and with a lower complexity. It crucially relies on the explicit construction of elliptic curves with complex multiplication.
  I will take you on a leisurely stroll through the different phases of the ECPP and fastECPP algorithms, with explanations of their complexity. We will then see the algorithmic choices I have made when integrating a parallelised implementation of fastECPP into my CM software, which has recently been used to prove the primality of a number of record size 50000 digits.

• 2022-07-12
  10:00
  Salle 2
  Michael Monagan (Simon Fraser University)
  Computing with polynomials over algebraic number fields

  Let $K = \mathbb{Q}(\alpha_1,\dots,\alpha_k)$ be an algebraic number field. We are interested in computing polynomial GCDs in $K[x]$ and $K[x_1,\dots,x_n]$. Of course we also want to multiply, divide and factor polynomials over $K$. In $K[x]$ we have the Euclidean algorithm but it “blows up”; there is a growth in the size of the rational numbers in the remainders. It is faster to compute the GCD modulo one or more primes and use the Chinese remainder theorem and rational number reconstruction. This leads to computing a GCD in $R[x]$ where $R = K \bmod p$ is usually not be a field – it is a finite ring.
  How do Computer Algebra Systems represent elements of $K$? How do Computer Algebra Systems compute GCDs in $K[x]$? What is the best way to do arithmetic in $R$? How can we compute a polynomial GCD in $K[x_1,\dots,x_n]$? In the talk we will try to answer these questions and we will present some timing benchmarks comparing our own C library for computing GCDs in $R[x]$ with Maple and Magma.