Olivier Bégassat

@olivierbbb

Joined on Jan 6, 2020

  • Introduction These notes grew out of an effort to understand the basics of class groups. With another VDF day around the corner, now seemed as good a time as any to get to grips with this material. Furthermore, class groups and lattices are part of the standard tool set in areas of cryptography relevant to blockchain and zero knowledge applications. The central object of these notes are rings of integers $\mathcal{O}_K$ in number fields $K$. These are objects borrowed from the realm of algebraic number theory (ANT). Topics derived from their study that have found application in cryptography include: Class Groups (of Imaginary Quadratic Number Fields), Lattices (ideal lattices or derived from groups of units of rings of integers), and to a lesser extent (it seems),
     Like  Bookmark
  • Introduction This post is an apetizer for a blog post in preparation on the FRI protocol. We describe what is arguably the simplest of all proof of proximity (to low degree polynomial functions)[^algthough] scheme out there. Here and elsewhere, low degree means "of degree $\leq d$" for some fixed positive integer $d$. But our interest in this scheme is as a means to shed light on a 👻 dual 👻 problem to that of proximity testing. This scheme was originally described in the 1991 paper Self Testing/Correcting for Polynomials and Approximate Functions by P. Gemmel, R. Lipton, R. Rubinfeld, M. Sudhan and A. Widegerson (we shall sometimes use the acronym GLRSW). It has been referred to as "Sudhan $d+1$" or some variation on that name in presentations on FRI given by Eli Ben Sasson. In StarkWare's blogpost on Low Degree Testing, it is what is called "the direct test". [^algthough]: although, more on that later. Compared to modern proof of proximity schemes such as FRI it is spectacularly inefficient: it runs in linear time $O(d)$ as opposed to FRI's polylogarithmic time $O(\ln(d)^2)$. However, it has the advantage of sheer simplicity: there is only ever one map at play (as opposed to the $O(\ln(d))$ inter-dependent maps in FRI);
     Like  Bookmark
  • ###### tags: `study notes` `number theory` # Filling out details in Baker's _Comprehensive Course_ [TOC] ## Theorem 11.2 ### "Then, by symmetry, we have ..." We give two proofs of Baker's claim that for $f\in\mathcal{O}_K[X]$ $$F=\prod_{\sigma:K\hookrightarrow\Bbb{C}}f^\sigma\in\Bbb{Z}[X]$$ Baker claims that this follows "by symmetry". One proof was provided to me in a comment by user @reuns and relies on the __Primitive Element Theorem__ and the __Symmetric Function Theorem__; we give a se
     Like  Bookmark