Number theory underlies many techniques for symbolic computation, and also in several neighbouring disciplines such as modern cryptography & cryptanalysis. In this session we shall see and discuss various state-of-the-art implementations as well as bring together researchers with varied applications and using different software systems. Topics may include, but are not limited to, certificates of correctness of computational results (e.g. primality certification), algebraic field extensions, local fields, arithmetic geometry. Details about important implementation techniques are also encouraged (e.g. exploiting parallellism, new empirically-confirmed complexity results, adroit use of approximation).
If you would like to give a talk please send your title and short abstract to the session organiser as soon as possible, and anyway by 1st March 2024. The short abstract will be posted on this web page once accepted.
There is an option to submit an extended abstract for the conference proceedings in Springer Lecture Notes in Computer Science to accompany the talk. This will be reviewed and if accepted, distributed during the meeting and online via Springer. The deadline to submit to these proceedings is 22nd March 2024. Details on page limits, style files and the submission link can be found on the main ICMS webpage
Title: ECPP over MPI
Speaker: Andreas ENGE
The FastECPP algorithm 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, to which I have contributed over the last two decades.
I will present the FastECPP implementation in my CM code which has pushed the record for the largest ECPP certified prime from 49000 digits in 2022 to 86000 digits in 2023, and which is available under a free license. I will explain how the possibilities and the limits of massive parallelisation have informed the algorithmic choices made in the code. Looking at the wall-clock time complexity when the number of cores tends to infinity shows where the practical limits of the algorithm lie to certify larger numbers.
Title: A weakness in GSW Encryption
Speaker: Aaruni KAUSHIK
In this talk, we look at the Fully Homomorphic Encryption system proposed by Craig Gentry, Amit Sahai, and Brent Waters in 2013. We present a restated version of the proposed cryptosystem, and then try to look at the ciphertexts resulting from the use of this system, to try to find patterns in them. For this task, we train a machine learning pipeline, utilizing Topological Data Analysis. We show that, even for supposedly secure parameters, this machine learning approach can simply guess what the plain text should have been in a majority of cases (accuracy > 70%), in very good time complexity (< O(n^3)). However, this attack was ineffective against the Shortest Vector Problem (SVP), the base problem upon which the encryption is based. This hints at a possible flaw somewhere in the reduction from SVP (via Gap-SVP and LWE) to the cryptosystem.
Title: Determinants over ZZ
Speaker: John ABBOTT
The computation of the determinant of an integer matrix is a well-studied problem. We present some practical improvements over the current, best, practical algorithm. Our method achieves better complexity on a specific class of matrices; it is implemented in the OSCAR system. Joint work with Claus FIEKER.
© 2024. All rights reserved.
