CWI Cryptology Group

Abstract: The best known algorithm to compute the Jacobi symbol of two n-bit integers runs in time O(M(n) log n), using Schönhage's fast continued fraction algorithm combined with an identity due to Gauss. We give a different O(M(n) log n) algorithm based on the binary recursive gcd algorithm from Stehlé and Zimmermann (2004). Our implementation - which to our best knowledge is the first one in O(M(n) log n) - is faster than GMP's quadratic implementation up from about 10000 decimal digits. This is joint work with Richard Brent (ANU, Canberra, Australia).

Abstract: Huygens is a Dutch POWER 6 supercomputer at SARA. We want to run Block Lanczos there, as part of the linear algebra stage of the RSA-768 factoring effort. This Lanczos step may need multiple core-years. We strive to utilize Huygens features while keeping the Lanczos algorithm intact. Cache awareness seems important. Keep cores busy. Utilize 128-bit vector type. This study is underway before the matrix is ready. We need to guess its size and density while choosing Lanczos parameters.