Math Jerremy Kun
https://jeremykun.com/
Math ∩ Programming
2022-12-28
J
<div><div>
	
<p>In this article I’ll cover three techniques to compute special types of polynomial products that show up in lattice cryptography and fully homomorphic encryption. Namely, the <em>negacyclic </em>polynomial product, which is the product of two polynomials in the quotient ring $\mathbb{Z}[x] / (x^N + 1)$. As a precursor to the negacyclic product, we’ll cover the simpler cyclic product.</p>
<p>All of the Python code written for this article <a href="https://github.com/j2kun/negacyclic">is on GitHub</a>.</p>
<h2>The DFT and Cyclic Polynomial Multiplication</h2>
<p>A recent <a href="https://jeremykun.com/2022/11/16/polynomial-multiplication-using-the-fft/">program gallery piece</a> showed how single-variable polynomial multiplication could be implemented using the Discrete Fourier Transform (DFT). This boils down to two observations:</p>
<ol>
<li>The product of two polynomials $f, g$ can be computed via the convolution of the coefficients of $f$ and $g$.</li>
<li>The <a href="https://en.wikipedia.org/wiki/Convolution_theorem">Convolution Theorem</a>, which says that the Fourier transform of a convolution of two signals $f, g$ is the point-wise product of the Fourier transforms of the two signals. (The same holds for the DFT)</li>
</ol>
<p>This provides a much faster polynomial product operation than one could implement using the naïve polynomial multiplication algorithm (though see the last section for an implementation anyway). The DFT can be used to speed up large <em>integer</em> multiplication as well.</p>
<p>A caveat with normal polynomial multiplication is that one needs to pad the input coefficient lists with enough zeros so that the convolution doesn’t “wrap around.” That padding results in the output having length at least as large as the sum of the degrees of $f$ and $g$ (see the <a href="https://jeremykun.com/2022/11/16/polynomial-multiplication-using-the-fft/">program gallery piece</a> for more details).</p>
<p>If you <em>don’t</em> pad the polynomials, instead you get what’s called a <em>cyclic</em> polynomial product. More concretely, if the two input polynomials $f, g$ are represented by coefficient lists $(f_0, f_1, \dots, f_{N-1}), (g_0, g_1, \dots, g_{N-1})$ of length $N$ (implying the inputs are degree at most $N-1$, i.e., the lists may end in a tail of zeros), then the Fourier Transform technique computes</p>
<p>\[ f(x) \cdot g(x) \mod (x^N – 1) \]</p>
<p>This modulus is in the sense of a <a href="https://jeremykun.com/2013/06/01/rings-a-second-primer/">quotient ring</a> $\mathbb{Z}[x] / (x^N – 1)$, where $(x^N – 1)$ denotes the ring ideal generated by $x^N-1$, i.e., all polynomials that are evenly divisible by $x^N – 1$. A particularly important interpretation of this quotient ring is achieved by interpreting the ideal generator $x^N – 1$ as an equation $x^N – 1 = 0$, also known as $x^N = 1$. To get the canonical ring element corresponding to any polynomial $h(x) \in \mathbb{Z}[x]$, you “set” $x^N = 1$ and reduce the polynomial until there are no more terms with degree bigger than $N-1$. For example, if $N=5$ then $x^{10} + x^6 – x^4 + x + 2 = -x^4 + 2x + 3$ (the $x^{10}$ becomes 1, and $x^6 = x$).</p>
<p>To prove the DFT product computes a product in this particular ring, note how the convolution theorem produces the following formula, where $\textup{fprod}(f, g)$ denotes the process of taking the Fourier transform of the two coefficient lists, multiplying them entrywise, and taking a (properly normalized) inverse FFT, and $\textup{fprod}(f, g)(j)$ is the $j$-th coefficient of the output polynomial:</p>
<p>\[ \textup{fprod}(f, g)(j) = \sum_{k=0}^{N-1} f_k g_{j-k \textup{ mod } N} \]</p>
<p>In words, the output polynomial coefficient $j$ equals the sum of all products of pairs of coefficients whose indices sum to $j$ when considered “wrapping around” $N$. Fixing $j=1$ as an example, $\textup{fprod}(f, g)(1) = f_0 g_1 + f_1g_0 + f_2 g_{N-1} + f_3 g_{N-2} + \dots$. This demonstrates the “set $x^N = 1$” interpretation above: the term $f_2 g_{N-1}$ corresponds to the product $f_2x^2 \cdot g_{N-1}x^{N-1}$, which contributes to the $x^1$ term of the polynomial product if and only if $x^{2 + N-1} = x$, if and only if $x^N = 1$.</p>
<p>To achieve this in code, we simply use the version of the code from the <a href="https://jeremykun.com/2022/11/16/polynomial-multiplication-using-the-fft/">program gallery piece</a>, but fix the size of the arrays given to <code>numpy.fft.fft</code> in advance. We will also, for simplicity, assume the $N$ one wishes to use is a power of 2. The resulting code is significantly simpler than the original program gallery code (we omit zero-padding to length $N$ for brevity).</p>
<div><pre>import numpy
from numpy.fft import fft, ifft
def cyclic_polymul(p1, p2, N):
 """Multiply two integer polynomials modulo (x^N - 1).
 p1 and p2 are arrays of coefficients in degree-increasing order.
 """
 assert len(p1) == len(p2) == N
 product = fft(p1) * fft(p2)
 inverted = ifft(product)
 return numpy.round(numpy.real(inverted)).astype(numpy.int32)
</pre></div>
<p>As a side note, there’s nothing that stops this from working with polynomials that have real or complex coefficients, but so long as we use small magnitude integer coefficients and round at the end, I don’t have to worry about precision issues (hat tip to Brad Lucier for suggesting an excellent paper by Colin Percival, “<a href="https://dl.acm.org/doi/10.1090/S0025-5718-02-01419-9">Rapid multiplication modulo the sum and difference of highly composite numbers</a>“, which covers these precision issues in detail).</p>
<h2>Negacyclic polynomials, DFT with duplication</h2>
<p>Now the kind of polynomial quotient ring that shows up in cryptography is critically <em>not</em> $\mathbb{Z}[x]/(x^N-1)$, because that ring has enough easy-to-reason-about structure that it can’t hide secrets. Instead, cryptographers use the ring $\mathbb{Z}[x]/(x^N+1)$ (the minus becomes a plus), which is believed to be more secure for cryptography—although I don’t have a great intuitive grasp on why.</p>
<p>The interpretation is similar here as before, except we “set” $x^N = -1$ instead of $x^N = 1$ in our reductions. Repeating the above example, if $N=5$ then $x^{10} + x^6 – x^4 + x + 2 = -x^4 + 3$ (the $x^{10}$ becomes $(-1)^2 = 1$, and $x^6 = -x$). It’s called <em>negacyclic</em> because as a term $x^k$ passes $k \geq N$, it cycles back to $x^0 = 1$, but with a sign flip.</p>
<p>The negacyclic polynomial multiplication can’t use the DFT without some special hacks. The first and simplest hack is to double the input lists with a negation. That is, starting from $f(x) \in \mathbb{Z}[x]/(x^N+1)$, we can define $f^*(x) = f(x) – x^Nf(x)$ in a different ring $\mathbb{Z}[x]/(x^{2N} – 1)$ (and similarly for $g^*$ and $g$).</p>
<p>Before seeing how this causes the DFT to (almost) compute a negacyclic polynomial product, some math wizardry. The ring $\mathbb{Z}[x]/(x^{2N} – 1)$ is special because it contains our negacyclic ring as a subring. Indeed, because the polynomial $x^{2N} – 1$ factors as $(x^N-1)(x^N+1)$, and because these two factors are coprime in $\mathbb{Z}[x]/(x^{2N} – 1)$, the <a href="https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Over_principal_ideal_domains">Chinese remainder theorem</a> (aka Sun-tzu’s theorem) generalizes to polynomial rings and says that any polynomial in $\mathbb{Z}[x]/(x^{2N} – 1)$ is uniquely determined by its remainders when divided by $(x^N-1)$ and $(x^N+1)$. Another way to say it is that the ring $\mathbb{Z}[x]/(x^{2N} – 1)$ factors as a direct product of the two rings $\mathbb{Z}[x]/(x^{N} – 1)$ and $\mathbb{Z}[x]/(x^{N} + 1)$.</p>
<p>Now mapping a polynomial $f(x)$ from the bigger ring $(x^{2N} – 1)$ to the smaller ring $(x^{N}+1)$ involves taking a remainder of $f(x)$ when dividing by $x^{N}+1$ (“setting” $x^N = -1$ and reducing). There are many possible preimage mappings, depending on what your goal is. In this case, we actually intentionally choose a <em>non</em> preimage mapping, because in general to compute a preimage requires solving a system of congruences in the larger polynomial ring. So instead we choose $f(x) \mapsto f^*(x) = f(x) – x^Nf(x) = -f(x)(x^N – 1)$, which maps back down to $2f(x)$ in $\mathbb{Z}[x]/(x^{N} + 1)$. This preimage mapping has a particularly nice structure, in that you build it by repeating the polynomial’s coefficients twice and flipping the sign of the second half. It’s easy to see that the product $f^*(x) g^*(x)$ maps down to $4f(x)g(x)$.</p>
<p>So if we properly account for these extra constant factors floating around, our strategy to perform negacyclic polynomial multiplication is to map $f$ and $g$ up to the larger ring as described, compute their <em>cyclic </em>product (modulo $x^{2N} – 1$) using the FFT, and then the result should be a degree $2N-1$ polynomial which can be reduced with one more modular reduction step to the right degree $N-1$ negacyclic product, i.e., setting $x^N = -1$, which materializes as taking the second half of the coefficients, flipping their signs, and adding them to the corresponding coefficients in the first half.</p>
<p>The code for this is:</p>
<div><pre>def negacyclic_polymul_preimage_and_map_back(p1, p2):
 p1_preprocessed = numpy.concatenate([p1, -p1])
 p2_preprocessed = numpy.concatenate([p2, -p2])
 product = fft(p1_preprocessed) * fft(p2_preprocessed)
 inverted = ifft(product)
 rounded = numpy.round(numpy.real(inverted)).astype(p1.dtype)
 return (rounded[: p1.shape[0]] - rounded[p1.shape[0] :]) // 4
</pre></div>
<p>However, this chosen mapping hides another clever trick. The product of the two preimages has enough structure that we can “read” the result off without doing the full “set $x^N = -1$” reduction step. Mapping $f$ and $g$ up to $f^*, g^*$ and taking their product modulo $(x^{2N} – 1)$ gives</p>
<p>\[ \begin{aligned} f^*g^* &amp;= -f(x^N-1) \cdot -g(x^N – 1) \\ &amp;= fg (x^N-1)^2 \\ &amp;= fg(x^{2N} – 2x^N + 1) \\ &amp;= fg(2 – 2x^N) \\ &amp;= 2(fg – x^Nfg) \end{aligned} \]</p>
<p>This has the same syntactical format as the original mapping $f \mapsto f – x^Nf$, with an extra factor of 2, and so its coefficients also have the form “repeat the coefficients and flip the sign of the second half” (times two). We can then do the “inverse mapping” by reading only the first half of the coefficients and dividing by 2.</p>
<div><pre>def negacyclic_polymul_use_special_preimage(p1, p2):
 p1_preprocessed = numpy.concatenate([p1, -p1])
 p2_preprocessed = numpy.concatenate([p2, -p2])
 product = fft(p1_preprocessed) * fft(p2_preprocessed)
 inverted = ifft(product)
 rounded = numpy.round(0.5 * numpy.real(inverted)).astype(p1.dtype)
 return rounded[: p1.shape[0]]
</pre></div>
<p>Our chosen mapping $f \mapsto f-x^Nf$ is not particularly special, except that it uses a small number of pre and post-processing operations. For example, if you instead used the mapping $f \mapsto 2f + x^Nf$ (which would map back to $f$ exactly), then the FFT product would result in $5fg + 4x^Nfg$ in the larger ring. You can still read off the coefficients as before, but you’d have to divide by 5 instead of 2 (which, the superstitious would say, is harder). It seems that “double and negate” followed by “halve and take first half” is the least amount of pre/post processing possible.</p>
<h2>Negacyclic polynomials with a “twist”</h2>
<p>The previous section identified a nice mapping (or embedding) of the input polynomials into a larger ring. But studying that shows some symmetric structure in the FFT output. I.e., the coefficients of $f$ and $g$ are repeated twice, with some scaling factors. It also involves taking an FFT of two $2N$-dimensional vectors when we start from two $N$-dimensional vectors.</p>
<p>This sort of situation should make you think that we can do this more efficiently, either by using a smaller size FFT or by packing some data into the complex part of the input, and indeed we can do both. </p>
<p>[Aside: it’s well known that if all the entries of an FFT input are real, then the result also has symmetry that can be exploted for efficiency by reframing the problem as a size-N/2 FFT in some cases, and just removing half the FFT algorithm’s steps in other cases, see <a href="https://en.wikipedia.org/wiki/Fast_Fourier_transform#FFT_algorithms_specialized_for_real_or_symmetric_data">Wikipedia for more</a>]</p>
<p>This technique was explained in <a href="http://cr.yp.to/lineartime/multapps-20080515.pdf">Fast multiplication and its applications</a> (pdf link) by <a href="https://en.wikipedia.org/wiki/Daniel_J._Bernstein">Daniel Bernstein</a>, a prominent cryptographer who <a href="https://cr.yp.to/2005-590.html">specializes in cryptography performance</a>, and whose work appears in widely-used standards like TLS, OpenSSH, and he designed a <a href="https://en.wikipedia.org/wiki/Curve25519">commonly used elliptic curve</a> for cryptography.</p>
<p>[Aside: Bernstein cites this technique as using something called the “<a href="https://cr.yp.to/arith/tangentfft-20070809.pdf">Tangent FFT</a> (pdf link).” This is a drop-in FFT replacement he invented that is faster than previous best (split-radix FFT), and Bernstein uses it mainly to give a precise expression for the number of operations required to do the multiplication end to end. We will continue to use the numpy FFT implementation, since in this article I’m just focusing on how to express negacyclic multiplication in terms of the FFT. Also worth noting both the Tangent FFT and “Fast multiplication” papers frame their techniques—including FFT algorithm implementations!—in terms of polynomial ring factorizations and mappings. Be still, my beating cardioid.]</p>
<p>In terms of polynomial mappings, we start from the ring $\mathbb{R}[x] / (x^N + 1)$, where $N$ is a power of 2. We then pick a reversible mapping from $\mathbb{R}[x]/(x^N + 1) \to \mathbb{C}[x]/(x^{N/2} – 1)$ (note the field change from real to complex), apply the FFT to the image of the mapping, and reverse appropriately it at the end.</p>
<p>One such mapping takes two steps, first mapping $\mathbb{R}[x]/(x^N + 1) \to \mathbb{C}[x]/(x^{N/2} – i)$ and then from $\mathbb{C}[x]/(x^{N/2} – i) \to \mathbb{C}[x]/(x^{N/2} – 1)$. The first mapping is as easy as the last section, because $(x^N + 1) = (x^{N/2} + i) (x^{N/2} – i)$, and so we can just set $x^{N/2} = i$ and reduce the polynomial. This as the effect of making the second half of the polynomial’s coefficients become the complex part of the first half of the coefficients.</p>
<p>The second mapping is more nuanced, because we’re not just reducing via factorization. And we can’t just map $i \mapsto 1$ generically, because that would reduce complex numbers down to real values. Instead, we observe that (momentarily using an arbitrary degree $k$ instead of $N/2$), for any polynomial $f \in \mathbb{C}[x]$, the remainder of $f \mod x^k-i$ uniquely determines the remainder of $f \mod x^k – 1$ via the change of variables $x \mapsto \omega_{4k} x$, where $\omega_{4k}$ is a $4k$-th primitive root of unity $\omega_{4k} = e^{\frac{2 \pi i}{4k}}$. Spelling this out in more detail: if $f(x) \in \mathbb{C}[x]$ has remainder $f(x) = g(x) + h(x)(x^k – i)$ for some polynomial $h(x)$, then</p>
<p>\[ \begin{aligned} f(\omega_{4k}x) &amp;= g(\omega_{4k}x) + h(\omega_{4k}x)((\omega_{4k}x)^{k} – i) \\ &amp;= g(\omega_{4k}x) + h(\omega_{4k}x)(e^{\frac{\pi i}{2}} x^k – i) \\ &amp;= g(\omega_{4k}x) + i h(\omega_{4k}x)(x^k – 1) \\ &amp;= g(\omega_{4k}x) \mod (x^k – 1) \end{aligned} \] </p>
<p>Translating this back to $k=N/2$, the mapping from $\mathbb{C}[x]/(x^{N/2} – i) \to \mathbb{C}[x]/(x^{N/2} – 1)$ is $f(x) \mapsto f(\omega_{2N}x)$. And if $f = f_0 + f_1x + \dots + f_{N/2 – 1}x^{N/2 – 1}$, then the mapping involves multiplying each coefficient $f_k$ by $\omega_{2N}^k$.</p>
<p>When you view polynomials as if they were a simple vector of their coefficients, then this operation $f(x) \mapsto f(\omega_{k}x)$ looks like $(a_0, a_1, \dots, a_n) \mapsto (a_0, \omega_{k} a_1, \dots, \omega_k^n a_n)$. Bernstein calls the operation a <em>twist</em> of $\mathbb{C}^n$, which I mused about in <a href="https://mathstodon.xyz/@j2kun/109350252331726394">this Mathstodon thread</a>.</p>
<p>What’s most important here is that each of these transformations are invertible. The first because the top half coefficients end up in the complex parts of the polynomial, and the second because the mapping $f(x) \mapsto f(\omega_{2N}^{-1}x)$ is an inverse. Together, this makes the preprocessing and postprocessing exact inverses of each other. The code is then</p>
<div><pre>def negacyclic_polymul_complex_twist(p1, p2):
 n = p2.shape[0]
 primitive_root = primitive_nth_root(2 * n)
 root_powers = primitive_root ** numpy.arange(n // 2)
 p1_preprocessed = (p1[: n // 2] + 1j * p1[n // 2 :]) * root_powers
 p2_preprocessed = (p2[: n // 2] + 1j * p2[n // 2 :]) * root_powers
 p1_ft = fft(p1_preprocessed)
 p2_ft = fft(p2_preprocessed)
 prod = p1_ft * p2_ft
 ifft_prod = ifft(prod)
 ifft_rotated = ifft_prod * primitive_root ** numpy.arange(0, -n // 2, -1)
 return numpy.round(
 numpy.concatenate([numpy.real(ifft_rotated), numpy.imag(ifft_rotated)])
 ).astype(p1.dtype)
</pre></div>
<p>And so, at the cost of a bit more pre- and postprocessing, we can negacyclically multiply two degree $N-1$ polynomials using an FFT of length $N/2$. In theory, no information is wasted and this is optimal.</p>
<h2>And finally, a simple matrix multiplication</h2>
<p>The last technique I wanted to share is <em>not </em>based on the FFT, but it’s another method for doing negacyclic polynomial multiplication that has come in handy in situations where I am unable to use FFTs. I call it the <em>Toeplitz</em> method, because one of the polynomials is converted to a <a href="https://en.wikipedia.org/wiki/Toeplitz_matrix">Toeplitz matrix</a>. Sometimes I hear it referred to as a <a href="https://en.wikipedia.org/wiki/Circulant_matrix"><em>circulant matrix</em></a> technique, but due to the negacyclic sign flip, I don’t think it’s a fully accurate term.</p>
<p>The idea is to put the coefficients of one polynomial $f(x) = f_0 + f_1x + \dots + f_{N-1}x^{N-1}$ into a matrix as follows:</p>
<p>\[ \begin{pmatrix} f_0 &amp; -f_{N-1} &amp; \dots &amp; -f_1 \\ f_1 &amp; f_0 &amp; \dots &amp; -f_2 \\ \vdots &amp; \vdots &amp; \ddots &amp; \vdots \\ f_{N-1} &amp; f_{N-2} &amp; \dots &amp; f_0 \end{pmatrix} \]</p>
<p>The polynomial coefficients are written down in the first column unchanged, then in each subsequent column, the coefficients are cyclically shifted down one, and the term that wraps around the top has its sign flipped. When the second polynomial is treated as a vector of its coefficients, say, $g(x) = g_0 + g_1x + \dots + g_{N-1}x^{N-1}$, then the matrix-vector product computes their negacyclic product (as a vector of coefficients):</p>
<p>\[ \begin{pmatrix} f_0 &amp; -f_{N-1} &amp; \dots &amp; -f_1 \\ f_1 &amp; f_0 &amp; \dots &amp; -f_2 \\ \vdots &amp; \vdots &amp; \ddots &amp; \vdots \\ f_{N-1} &amp; f_{N-2} &amp; \dots &amp; f_0 \end{pmatrix} \begin{pmatrix} g_0 \\ g_1 \\ \vdots \\ g_{N-1} \end{pmatrix} \]</p>
<p>This works because each row $j$ corresponds to one output term $x^j$, and the cyclic shift for that row accounts for the degree-wrapping, with the sign flip accounting for the negacyclic part. (If there were no sign attached, this method could be used to compute a cyclic polynomial product).</p>
<p>The Python code for this is</p>
<div><pre>def cylic_matrix(c: numpy.array) -&gt; numpy.ndarray:
 """Generates a cyclic matrix with each row of the input shifted.
 For input: [1, 2, 3], generates the following matrix:
 [[1 2 3]
 [2 3 1]
 [3 1 2]]
 """
 c = numpy.asarray(c).ravel()
 a, b = numpy.ogrid[0 : len(c), 0 : -len(c) : -1]
 indx = a + b
 return c[indx]
def negacyclic_polymul_toeplitz(p1, p2):
 n = len(p1)
 # Generates a sign matrix with 1s below the diagonal and -1 above.
 up_tri = numpy.tril(numpy.ones((n, n), dtype=int), 0)
 low_tri = numpy.triu(numpy.ones((n, n), dtype=int), 1) * -1
 sign_matrix = up_tri + low_tri
 cyclic_matrix = cylic_matrix(p1)
 toeplitz_p1 = sign_matrix * cyclic_matrix
 return numpy.matmul(toeplitz_p1, p2)
</pre></div>
<p>Obviously on most hardware this would be less efficient than an FFT-based method (and there is some relationship between circulant matrices and Fourier Transforms, see <a href="https://en.wikipedia.org/wiki/Circulant_matrix">Wikipedia</a>). But in some cases—when the polynomials are small, or one of the two polynomials is static, or a particular hardware choice doesn’t handle FFTs with high-precision floats very well, or you want to take advantage of natural parallelism in the matrix-vector product—this method can be useful. It’s also simpler to reason about.</p>
<p>Until next time!</p>
	</div>||||I|||| Math ∩ Programming

 Navigation

 Skip to content
 * Home
 * Main Content
 * Primers
 * Research
 * Program Gallery
 * Proof Gallery
 * About the Author

 Post navigation

 ← Older posts

 Featured Posts

 Featured | Posted by j2kun
  
 Making Hybrid Images Neural Networks Elliptic Curves 
 and Backpropagation and Cryptography 
  
 Probably Approximately 
 Bezier Curves and Picasso Computing Homology Correct – A Formal Theory
 of Learning 
 

 Share this:

 * Click to share on Facebook (Opens in new window)
 * Click to share on Reddit (Opens in new window)
 * Click to share on Twitter (Opens in new window)
 * More
 * 

 Like this:

 Like Loading...
 Posted in General Tagged featured , mathematics , programming

 Estimating the Security of Ring Learning with Errors (RLWE)

 Posted on December 28, 2022 by j2kun

 This article was written by my colleague, Cathie Yun. Cathie is an applied cryptographer and security engineer, currently working with me to make fully homomorphic encryption a reality at Google. She’s also done a lot of cool stuff with zero knowledge proofs.

 In previous articles, we’ve discussed techniques used in Fully Homomorphic Encryption (FHE) schemes. The basis for many FHE schemes, as well as other privacy-preserving protocols, is the Learning With Errors (LWE) problem. In this article, we’ll talk about how to estimate the security of lattice-based schemes that rely on the hardness of LWE, as well as its widely used variant, Ring LWE (RLWE).

 A previous article on modulus switching introduced LWE encryption, but as a refresher:

 Reminder of LWE

 A literal repetition from the modulus switching article. The LWE encryption scheme I’ll use has the following parameters:

 * A plaintext space $\mathbb{Z}/q\mathbb{Z}$, where $q \geq 2$ is a positive integer. This is the space that the underlying message comes from.
 * An LWE dimension $n \in \mathbb{N}$.
 * A discrete Gaussian error distribution $ D$ with a mean of zero and a fixed standard deviation.

 An LWE secret key is defined as a vector in $\{0, 1\}^n$ (uniformly sampled). An LWE ciphertext is defined as a vector $a = (a_1, \dots, a_n)$, sampled uniformly over $(\mathbb{Z} / q\mathbb{Z})^n$, and a scalar $b = \langle a, s \rangle + m + e$, where $e$ is drawn from $D$ and all arithmetic is done modulo $q$. Note that $e$ must be small for the encryption to be valid.

 Learning With Errors (LWE) security

 Choosing appropriate LWE parameters is a nontrivial challenge when designing and implementing LWE based schemes, because there are conflicting requirements of security, correctness, and performance. Some of the parameters that can be manipulated are the LWE dimension $n$, error distribution $D$ (referred to in the next few sections as $X_e$), secret distribution $X_s$, and plaintext modulus $q$.

 Lattice Estimator

 Here is where the Lattice Estimator tool comes to our assistance! The lattice estimator is a Sage module written by a group of lattice cryptography researchers which estimates the concrete security of Learning with Errors (LWE) instances.

 For a given set of LWE parameters, the Lattice Estimator calculates the cost of all known efficient lattice attacks – for example, the Primal, Dual, and Coded-BKW attacks. It returns the estimated number of “rops” or “ring operations” required to carry out each attack; the attack that is the most efficient is the one that determines the security parameter. The bits of security for the parameter set can be calculated as $\log_2(\text{rops})$ for the most efficient attack.

 Running the Lattice Estimator

 For example, let’s estimate the security of the security parameters originally published for the popular TFHE scheme:

 
 n = 630
 q = 2^32
 Xs = UniformMod(2)
 Xe = DiscreteGaussian(stddev=2^17)
 

 After installing the Lattice Estimator and sage, we run the following commands in sage:

 
 > from estimator import *
 > schemes.TFHE630
 LWEParameters(n=630, q=4294967296, Xs=D(σ=0.50, μ=-0.50), Xe=D(σ=131072.00), m=+Infinity, tag='TFHE630')
 > _ = LWE.estimate(schemes.TFHE630)
 bkw :: rop: ≈2^153.1, m: ≈2^139.4, mem: ≈2^132.6, b: 4, t1: 0, t2: 24, ℓ: 3, #cod: 552, #top: 0, #test: 78, tag: coded-bkw
 usvp :: rop: ≈2^124.5, red: ≈2^124.5, δ: 1.004497, β: 335, d: 1123, tag: usvp
 bdd :: rop: ≈2^131.0, red: ≈2^115.1, svp: ≈2^131.0, β: 301, η: 393, d: 1095, tag: bdd
 bdd_hybrid :: rop: ≈2^185.3, red: ≈2^115.9, svp: ≈2^185.3, β: 301, η: 588, ζ: 0, |S|: 1, d: 1704, prob: 1, ↻: 1, tag: hybrid
 bdd_mitm_hybrid :: rop: ≈2^265.5, red: ≈2^264.5, svp: ≈2^264.5, β: 301, η: 2, ζ: 215, |S|: ≈2^189.2, d: 1489, prob: ≈2^-146.6, ↻: ≈2^148.8, tag: hybrid
 dual :: rop: ≈2^128.7, mem: ≈2^72.0, m: 551, β: 346, d: 1181, ↻: 1, tag: dual
 dual_hybrid :: rop: ≈2^119.8, mem: ≈2^115.5, m: 516, β: 314, d: 1096, ↻: 1, ζ: 50, tag: dual_hybrid
 

 In this example, the most efficient attack is the dual_hybrid attack. It uses 2^119.8 ring operations, and so these parameters provide 119.8 bits of security. The reader may notice that the TFHE website claims those parameters give 128 bits of security. This discrepancy is due to the fact that they used an older library (the LWE estimator, which is no longer maintained), which doesn’t take into account the most up-to-date lattice attacks.

 For further reading, Benjamin Curtis wrote an article about parameter selection for the CONCRETE implementation of the TFHE scheme. Benjamin Curtis, Martin Albrecht, and other researchers also used the Lattice Estimator to estimate all the LWE and NTRU schemes.

 Ring Learning with Errors (RLWE) security

 It is often desirable to use Ring LWE instead of LWE, for greater efficiency and smaller key sizes (as Chris Peikert illustrates via meme). We’d like to estimate the security of a Ring LWE scheme, but it wasn’t immediately obvious to us how to do this, since the Lattice Estimator only operates over LWE instances. In order to use the Lattice Estimator for this security estimate, we first needed to do a reduction from the RLWE instance to an LWE instance.

 Attempted RLWE to LWE reduction

 Given an RLWE instance with $ \text{RLWE_dimension} = k $ and $ \text{poly_log_degree} = N $, we can create a relation that looks like an LWE instance of $ \text{LWE_dimension} = N * k $ with the same security, as long as $N$ is a power of 2 and there are no known attacks that target the ring structure of RLWE that are more efficient than the best LWE attacks. Note: $N$ must be a power of 2 so that $x^N+1$ is a cyclotomic polynomial.

 An RLWE encryption has the following form: $ (a_0(x), a_1(x), … a_{k-1}(x), b(x)) $

 * Public polynomials: $ a_0(x), a_1(x), \dots a_{k-1}(x) \overset{{\scriptscriptstyle\$}}{\leftarrow} (\mathbb{Z}/{q \mathbb{Z}[x]} ) / (x^N + 1)^k$
 * Secret (binary) polynomials: $ s_0(x), s_1(x), \dots s_{k-1}(x) \overset{{\scriptscriptstyle\$}}{\leftarrow} (\mathbb{B}_N[x])^k$
 * Error: $ e(x) \overset{{\scriptscriptstyle\$}}{\leftarrow} \chi_e$
 * RLWE instance: $ b(x) = \sum_{i=0}^{k-1} a_i(x) \cdot s_i(x) + e(x) \in (\mathbb{Z}/{q \mathbb{Z}[x]} ) / (x^N + 1)$

 We would like to express this in the form of an LWE encryption. We can make start with the simple case, where $ k=1 $. Therefore, we will only be working with the zero-entry polynomials, $a_0(x)$ and $s_0(x)$. (For simplicity, in the next example you can ignore the zero-subscript and think of them as $a(x)$ and $s(x)$).

 Naive reduction for $k=1$ (wrong!)

 Naively, if we simply defined the LWE $A$ matrix to be a concatenation of the coefficients of the RLWE polynomial $a(x)$, we get:

 $$ A_{\text{LWE}} = ( a_{0, 0}, a_{0, 1}, \dots a_{0, N-1} ) $$

 We can do the same for the LWE $s$ vector:

 $$ s_{\text{LWE}} = ( s_{0, 0}, s_{0, 1}, \dots s_{0, N-1} ) $$

 But this doesn’t give us the value of $b_{LWE}$ for the LWE encryption that we want. In particular, the first entry of $b_{LWE}$, which we can call $b_{\text{LWE}, 0}$, is simply a product of the first entries of $a_0(x)$ and $s_0(x)$:

 $$ b_{\text{LWE}, 0} = a_{0, 0} \cdot s_{0, 0} + e_0 $$

 However, we want $b_{\text{LWE}, 0}$ to be a sum of the products of all the coefficients of $a_0(x)$ and $s_0(x)$ that give us a zero-degree coefficient mod $x^N + 1$. This modulus is important because it causes the product of high-degree monomials to “wrap around” to smaller degree monomials because of the negacyclic property, such that $x^N \equiv -1 \mod x^N + 1$. So the constant term $b_{\text{LWE}, 0}$ should include all of the following terms:

 $$\begin{aligned}
 b_{\text{LWE}, 0} = & a_{0, 0} \cdot s_{0, 0} \\
 – & a_{0, 1} \cdot s_{0, N-1} \\
 – & a_{0, 2} \cdot s_{0, N-2} \\
 – & \dots \\
 – & a_{0, N-1} \cdot s_{0, 1}\\
 + & e_0\\
 \end{aligned}
 $$

 Improved reduction for $k=1$

 We can achieve the desired value of $b_{\text{LWE}}$ by more strategically forming a matrix $A_{\text{LWE}}$, to reflect the negacyclic property of our polynomials in the RLWE space. We can keep the naive construction for $s_\text{LWE}$.

 $$ A_{\text{LWE}} =
 \begin{pmatrix}
 a_{0, 0} & -a_{0, N-1} & -a_{0, N-2} & \dots & -a_{0, 1}\\
 a_{0, 1} & a_{0, 0} & -a_{0, N-1} & \dots & -a_{0, 2}\\
 \vdots & \ddots & & & \vdots \\
 a_{0, N-1} & \dots & & & a_{0, 0} \\
 \end{pmatrix}
 $$

 This definition of $A_\text{LWE}$ gives us the desired value for $b_\text{LWE}$, when $b_{\text{LWE}}$ is interpreted as the coefficients of a polynomial. As an example, we can write out the elements of the first row of $b_\text{LWE}$:

 $$
 \begin{aligned}
 b_{\text{LWE}, 0} = & \sum_{i=0}^{N-1} A_{\text{LWE}, 0, i} \cdot s_{0, i} + e_0 \\
 b_{\text{LWE}, 0} = & a_{0, 0} \cdot s_{0, 0} \\
 – & a_{0, 1} \cdot s_{0, N-1} \\
 – & a_{0, 2} \cdot s_{0, N-2} \\
 – & \dots \\
 – & a_{0, N-1} \cdot s_{0, 1}\\
 + & e_0 \\
 \end{aligned}
 $$

 Generalizing for all $k$

 In the generalized $k$ case, we have the RLWE equation:

 $$ b(x) = a_0(x) \cdot s_0(x) + a_1(x) \cdot s_1(x) \cdot a_{k-1}(x) \cdot s_{k-1}(x) + e(x) $$

 We can construct the LWE elements as follows:

 $$A_{\text{LWE}} =
 \left ( \begin{array}{c|c|c|c}
 A_{0, \text{LWE}} & A_{1, \text{LWE}} & \dots & A_{k-1, \text{LWE}} \end{array}
 \right )
 $$

 where each sub-matrix is the construction from the previous section:

 $$ A_{\text{LWE}} =
 \begin{pmatrix}
 a_{i, 0} & -a_{i, N-1} & -a_{i, N-2} & \dots & -a_{i, 1}\\
 a_{i, 1} & a_{i, 0} & -a_{i, N-1} & \dots & -a_{i, 2}\\
 \vdots & \ddots & & & \vdots \\
 a_{i, N-1} & \dots & & & a_{i, 0} \\
 \end{pmatrix}
 $$

 And the secret keys are stacked similarly:

 $$ s_{\text{LWE}} = ( s_{0, 0}, s_{0, 1}, \dots s_{0, N-1} \mid s_{1, 0}, s_{1, 1}, \dots s_{1, N-1} \mid \dots ) $$

 This is how we can reduce an RLWE instance with RLWE dimension $k$ and polynomial modulus degree $N$, to a relation that looks like an LWE instance of LWE dimension $N * k$.

 Caveats and open research

 This reduction does not result in a correctly formed LWE instance, since an LWE instance would have a matrix $A$ that is randomly sampled, whereas the reduction results in an matrix $A$ that has cyclic structure, due to the cyclic property of the RLWE instance. This is why I’ve been emphasizing that the reduction produces an instance that looks like LWE. All currently known attacks on RLWE do not take advantage of the structure, but rather directly attack this transformed LWE instance. Whether the additional ring structure can be exploited in the design of more efficient attacks remains an open question in the lattice cryptography research community.

 In her PhD thesis, Rachel Player mentions the RLWE to LWE security reduction:

 In order to try to pick parameters in Ring-LWE-based schemes (FHE or otherwise) that we hope are sufficiently secure, we can choose parameters such that the underlying Ring-LWE instance should be hard to solve according to known attacks. Each Ring-LWE sample can be used to extract $n$ LWE samples. To the best of our knowledge, the most powerful attacks against $d$-sample Ring-LWE all work by instead attacking the $nd$-sample LWE problem. When estimating the security of a particular set of Ring-LWE parameters we therefore estimate the security of the induced set of LWE parameters.

 This indicates that we can do this reduction for certain RLWE instances. However, we must be careful to ensure that the polynomial modulus degree $N$ is a power of two, because otherwise the error distribution “breaks”, as my colleague Baiyu Li explained to me in conversation:

 The RLWE problem is typically defined in using the ring of integers of the cyclotomic field $\mathbb{Q}[X]/(f(X))$, where $f(X)$ is a cyclotomic polynomial of degree $k=\phi(N)$ (where $\phi$ is Euler’s totient function), and the error is a spherical Gaussian over the image of the canonical embedding into the complex numbers $\mathbb{C}^k$ (basically the images of primitive roots of unity under $f$). In many cases we set $N$ to be a power of 2, thus $f(X)=X^{N/2}+1$, since the canonical embedding for such $N$ has a nice property that the preimage of the spherical Gaussian error is also a spherical Gaussian over the coefficients of polynomials in $\mathbb{Q}[X]/(f(X))$. So in this case we can sample $k=N/2$ independent Gaussian numbers and use them as the coefficients of the error polynomial $e(x)$. For $N$ not a power of 2, $f(X)$ may have some low degree terms, and in order to get the spherical Gaussian with the same variance $s^2$ in the canonical embedding, we probably need to use a larger variance when sampling the error polynomial coefficients.

 The RLWE we frequently use in practice is actually a specialized version called “polynomial LWE”, and instantiated with $N$ = power of 2 and so $f(X)=X^{N/2}+1$. For other parameters the two are not exactly the same. This paper has some explanations: https://eprint.iacr.org/2018/170.pdf

 The error distribution “breaks” if $N$ is not a power of 2 due to the fact that the precise form of RLWE is not defined on integer polynomial rings $R = \mathbb{Z}[X]/(f(X))$, but is defined on its dual (or the dual in the underlying number field, which is a fractional ideal of $\mathbb{Q}[X]/(f(x))$), and the noise distribution is on the Minkowski embedding of this dual ring. For non-power of 2 $N$, the product mod $f$ of two small polynomials in $\mathbb{Q}[X]/(f(x))$ may be large, where small/large means their L2 norm on the coefficient vector. This means that in order to sample the required noise distribution, you may need a skewed coefficient distribution. Only when $N$ is a power of 2, the dual of $R$ is a scaling of $R$, and distance in the embedding of $R^{\text{dual}}$ is preserved in $R$, and so we can just sample iid gaussian coefficient to get the required noise.

 Because working with a power-of-two RLWE polynomial modulus gives “nice” error behavior, this parameter choice is often recommended and chosen for concrete instantiations of RLWE. For example, the Homomorphic Encryption Standard
 recommends and only analyzes the security of parameters for power-of-two cyclotomic fields for use in homomorphic encryption (though future versions of the standard aim to extend the security analysis to generic cyclotomic rings):

 We stress that when the error is chosen from sufficiently wide and “well spread” distributions that match the ring at hand, we do not have meaningful attacks on RLWE that are better than LWE attacks, regardless of the ring. For power-of-two cyclotomics, it is sufficient to sample the noise in the polynomial basis, namely choosing the coefficients of the error polynomial $e \in \mathbb{Z}[x] / \phi_k(x)$ independently at random from a very “narrow” distribution.

 Existing works analyzing and targeting the ring structure of RLWE include:

 * How (Not) to Instantiate Ring-LWE
 * Challenges for RLWE
 * On the Ring-LWE and Polynomial-LWE Problems

 It would of course be great to have a definitive answer on whether we can be confident using this RLWE to LWE reduction to estimate the security of RLWE based schemes. In the meantime, we have seen many Fully Homomorphic Encryption (FHE) schemes using this RLWE to LWE reduction, and we hope that this article helps explain how that reduction works and the existing open questions around this approach.

 Share this:

 * Click to share on Facebook (Opens in new window)
 * Click to share on Reddit (Opens in new window)
 * Click to share on Twitter (Opens in new window)
 * More
 * 

 Like this:

 Like Loading...
 Posted in Cryptography , Ring Theory Tagged cryptography , lattice cryptography , learning with errors , lwe , mathematics , programming , ring learning with errors , rlwe , sage , security Leave a comment

 Negacyclic Polynomial Multiplication

 Posted on December 9, 2022 by j2kun

 In this article I’ll cover three techniques to compute special types of polynomial products that show up in lattice cryptography and fully homomorphic encryption. Namely, the negacyclic polynomial product, which is the product of two polynomials in the quotient ring $\mathbb{Z}[x] / (x^N + 1)$. As a precursor to the negacyclic product, we’ll cover the simpler cyclic product.

 All of the Python code written for this article is on GitHub.

 The DFT and Cyclic Polynomial Multiplication

 A recent program gallery piece showed how single-variable polynomial multiplication could be implemented using the Discrete Fourier Transform (DFT). This boils down to two observations:

 1. The product of two polynomials $f, g$ can be computed via the convolution of the coefficients of $f$ and $g$.
 2. The Convolution Theorem, which says that the Fourier transform of a convolution of two signals $f, g$ is the point-wise product of the Fourier transforms of the two signals. (The same holds for the DFT)

 This provides a much faster polynomial product operation than one could implement using the naïve polynomial multiplication algorithm (though see the last section for an implementation anyway). The DFT can be used to speed up large integer multiplication as well.

 A caveat with normal polynomial multiplication is that one needs to pad the input coefficient lists with enough zeros so that the convolution doesn’t “wrap around.” That padding results in the output having length at least as large as the sum of the degrees of $f$ and $g$ (see the program gallery piece for more details).

 If you don’t pad the polynomials, instead you get what’s called a cyclic polynomial product. More concretely, if the two input polynomials $f, g$ are represented by coefficient lists $(f_0, f_1, \dots, f_{N-1}), (g_0, g_1, \dots, g_{N-1})$ of length $N$ (implying the inputs are degree at most $N-1$, i.e., the lists may end in a tail of zeros), then the Fourier Transform technique computes

 \[ f(x) \cdot g(x) \mod (x^N – 1) \]

 This modulus is in the sense of a quotient ring $\mathbb{Z}[x] / (x^N – 1)$, where $(x^N – 1)$ denotes the ring ideal generated by $x^N-1$, i.e., all polynomials that are evenly divisible by $x^N – 1$. A particularly important interpretation of this quotient ring is achieved by interpreting the ideal generator $x^N – 1$ as an equation $x^N – 1 = 0$, also known as $x^N = 1$. To get the canonical ring element corresponding to any polynomial $h(x) \in \mathbb{Z}[x]$, you “set” $x^N = 1$ and reduce the polynomial until there are no more terms with degree bigger than $N-1$. For example, if $N=5$ then $x^{10} + x^6 – x^4 + x + 2 = -x^4 + 2x + 3$ (the $x^{10}$ becomes 1, and $x^6 = x$).

 To prove the DFT product computes a product in this particular ring, note how the convolution theorem produces the following formula, where $\textup{fprod}(f, g)$ denotes the process of taking the Fourier transform of the two coefficient lists, multiplying them entrywise, and taking a (properly normalized) inverse FFT, and $\textup{fprod}(f, g)(j)$ is the $j$-th coefficient of the output polynomial:

 \[ \textup{fprod}(f, g)(j) = \sum_{k=0}^{N-1} f_k g_{j-k \textup{ mod } N} \]

 In words, the output polynomial coefficient $j$ equals the sum of all products of pairs of coefficients whose indices sum to $j$ when considered “wrapping around” $N$. Fixing $j=1$ as an example, $\textup{fprod}(f, g)(1) = f_0 g_1 + f_1g_0 + f_2 g_{N-1} + f_3 g_{N-2} + \dots$. This demonstrates the “set $x^N = 1$” interpretation above: the term $f_2 g_{N-1}$ corresponds to the product $f_2x^2 \cdot g_{N-1}x^{N-1}$, which contributes to the $x^1$ term of the polynomial product if and only if $x^{2 + N-1} = x$, if and only if $x^N = 1$.

 To achieve this in code, we simply use the version of the code from the program gallery piece, but fix the size of the arrays given to numpy.fft.fft in advance. We will also, for simplicity, assume the $N$ one wishes to use is a power of 2. The resulting code is significantly simpler than the original program gallery code (we omit zero-padding to length $N$ for brevity).

 
 import numpy
 from numpy.fft import fft, ifft
 
 def cyclic_polymul(p1, p2, N):
 """Multiply two integer polynomials modulo (x^N - 1).
 
 p1 and p2 are arrays of coefficients in degree-increasing order.
 """
 assert len(p1) == len(p2) == N
 product = fft(p1) * fft(p2)
 inverted = ifft(product)
 return numpy.round(numpy.real(inverted)).astype(numpy.int32)
 

 As a side note, there’s nothing that stops this from working with polynomials that have real or complex coefficients, but so long as we use small magnitude integer coefficients and round at the end, I don’t have to worry about precision issues (hat tip to Brad Lucier for suggesting an excellent paper by Colin Percival, “Rapid multiplication modulo the sum and difference of highly composite numbers“, which covers these precision issues in detail).

 Negacyclic polynomials, DFT with duplication

 Now the kind of polynomial quotient ring that shows up in cryptography is critically not $\mathbb{Z}[x]/(x^N-1)$, because that ring has enough easy-to-reason-about structure that it can’t hide secrets. Instead, cryptographers use the ring $\mathbb{Z}[x]/(x^N+1)$ (the minus becomes a plus), which is believed to be more secure for cryptography—although I don’t have a great intuitive grasp on why.

 The interpretation is similar here as before, except we “set” $x^N = -1$ instead of $x^N = 1$ in our reductions. Repeating the above example, if $N=5$ then $x^{10} + x^6 – x^4 + x + 2 = -x^4 + 3$ (the $x^{10}$ becomes $(-1)^2 = 1$, and $x^6 = -x$). It’s called negacyclic because as a term $x^k$ passes $k \geq N$, it cycles back to $x^0 = 1$, but with a sign flip.

 The negacyclic polynomial multiplication can’t use the DFT without some special hacks. The first and simplest hack is to double the input lists with a negation. That is, starting from $f(x) \in \mathbb{Z}[x]/(x^N+1)$, we can define $f^*(x) = f(x) – x^Nf(x)$ in a different ring $\mathbb{Z}[x]/(x^{2N} – 1)$ (and similarly for $g^*$ and $g$).

 Before seeing how this causes the DFT to (almost) compute a negacyclic polynomial product, some math wizardry. The ring $\mathbb{Z}[x]/(x^{2N} – 1)$ is special because it contains our negacyclic ring as a subring. Indeed, because the polynomial $x^{2N} – 1$ factors as $(x^N-1)(x^N+1)$, and because these two factors are coprime in $\mathbb{Z}[x]/(x^{2N} – 1)$, the Chinese remainder theorem (aka Sun-tzu’s theorem) generalizes to polynomial rings and says that any polynomial in $\mathbb{Z}[x]/(x^{2N} – 1)$ is uniquely determined by its remainders when divided by $(x^N-1)$ and $(x^N+1)$. Another way to say it is that the ring $\mathbb{Z}[x]/(x^{2N} – 1)$ factors as a direct product of the two rings $\mathbb{Z}[x]/(x^{N} – 1)$ and $\mathbb{Z}[x]/(x^{N} + 1)$.

 Now mapping a polynomial $f(x)$ from the bigger ring $(x^{2N} – 1)$ to the smaller ring $(x^{N}+1)$ involves taking a remainder of $f(x)$ when dividing by $x^{N}+1$ (“setting” $x^N = -1$ and reducing). There are many possible preimage mappings, depending on what your goal is. In this case, we actually intentionally choose a non preimage mapping, because in general to compute a preimage requires solving a system of congruences in the larger polynomial ring. So instead we choose $f(x) \mapsto f^*(x) = f(x) – x^Nf(x) = -f(x)(x^N – 1)$, which maps back down to $2f(x)$ in $\mathbb{Z}[x]/(x^{N} + 1)$. This preimage mapping has a particularly nice structure, in that you build it by repeating the polynomial’s coefficients twice and flipping the sign of the second half. It’s easy to see that the product $f^*(x) g^*(x)$ maps down to $4f(x)g(x)$.

 So if we properly account for these extra constant factors floating around, our strategy to perform negacyclic polynomial multiplication is to map $f$ and $g$ up to the larger ring as described, compute their cyclic product (modulo $x^{2N} – 1$) using the FFT, and then the result should be a degree $2N-1$ polynomial which can be reduced with one more modular reduction step to the right degree $N-1$ negacyclic product, i.e., setting $x^N = -1$, which materializes as taking the second half of the coefficients, flipping their signs, and adding them to the corresponding coefficients in the first half.

 The code for this is:

 
 def negacyclic_polymul_preimage_and_map_back(p1, p2):
 p1_preprocessed = numpy.concatenate([p1, -p1])
 p2_preprocessed = numpy.concatenate([p2, -p2])
 product = fft(p1_preprocessed) * fft(p2_preprocessed)
 inverted = ifft(product)
 rounded = numpy.round(numpy.real(inverted)).astype(p1.dtype)
 return (rounded[: p1.shape[0]] - rounded[p1.shape[0] :]) // 4
 

 However, this chosen mapping hides another clever trick. The product of the two preimages has enough structure that we can “read” the result off without doing the full “set $x^N = -1$” reduction step. Mapping $f$ and $g$ up to $f^*, g^*$ and taking their product modulo $(x^{2N} – 1)$ gives

 \[ \begin{aligned} f^*g^* &= -f(x^N-1) \cdot -g(x^N – 1) \\ &= fg (x^N-1)^2 \\ &= fg(x^{2N} – 2x^N + 1) \\ &= fg(2 – 2x^N) \\ &= 2(fg – x^Nfg) \end{aligned} \]

 This has the same syntactical format as the original mapping $f \mapsto f – x^Nf$, with an extra factor of 2, and so its coefficients also have the form “repeat the coefficients and flip the sign of the second half” (times two). We can then do the “inverse mapping” by reading only the first half of the coefficients and dividing by 2.

 
 def negacyclic_polymul_use_special_preimage(p1, p2):
 p1_preprocessed = numpy.concatenate([p1, -p1])
 p2_preprocessed = numpy.concatenate([p2, -p2])
 product = fft(p1_preprocessed) * fft(p2_preprocessed)
 inverted = ifft(product)
 rounded = numpy.round(0.5 * numpy.real(inverted)).astype(p1.dtype)
 return rounded[: p1.shape[0]]
 

 Our chosen mapping $f \mapsto f-x^Nf$ is not particularly special, except that it uses a small number of pre and post-processing operations. For example, if you instead used the mapping $f \mapsto 2f + x^Nf$ (which would map back to $f$ exactly), then the FFT product would result in $5fg + 4x^Nfg$ in the larger ring. You can still read off the coefficients as before, but you’d have to divide by 5 instead of 2 (which, the superstitious would say, is harder). It seems that “double and negate” followed by “halve and take first half” is the least amount of pre/post processing possible.

 Negacyclic polynomials with a “twist”

 The previous section identified a nice mapping (or embedding) of the input polynomials into a larger ring. But studying that shows some symmetric structure in the FFT output. I.e., the coefficients of $f$ and $g$ are repeated twice, with some scaling factors. It also involves taking an FFT of two $2N$-dimensional vectors when we start from two $N$-dimensional vectors.

 This sort of situation should make you think that we can do this more efficiently, either by using a smaller size FFT or by packing some data into the complex part of the input, and indeed we can do both.

 [Aside: it’s well known that if all the entries of an FFT input are real, then the result also has symmetry that can be exploted for efficiency by reframing the problem as a size-N/2 FFT in some cases, and just removing half the FFT algorithm’s steps in other cases, see Wikipedia for more]

 This technique was explained in Fast multiplication and its applications (pdf link) by Daniel Bernstein, a prominent cryptographer who specializes in cryptography performance, and whose work appears in widely-used standards like TLS, OpenSSH, and he designed a commonly used elliptic curve for cryptography.

 [Aside: Bernstein cites this technique as using something called the “Tangent FFT (pdf link).” This is a drop-in FFT replacement he invented that is faster than previous best (split-radix FFT), and Bernstein uses it mainly to give a precise expression for the number of operations required to do the multiplication end to end. We will continue to use the numpy FFT implementation, since in this article I’m just focusing on how to express negacyclic multiplication in terms of the FFT. Also worth noting both the Tangent FFT and “Fast multiplication” papers frame their techniques—including FFT algorithm implementations!—in terms of polynomial ring factorizations and mappings. Be still, my beating cardioid.]

 In terms of polynomial mappings, we start from the ring $\mathbb{R}[x] / (x^N + 1)$, where $N$ is a power of 2. We then pick a reversible mapping from $\mathbb{R}[x]/(x^N + 1) \to \mathbb{C}[x]/(x^{N/2} – 1)$ (note the field change from real to complex), apply the FFT to the image of the mapping, and reverse appropriately it at the end.

 One such mapping takes two steps, first mapping $\mathbb{R}[x]/(x^N + 1) \to \mathbb{C}[x]/(x^{N/2} – i)$ and then from $\mathbb{C}[x]/(x^{N/2} – i) \to \mathbb{C}[x]/(x^{N/2} – 1)$. The first mapping is as easy as the last section, because $(x^N + 1) = (x^{N/2} + i) (x^{N/2} – i)$, and so we can just set $x^{N/2} = i$ and reduce the polynomial. This as the effect of making the second half of the polynomial’s coefficients become the complex part of the first half of the coefficients.

 The second mapping is more nuanced, because we’re not just reducing via factorization. And we can’t just map $i \mapsto 1$ generically, because that would reduce complex numbers down to real values. Instead, we observe that (momentarily using an arbitrary degree $k$ instead of $N/2$), for any polynomial $f \in \mathbb{C}[x]$, the remainder of $f \mod x^k-i$ uniquely determines the remainder of $f \mod x^k – 1$ via the change of variables $x \mapsto \omega_{4k} x$, where $\omega_{4k}$ is a $4k$-th primitive root of unity $\omega_{4k} = e^{\frac{2 \pi i}{4k}}$. Spelling this out in more detail: if $f(x) \in \mathbb{C}[x]$ has remainder $f(x) = g(x) + h(x)(x^k – i)$ for some polynomial $h(x)$, then

 \[ \begin{aligned} f(\omega_{4k}x) &= g(\omega_{4k}x) + h(\omega_{4k}x)((\omega_{4k}x)^{k} – i) \\ &= g(\omega_{4k}x) + h(\omega_{4k}x)(e^{\frac{\pi i}{2}} x^k – i) \\ &= g(\omega_{4k}x) + i h(\omega_{4k}x)(x^k – 1) \\ &= g(\omega_{4k}x) \mod (x^k – 1) \end{aligned} \]

 Translating this back to $k=N/2$, the mapping from $\mathbb{C}[x]/(x^{N/2} – i) \to \mathbb{C}[x]/(x^{N/2} – 1)$ is $f(x) \mapsto f(\omega_{2N}x)$. And if $f = f_0 + f_1x + \dots + f_{N/2 – 1}x^{N/2 – 1}$, then the mapping involves multiplying each coefficient $f_k$ by $\omega_{2N}^k$.

 When you view polynomials as if they were a simple vector of their coefficients, then this operation $f(x) \mapsto f(\omega_{k}x)$ looks like $(a_0, a_1, \dots, a_n) \mapsto (a_0, \omega_{k} a_1, \dots, \omega_k^n a_n)$. Bernstein calls the operation a twist of $\mathbb{C}^n$, which I mused about in this Mathstodon thread.

 What’s most important here is that each of these transformations are invertible. The first because the top half coefficients end up in the complex parts of the polynomial, and the second because the mapping $f(x) \mapsto f(\omega_{2N}^{-1}x)$ is an inverse. Together, this makes the preprocessing and postprocessing exact inverses of each other. The code is then

 
 def negacyclic_polymul_complex_twist(p1, p2):
 n = p2.shape[0]
 primitive_root = primitive_nth_root(2 * n)
 root_powers = primitive_root ** numpy.arange(n // 2)
 
 p1_preprocessed = (p1[: n // 2] + 1j * p1[n // 2 :]) * root_powers
 p2_preprocessed = (p2[: n // 2] + 1j * p2[n // 2 :]) * root_powers
 
 p1_ft = fft(p1_preprocessed)
 p2_ft = fft(p2_preprocessed)
 prod = p1_ft * p2_ft
 ifft_prod = ifft(prod)
 ifft_rotated = ifft_prod * primitive_root ** numpy.arange(0, -n // 2, -1)
 
 return numpy.round(
 numpy.concatenate([numpy.real(ifft_rotated), numpy.imag(ifft_rotated)])
 ).astype(p1.dtype)
 

 And so, at the cost of a bit more pre- and postprocessing, we can negacyclically multiply two degree $N-1$ polynomials using an FFT of length $N/2$. In theory, no information is wasted and this is optimal.

 And finally, a simple matrix multiplication

 The last technique I wanted to share is not based on the FFT, but it’s another method for doing negacyclic polynomial multiplication that has come in handy in situations where I am unable to use FFTs. I call it the Toeplitz method, because one of the polynomials is converted to a Toeplitz matrix. Sometimes I hear it referred to as a circulant matrix technique, but due to the negacyclic sign flip, I don’t think it’s a fully accurate term.

 The idea is to put the coefficients of one polynomial $f(x) = f_0 + f_1x + \dots + f_{N-1}x^{N-1}$ into a matrix as follows:

 \[ \begin{pmatrix} f_0 & -f_{N-1} & \dots & -f_1 \\ f_1 & f_0 & \dots & -f_2 \\ \vdots & \vdots & \ddots & \vdots \\ f_{N-1} & f_{N-2} & \dots & f_0 \end{pmatrix} \]

 The polynomial coefficients are written down in the first column unchanged, then in each subsequent column, the coefficients are cyclically shifted down one, and the term that wraps around the top has its sign flipped. When the second polynomial is treated as a vector of its coefficients, say, $g(x) = g_0 + g_1x + \dots + g_{N-1}x^{N-1}$, then the matrix-vector product computes their negacyclic product (as a vector of coefficients):

 \[ \begin{pmatrix} f_0 & -f_{N-1} & \dots & -f_1 \\ f_1 & f_0 & \dots & -f_2 \\ \vdots & \vdots & \ddots & \vdots \\ f_{N-1} & f_{N-2} & \dots & f_0 \end{pmatrix} \begin{pmatrix} g_0 \\ g_1 \\ \vdots \\ g_{N-1} \end{pmatrix} \]

 This works because each row $j$ corresponds to one output term $x^j$, and the cyclic shift for that row accounts for the degree-wrapping, with the sign flip accounting for the negacyclic part. (If there were no sign attached, this method could be used to compute a cyclic polynomial product).

 The Python code for this is

 
 def cylic_matrix(c: numpy.array) -> numpy.ndarray:
 """Generates a cyclic matrix with each row of the input shifted.
 
 For input: [1, 2, 3], generates the following matrix:
 
 [[1 2 3]
 [2 3 1]
 [3 1 2]]
 """
 c = numpy.asarray(c).ravel()
 a, b = numpy.ogrid[0 : len(c), 0 : -len(c) : -1]
 indx = a + b
 return c[indx]
 
 
 def negacyclic_polymul_toeplitz(p1, p2):
 n = len(p1)
 
 # Generates a sign matrix with 1s below the diagonal and -1 above.
 up_tri = numpy.tril(numpy.ones((n, n), dtype=int), 0)
 low_tri = numpy.triu(numpy.ones((n, n), dtype=int), 1) * -1
 sign_matrix = up_tri + low_tri
 
 cyclic_matrix = cylic_matrix(p1)
 toeplitz_p1 = sign_matrix * cyclic_matrix
 return numpy.matmul(toeplitz_p1, p2)
 

 Obviously on most hardware this would be less efficient than an FFT-based method (and there is some relationship between circulant matrices and Fourier Transforms, see Wikipedia). But in some cases—when the polynomials are small, or one of the two polynomials is static, or a particular hardware choice doesn’t handle FFTs with high-precision floats very well, or you want to take advantage of natural parallelism in the matrix-vector product—this method can be useful. It’s also simpler to reason about.

 Until next time!

 Share this:

 * Click to share on Facebook (Opens in new window)
 * Click to share on Reddit (Opens in new window)
 * Click to share on Twitter (Opens in new window)
 * More
 * 

 Like this:

 Like Loading...
 Posted in Algorithms , Cryptography , Number Theory , Ring Theory Tagged complex twist , cryptography , fourier transform , mathematics , negacyclic , polynomial ring , polynomials , programming , python 1 Comment

 Polynomial Multiplication Using the FFT

 Posted on November 16, 2022 by j2kun

 Problem: Compute the product of two polynomials efficiently.

 Solution:

 
 import numpy
 from numpy.fft import fft, ifft
 
 
 def poly_mul(p1, p2):
 """Multiply two polynomials.
 
 p1 and p2 are arrays of coefficients in degree-increasing order.
 """
 deg1 = p1.shape[0] - 1
 deg2 = p1.shape[0] - 1
 # Would be 2*(deg1 + deg2) + 1, but the next-power-of-2 handles the +1
 total_num_pts = 2 * (deg1 + deg2)
 next_power_of_2 = 1 << (total_num_pts - 1).bit_length()
 
 ff_p1 = fft(numpy.pad(p1, (0, next_power_of_2 - p1.shape[0])))
 ff_p2 = fft(numpy.pad(p2, (0, next_power_of_2 - p2.shape[0])))
 product = ff_p1 * ff_p2
 inverted = ifft(product)
 rounded = numpy.round(numpy.real(inverted)).astype(numpy.int32)
 return numpy.trim_zeros(rounded, trim='b')
 

 Discussion: The Fourier Transform has a lot of applications to science, and I’ve covered it on this blog before, see the Signal Processing section of Main Content. But it also has applications to fast computational mathematics.

 The naive algorithm for multiplying two polynomials is the “grade-school” algorithm most readers will already be familiar with (see e.g., this page), but for large polynomials that algorithm is slow. It requires $O(n^2)$ arithmetic operations to multiply two polynomials of degree $n$.

 This short tip shows a different approach, which is based on the idea of polynomial interpolation. As a side note, I show the basic theory of polynomial interpolation in chapter 2 of my book, A Programmer’s Introduction to Mathematics, along with an application to cryptography called “Secret Sharing.”

 The core idea is that given $n+1$ distinct evaluations of a polynomial $p(x)$ (i.e., points $(x, p(x))$ with different $x$ inputs), you can reconstruct the coefficients of $p(x)$ exactly. And if you have two such point sets for two different polynomials $p(x), q(x)$, a valid point set of the product $(pq)(x)$ is the product of the points that have the same $x$ inputs.

 \[ \begin{aligned} p(x) &= \{ (x_0, p(x_0)), (x_1, p(x_1)), \dots, (x_n, p(x_n)) \} \\ q(x) &= \{ (x_0, q(x_0)), (x_1, q(x_1)), \dots, (x_n, q(x_n)) \} \\ (pq)(x) &= \{ (x_0, p(x_0)q(x_0)), (x_1, p(x_1)q(x_1)), \dots, (x_n, p(x_n)q(x_n)) \} \end{aligned} \]

 The above uses $=$ loosely to represent that the polynomial $p$ can be represented by the point set on the right hand side.

 So given two polynomials $p(x), q(x)$ in their coefficient forms, one can first convert them to their point forms, multiply the points, and then reconstruct the resulting product.

 The problem is that the two conversions, both to and from the coefficient form, are inefficient for arbitrary choices of points $x_0, \dots, x_n$. The trick comes from choosing special points, in such a way that the intermediate values computed in the conversion steps can be reused. This is where the Fourier Transform comes in: choose $x_0 = \omega_{N}$, the complex-N-th root of unity, and $x_k = \omega_N^k$ as its exponents. $N$ is required to be large enough so that $\omega_N$’s exponents have at least $2n+1$ distinct values required for interpolating a degree-at-most-$2n$ polynomial, and because we’re doing the Fourier Transform, it will naturally be “the next largest power of 2” bigger than the degree of the product polynomial.

 Then one has to observe that, by its very formula, the Fourier Transform is exactly the evaluation of a polynomial at the powers of the $N$-th root of unity! In formulas: if $a = (a_0, \dots, a_{n-1})$ is a list of real numbers define $p_a(x) = a_0 + a_1x + \dots + a_{n-1}x^{n-1}$. Then $\mathscr{F}(a)(k)$, the Fourier Transform of $a$ at index $k$, is equal to $p_a(\omega_n^k)$. These notes by Denis Pankratov have more details showing that the Fourier Transform formula is a polynomial evaluation (see Section 3), and this YouTube video by Reducible also has a nice exposition. This interpretation of the FT as polynomial evaluation seems to inspire quite a few additional techniques for computing the Fourier Transform that I plan to write about in the future.

 The last step is to reconstruct the product polynomial from the product of the two point sets, but because the Fourier Transform is an invertible function (and linear, too), the inverse Fourier Transform does exactly that: given a list of the $n$ evaluations of a polynomial at $\omega_n^k, k=0, \dots, n-1$, return the coefficients of the polynomial.

 This all fits together into the code above:

 1. Pad the input coefficient lists with zeros, so that the lists are a power of 2 and at least 1 more than the degree of the output product polynomial.
 2. Compute the FFT of the two padded polynomials.
 3. Multiply the result pointwise.
 4. Compute the IFFT of the product.
 5. Round the resulting (complex) values back to integers.

 Hey, wait a minute! What about precision issues?

 They are a problem when you have large numbers or large polynomials, because the intermediate values in steps 2-4 can lose precision due to the floating point math involved. This short note of Richard Fateman discusses some of those issues, and two paths forward include: deal with it somehow, or use an integer-exact analogue called the Number Theoretic Transform (which itself has issues I’ll discuss in a future, longer article).

 Postscript: I’m not sure how widely this technique is used. It appears the NTL library uses the polynomial version of Karatsuba multiplication instead (though it implements FFT elsewhere). However, I know for sure that much software involved in doing fully homomorphic encryption rely on the FFT for performance reasons, and the ones that don’t instead use the NTT.

 Share this:

 * Click to share on Facebook (Opens in new window)
 * Click to share on Reddit (Opens in new window)
 * Click to share on Twitter (Opens in new window)
 * More
 * 

 Like this:

 Like Loading...
 Posted in Algorithms , Number Theory , Program Gallery Tagged fft , fourier transform , mathematics , polynomial interpolation , polynomials , programming , python 3 Comments

 Carnival of Mathematics #209

 Posted on October 2, 2022 by j2kun

 Welcome to the 209th Carnival of Mathematics!

 209 has a few distinctions, including being the smallest number with 6 representations as a sum of 3 positive squares:

 $$\begin{aligned}209 &= 1^2 + 8^2 + 12^2 \\ &= 2^2 + 3^2 + 14^2 \\ &= 2^2 + 6^2 + 13^2 \\ &= 3^2 + 10^2 + 10^2 \\ &= 4^2 + 7^2 + 12^2 \\ &= 8^2 + 8^2 + 9^2 \end{aligned}$$

 As well as being the 43rd Ulam number, the number of partitions of 16 into relatively prime parts and the number of partitions of 63 into squares.

 Be sure to submit fun math you find in October to the next carvinal host!

 Math YouTubers

 The Heidelberg Laureate forum took place, which featured lectures from renowned mathematicians and computer scientists, like Rob Tarjan and Avi Wigderson on the CS theory side, as well as a panel discussion on post-quantum cryptography with none other than Vint Cerf, Whitfield Diffie, and Adi Shamir. All the videos are on YouTube.

 Tom Edgar, who is behind the Mathematical Visual Proofs YouTube channel, published a video (using manim) exploring for which $n$ it is possible to divide a disk into $n$ equal pieces using a straightedge and compass. It was based on a proof from Roger Nelsen’s and Claudi Alsina’s book, “Icons of Mathematics”.

 The folks at Ganit Charcha also published a talk “Fascinating Facts About Pi” from a Pi Day 2022 celebration. The video includes a question that was new to me about interpreting subsequences of pi digits as indexes and doing reverse lookups until you find a loop.

 Henry Segerman published two nice videos, including one on an illusion of a square and circle in the same shape, and a preview of a genus-2 holonomy maze (Augh, my wallet! I have both of his original holonomy mazes and my houseguests love playing with them!)

 Steve Mould published a nice video about the Chladni figures used (or adapted) in the new Lord of the Rings TV series’ title sequence.

 The Simons institute has been doing a workshop on graph limits, which aims to cover some of the theory about things like low-rank matrix completion, random graphs, and various models of networks. Their lectures are posted on their YouTube page.

 Math Twitter

 Peter Rowlett shared a nice activity with his son about distinct colorings of a square divided into four triangular regions.

 Krystal Guo showed off her approach to LiveTeX’ing lectures.

 Tamás Görbe gave a nice thread about a function that enumerates all rational numbers exactly once.

 Every math club leader should be called the Prime Minister.

 In doing research for my book, I was writing a chapter on balanced incomplete block designs, and I found a few nice tidbits in threads (thread 1, thread 2). A few here: Latin squares were on Islamic amulets from the 1200’s. The entire back catalog of “The Mathematical Scientist” journal is available on Google Drive, and through it I found an old article describing the very first use of Latin squares for experimental design, in which a man ran an experiment on what crop was best to feed his sheep during the winter months in France in the 1800’s. Finally, I determined that NFL season scheduling is done via integer linear programming.

 Math Bloggers

 Lúcás Meier published a nice article at the end of August (which I only discovered in September, it counts!) going over the details of his favorite cryptography paper “Unifying Zero-Knowledge Proofs of Knowledge”, by Ueli Maurer, which gives a single zero-knowledge protocol that generalizes Schnorr, Fiat-Shamir, and a few others for proving knowledge of logarithms and roots.

 Ralph Levien published a blog post about how to efficiently draw a decent approximation to the curve parallel to a given cubic Bezier curve. He has a previous blog post about fitting cubic Beziers to data, and a variety of other interesting graphics-inspired math articles in between articles about Rust and GPUs.

 Share this:

 * Click to share on Facebook (Opens in new window)
 * Click to share on Reddit (Opens in new window)
 * Click to share on Twitter (Opens in new window)
 * More
 * 

 Like this:

 Like Loading...
 Posted in General Tagged carnival , knot theory , mathematics , sieve , umap Leave a comment

 Post navigation

 ← Older posts
 Search

 Sign up for a mailing list to be notified of new books I'm working on

 RSS

 * RSS - Posts
 %d bloggers like this:
In this article I’ll cover three techniques to compute special types of polynomial products that show up in lattice cryptography and fully homomorphic encryption. Namely, the negacyclic polynomial product, which is the product of two polynomials in the quotient ring $\mathbb{Z}[x] / (x^N + 1)$. As a precursor to the negacyclic product, we’ll cover the simpler cyclic product.
All of the Python code written for this article is on GitHub.
The DFT and Cyclic Polynomial Multiplication
A recent program gallery piece showed how single-variable polynomial multiplication could be implemented using the Discrete Fourier Transform (DFT). This boils down to two observations:
The product of two polynomials $f, g$ can be computed via the convolution of the coefficients of $f$ and $g$.
The Convolution Theorem, which says that the Fourier transform of a convolution of two signals $f, g$ is the point-wise product of the Fourier transforms of the two signals. (The same holds for the DFT)
This provides a much faster polynomial product operation than one could implement using the naïve polynomial multiplication algorithm (though see the last section for an implementation anyway). The DFT can be used to speed up large integer multiplication as well.
A caveat with normal polynomial multiplication is that one needs to pad the input coefficient lists with enough zeros so that the convolution doesn’t “wrap around.” That padding results in the output having length at least as large as the sum of the degrees of $f$ and $g$ (see the program gallery piece for more details).
If you don’t pad the polynomials, instead you get what’s called a cyclic polynomial product. More concretely, if the two input polynomials $f, g$ are represented by coefficient lists $(f_0, f_1, \dots, f_{N-1}), (g_0, g_1, \dots, g_{N-1})$ of length $N$ (implying the inputs are degree at most $N-1$, i.e., the lists may end in a tail of zeros), then the Fourier Transform technique computes
\[ f(x) \cdot g(x) \mod (x^N – 1) \]
This modulus is in the sense of a quotient ring $\mathbb{Z}[x] / (x^N – 1)$, where $(x^N – 1)$ denotes the ring ideal generated by $x^N-1$, i.e., all polynomials that are evenly divisible by $x^N – 1$. A particularly important interpretation of this quotient ring is achieved by interpreting the ideal generator $x^N – 1$ as an equation $x^N – 1 = 0$, also known as $x^N = 1$. To get the canonical ring element corresponding to any polynomial $h(x) \in \mathbb{Z}[x]$, you “set” $x^N = 1$ and reduce the polynomial until there are no more terms with degree bigger than $N-1$. For example, if $N=5$ then $x^{10} + x^6 – x^4 + x + 2 = -x^4 + 2x + 3$ (the $x^{10}$ becomes 1, and $x^6 = x$).
To prove the DFT product computes a product in this particular ring, note how the convolution theorem produces the following formula, where $\textup{fprod}(f, g)$ denotes the process of taking the Fourier transform of the two coefficient lists, multiplying them entrywise, and taking a (properly normalized) inverse FFT, and $\textup{fprod}(f, g)(j)$ is the $j$-th coefficient of the output polynomial:
\[ \textup{fprod}(f, g)(j) = \sum_{k=0}^{N-1} f_k g_{j-k \textup{ mod } N} \]
In words, the output polynomial coefficient $j$ equals the sum of all products of pairs of coefficients whose indices sum to $j$ when considered “wrapping around” $N$. Fixing $j=1$ as an example, $\textup{fprod}(f, g)(1) = f_0 g_1 + f_1g_0 + f_2 g_{N-1} + f_3 g_{N-2} + \dots$. This demonstrates the “set $x^N = 1$” interpretation above: the term $f_2 g_{N-1}$ corresponds to the product $f_2x^2 \cdot g_{N-1}x^{N-1}$, which contributes to the $x^1$ term of the polynomial product if and only if $x^{2 + N-1} = x$, if and only if $x^N = 1$.
To achieve this in code, we simply use the version of the code from the program gallery piece, but fix the size of the arrays given to numpy.fft.fft in advance. We will also, for simplicity, assume the $N$ one wishes to use is a power of 2. The resulting code is significantly simpler than the original program gallery code (we omit zero-padding to length $N$ for brevity).
 import numpy
from numpy.fft import fft, ifft
def cyclic_polymul(p1, p2, N):
 """Multiply two integer polynomials modulo (x^N - 1).
 p1 and p2 are arrays of coefficients in degree-increasing order.
 """
 assert len(p1) == len(p2) == N
 product = fft(p1) * fft(p2)
 inverted = ifft(product)
 return numpy.round(numpy.real(inverted)).astype(numpy.int32)
 
As a side note, there’s nothing that stops this from working with polynomials that have real or complex coefficients, but so long as we use small magnitude integer coefficients and round at the end, I don’t have to worry about precision issues (hat tip to Brad Lucier for suggesting an excellent paper by Colin Percival, “Rapid multiplication modulo the sum and difference of highly composite numbers“, which covers these precision issues in detail).
Negacyclic polynomials, DFT with duplication
Now the kind of polynomial quotient ring that shows up in cryptography is critically not $\mathbb{Z}[x]/(x^N-1)$, because that ring has enough easy-to-reason-about structure that it can’t hide secrets. Instead, cryptographers use the ring $\mathbb{Z}[x]/(x^N+1)$ (the minus becomes a plus), which is believed to be more secure for cryptography—although I don’t have a great intuitive grasp on why.
The interpretation is similar here as before, except we “set” $x^N = -1$ instead of $x^N = 1$ in our reductions. Repeating the above example, if $N=5$ then $x^{10} + x^6 – x^4 + x + 2 = -x^4 + 3$ (the $x^{10}$ becomes $(-1)^2 = 1$, and $x^6 = -x$). It’s called negacyclic because as a term $x^k$ passes $k \geq N$, it cycles back to $x^0 = 1$, but with a sign flip.
The negacyclic polynomial multiplication can’t use the DFT without some special hacks. The first and simplest hack is to double the input lists with a negation. That is, starting from $f(x) \in \mathbb{Z}[x]/(x^N+1)$, we can define $f^*(x) = f(x) – x^Nf(x)$ in a different ring $\mathbb{Z}[x]/(x^{2N} – 1)$ (and similarly for $g^*$ and $g$).
Before seeing how this causes the DFT to (almost) compute a negacyclic polynomial product, some math wizardry. The ring $\mathbb{Z}[x]/(x^{2N} – 1)$ is special because it contains our negacyclic ring as a subring. Indeed, because the polynomial $x^{2N} – 1$ factors as $(x^N-1)(x^N+1)$, and because these two factors are coprime in $\mathbb{Z}[x]/(x^{2N} – 1)$, the Chinese remainder theorem (aka Sun-tzu’s theorem) generalizes to polynomial rings and says that any polynomial in $\mathbb{Z}[x]/(x^{2N} – 1)$ is uniquely determined by its remainders when divided by $(x^N-1)$ and $(x^N+1)$. Another way to say it is that the ring $\mathbb{Z}[x]/(x^{2N} – 1)$ factors as a direct product of the two rings $\mathbb{Z}[x]/(x^{N} – 1)$ and $\mathbb{Z}[x]/(x^{N} + 1)$.
Now mapping a polynomial $f(x)$ from the bigger ring $(x^{2N} – 1)$ to the smaller ring $(x^{N}+1)$ involves taking a remainder of $f(x)$ when dividing by $x^{N}+1$ (“setting” $x^N = -1$ and reducing). There are many possible preimage mappings, depending on what your goal is. In this case, we actually intentionally choose a non preimage mapping, because in general to compute a preimage requires solving a system of congruences in the larger polynomial ring. So instead we choose $f(x) \mapsto f^*(x) = f(x) – x^Nf(x) = -f(x)(x^N – 1)$, which maps back down to $2f(x)$ in $\mathbb{Z}[x]/(x^{N} + 1)$. This preimage mapping has a particularly nice structure, in that you build it by repeating the polynomial’s coefficients twice and flipping the sign of the second half. It’s easy to see that the product $f^*(x) g^*(x)$ maps down to $4f(x)g(x)$.
So if we properly account for these extra constant factors floating around, our strategy to perform negacyclic polynomial multiplication is to map $f$ and $g$ up to the larger ring as described, compute their cyclic product (modulo $x^{2N} – 1$) using the FFT, and then the result should be a degree $2N-1$ polynomial which can be reduced with one more modular reduction step to the right degree $N-1$ negacyclic product, i.e., setting $x^N = -1$, which materializes as taking the second half of the coefficients, flipping their signs, and adding them to the corresponding coefficients in the first half.
The code for this is:
 def negacyclic_polymul_preimage_and_map_back(p1, p2):
 p1_preprocessed = numpy.concatenate([p1, -p1])
 p2_preprocessed = numpy.concatenate([p2, -p2])
 product = fft(p1_preprocessed) * fft(p2_preprocessed)
 inverted = ifft(product)
 rounded = numpy.round(numpy.real(inverted)).astype(p1.dtype)
 return (rounded[: p1.shape[0]] - rounded[p1.shape[0] :]) // 4
 
However, this chosen mapping hides another clever trick. The product of the two preimages has enough structure that we can “read” the result off without doing the full “set $x^N = -1$” reduction step. Mapping $f$ and $g$ up to $f^*, g^*$ and taking their product modulo $(x^{2N} – 1)$ gives
\[ \begin{aligned} f^*g^* &amp;= -f(x^N-1) \cdot -g(x^N – 1) \\ &amp;= fg (x^N-1)^2 \\ &amp;= fg(x^{2N} – 2x^N + 1) \\ &amp;= fg(2 – 2x^N) \\ &amp;= 2(fg – x^Nfg) \end{aligned} \]
This has the same syntactical format as the original mapping $f \mapsto f – x^Nf$, with an extra factor of 2, and so its coefficients also have the form “repeat the coefficients and flip the sign of the second half” (times two). We can then do the “inverse mapping” by reading only the first half of the coefficients and dividing by 2.
 def negacyclic_polymul_use_special_preimage(p1, p2):
 p1_preprocessed = numpy.concatenate([p1, -p1])
 p2_preprocessed = numpy.concatenate([p2, -p2])
 product = fft(p1_preprocessed) * fft(p2_preprocessed)
 inverted = ifft(product)
 rounded = numpy.round(0.5 * numpy.real(inverted)).astype(p1.dtype)
 return rounded[: p1.shape[0]]
 
Our chosen mapping $f \mapsto f-x^Nf$ is not particularly special, except that it uses a small number of pre and post-processing operations. For example, if you instead used the mapping $f \mapsto 2f + x^Nf$ (which would map back to $f$ exactly), then the FFT product would result in $5fg + 4x^Nfg$ in the larger ring. You can still read off the coefficients as before, but you’d have to divide by 5 instead of 2 (which, the superstitious would say, is harder). It seems that “double and negate” followed by “halve and take first half” is the least amount of pre/post processing possible.
Negacyclic polynomials with a “twist”
The previous section identified a nice mapping (or embedding) of the input polynomials into a larger ring. But studying that shows some symmetric structure in the FFT output. I.e., the coefficients of $f$ and $g$ are repeated twice, with some scaling factors. It also involves taking an FFT of two $2N$-dimensional vectors when we start from two $N$-dimensional vectors.
This sort of situation should make you think that we can do this more efficiently, either by using a smaller size FFT or by packing some data into the complex part of the input, and indeed we can do both. 
[Aside: it’s well known that if all the entries of an FFT input are real, then the result also has symmetry that can be exploted for efficiency by reframing the problem as a size-N/2 FFT in some cases, and just removing half the FFT algorithm’s steps in other cases, see Wikipedia for more]
This technique was explained in Fast multiplication and its applications (pdf link) by Daniel Bernstein, a prominent cryptographer who specializes in cryptography performance, and whose work appears in widely-used standards like TLS, OpenSSH, and he designed a commonly used elliptic curve for cryptography.
[Aside: Bernstein cites this technique as using something called the “Tangent FFT (pdf link).” This is a drop-in FFT replacement he invented that is faster than previous best (split-radix FFT), and Bernstein uses it mainly to give a precise expression for the number of operations required to do the multiplication end to end. We will continue to use the numpy FFT implementation, since in this article I’m just focusing on how to express negacyclic multiplication in terms of the FFT. Also worth noting both the Tangent FFT and “Fast multiplication” papers frame their techniques—including FFT algorithm implementations!—in terms of polynomial ring factorizations and mappings. Be still, my beating cardioid.]
In terms of polynomial mappings, we start from the ring $\mathbb{R}[x] / (x^N + 1)$, where $N$ is a power of 2. We then pick a reversible mapping from $\mathbb{R}[x]/(x^N + 1) \to \mathbb{C}[x]/(x^{N/2} – 1)$ (note the field change from real to complex), apply the FFT to the image of the mapping, and reverse appropriately it at the end.
One such mapping takes two steps, first mapping $\mathbb{R}[x]/(x^N + 1) \to \mathbb{C}[x]/(x^{N/2} – i)$ and then from $\mathbb{C}[x]/(x^{N/2} – i) \to \mathbb{C}[x]/(x^{N/2} – 1)$. The first mapping is as easy as the last section, because $(x^N + 1) = (x^{N/2} + i) (x^{N/2} – i)$, and so we can just set $x^{N/2} = i$ and reduce the polynomial. This as the effect of making the second half of the polynomial’s coefficients become the complex part of the first half of the coefficients.
The second mapping is more nuanced, because we’re not just reducing via factorization. And we can’t just map $i \mapsto 1$ generically, because that would reduce complex numbers down to real values. Instead, we observe that (momentarily using an arbitrary degree $k$ instead of $N/2$), for any polynomial $f \in \mathbb{C}[x]$, the remainder of $f \mod x^k-i$ uniquely determines the remainder of $f \mod x^k – 1$ via the change of variables $x \mapsto \omega_{4k} x$, where $\omega_{4k}$ is a $4k$-th primitive root of unity $\omega_{4k} = e^{\frac{2 \pi i}{4k}}$. Spelling this out in more detail: if $f(x) \in \mathbb{C}[x]$ has remainder $f(x) = g(x) + h(x)(x^k – i)$ for some polynomial $h(x)$, then
\[ \begin{aligned} f(\omega_{4k}x) &amp;= g(\omega_{4k}x) + h(\omega_{4k}x)((\omega_{4k}x)^{k} – i) \\ &amp;= g(\omega_{4k}x) + h(\omega_{4k}x)(e^{\frac{\pi i}{2}} x^k – i) \\ &amp;= g(\omega_{4k}x) + i h(\omega_{4k}x)(x^k – 1) \\ &amp;= g(\omega_{4k}x) \mod (x^k – 1) \end{aligned} \] 
Translating this back to $k=N/2$, the mapping from $\mathbb{C}[x]/(x^{N/2} – i) \to \mathbb{C}[x]/(x^{N/2} – 1)$ is $f(x) \mapsto f(\omega_{2N}x)$. And if $f = f_0 + f_1x + \dots + f_{N/2 – 1}x^{N/2 – 1}$, then the mapping involves multiplying each coefficient $f_k$ by $\omega_{2N}^k$.
When you view polynomials as if they were a simple vector of their coefficients, then this operation $f(x) \mapsto f(\omega_{k}x)$ looks like $(a_0, a_1, \dots, a_n) \mapsto (a_0, \omega_{k} a_1, \dots, \omega_k^n a_n)$. Bernstein calls the operation a twist of $\mathbb{C}^n$, which I mused about in this Mathstodon thread.
What’s most important here is that each of these transformations are invertible. The first because the top half coefficients end up in the complex parts of the polynomial, and the second because the mapping $f(x) \mapsto f(\omega_{2N}^{-1}x)$ is an inverse. Together, this makes the preprocessing and postprocessing exact inverses of each other. The code is then
 def negacyclic_polymul_complex_twist(p1, p2):
 n = p2.shape[0]
 primitive_root = primitive_nth_root(2 * n)
 root_powers = primitive_root ** numpy.arange(n // 2)
 p1_preprocessed = (p1[: n // 2] + 1j * p1[n // 2 :]) * root_powers
 p2_preprocessed = (p2[: n // 2] + 1j * p2[n // 2 :]) * root_powers
 p1_ft = fft(p1_preprocessed)
 p2_ft = fft(p2_preprocessed)
 prod = p1_ft * p2_ft
 ifft_prod = ifft(prod)
 ifft_rotated = ifft_prod * primitive_root ** numpy.arange(0, -n // 2, -1)
 return numpy.round(
 numpy.concatenate([numpy.real(ifft_rotated), numpy.imag(ifft_rotated)])
 ).astype(p1.dtype)
 
And so, at the cost of a bit more pre- and postprocessing, we can negacyclically multiply two degree $N-1$ polynomials using an FFT of length $N/2$. In theory, no information is wasted and this is optimal.
And finally, a simple matrix multiplication
The last technique I wanted to share is not based on the FFT, but it’s another method for doing negacyclic polynomial multiplication that has come in handy in situations where I am unable to use FFTs. I call it the Toeplitz method, because one of the polynomials is converted to a Toeplitz matrix. Sometimes I hear it referred to as a  circulant matrix  technique, but due to the negacyclic sign flip, I don’t think it’s a fully accurate term.
The idea is to put the coefficients of one polynomial $f(x) = f_0 + f_1x + \dots + f_{N-1}x^{N-1}$ into a matrix as follows:
\[ \begin{pmatrix} f_0 &amp; -f_{N-1} &amp; \dots &amp; -f_1 \\ f_1 &amp; f_0 &amp; \dots &amp; -f_2 \\ \vdots &amp; \vdots &amp; \ddots &amp; \vdots \\ f_{N-1} &amp; f_{N-2} &amp; \dots &amp; f_0 \end{pmatrix} \]
The polynomial coefficients are written down in the first column unchanged, then in each subsequent column, the coefficients are cyclically shifted down one, and the term that wraps around the top has its sign flipped. When the second polynomial is treated as a vector of its coefficients, say, $g(x) = g_0 + g_1x + \dots + g_{N-1}x^{N-1}$, then the matrix-vector product computes their negacyclic product (as a vector of coefficients):
\[ \begin{pmatrix} f_0 &amp; -f_{N-1} &amp; \dots &amp; -f_1 \\ f_1 &amp; f_0 &amp; \dots &amp; -f_2 \\ \vdots &amp; \vdots &amp; \ddots &amp; \vdots \\ f_{N-1} &amp; f_{N-2} &amp; \dots &amp; f_0 \end{pmatrix} \begin{pmatrix} g_0 \\ g_1 \\ \vdots \\ g_{N-1} \end{pmatrix} \]
This works because each row $j$ corresponds to one output term $x^j$, and the cyclic shift for that row accounts for the degree-wrapping, with the sign flip accounting for the negacyclic part. (If there were no sign attached, this method could be used to compute a cyclic polynomial product).
The Python code for this is
 def cylic_matrix(c: numpy.array) -&gt; numpy.ndarray:
 """Generates a cyclic matrix with each row of the input shifted.
 For input: [1, 2, 3], generates the following matrix:
 [[1 2 3]
 [2 3 1]
 [3 1 2]]
 """
 c = numpy.asarray(c).ravel()
 a, b = numpy.ogrid[0 : len(c), 0 : -len(c) : -1]
 indx = a + b
 return c[indx]
def negacyclic_polymul_toeplitz(p1, p2):
 n = len(p1)
 # Generates a sign matrix with 1s below the diagonal and -1 above.
 up_tri = numpy.tril(numpy.ones((n, n), dtype=int), 0)
 low_tri = numpy.triu(numpy.ones((n, n), dtype=int), 1) * -1
 sign_matrix = up_tri + low_tri
 cyclic_matrix = cylic_matrix(p1)
 toeplitz_p1 = sign_matrix * cyclic_matrix
 return numpy.matmul(toeplitz_p1, p2)
 
Obviously on most hardware this would be less efficient than an FFT-based method (and there is some relationship between circulant matrices and Fourier Transforms, see Wikipedia). But in some cases—when the polynomials are small, or one of the two polynomials is static, or a particular hardware choice doesn’t handle FFTs with high-precision floats very well, or you want to take advantage of natural parallelism in the matrix-vector product—this method can be useful. It’s also simpler to reason about.
Until next time!
Math ∩ Programming
https://jeremykun.com/
http://users.csc.calpoly.edu/~jworkman/CSS/Jeremy/
Jeremy Kun :: What a guy!
None
None
<div><div>
<p></p><h2>Hi!</h2>
<p>My name is Jeremy Kun, and I'm a pretty cool guy. I've got all sorts of neat talents. Check me out on <a href="http://www.facebook.com/profile.php?id=681005077">Facebook</a>, or <a href="http://www.linkedin.com/in/jeremykun">LinkedIn</a>.</p>
<h2>About Me</h2>
<p>In my spare time I like to play and write music. I play the piano, djembe, guitar, didgeridoo, and I would like to learn the violin. My favorite musician is John Lennon, and I like Death Cab For Cutie as well. I also enjoy reading, and I like <a href="http://www.youtube.com/watch?v=bzVyqiskpMk">parodies of literature</a>. My apartment smells of rich mahogany, and I enjoy long walks on the beach. This summer I have an internship with Amazon, which I'm very excited about. I think that <a href="http://xkcd.com/verizon/">math jokes</a> are hilarious. I have a black belt in Tae Kwon Do, and I once killed a tiger with my bare hands. Needless to say, I had all the tiger-jerky I could ever want. I speak German and would like to live in Berlin for a while. My favorite movie is, in fact, <a href="http://www.youtube.com/watch?v=qM-gZintWDc">the best movie ever made</a>. When I was seven, I was hit by a bus. You may think that's a tragedy, but you should see the bus. Most importantly, I cook a damn good Pad Thai.</p>
<p>So feel free to peruse my site and learn more about me. If you'd like to contact me, then I apologize, because I am currently and indefinitely unavailable.</p>
</div></div>||||I|||| Jeremy Kun

 What a guy!

 * Home
 * School
 * Personal Projects


 Hi!

 My name is Jeremy Kun, and I'm a pretty cool guy. I've got all sorts of neat talents. Check me out on Facebook, or LinkedIn.

 About Me

 In my spare time I like to play and write music. I play the piano, djembe, guitar, didgeridoo, and I would like to learn the violin. My favorite musician is John Lennon, and I like Death Cab For Cutie as well. I also enjoy reading, and I like parodies of literature. My apartment smells of rich mahogany, and I enjoy long walks on the beach. This summer I have an internship with Amazon, which I'm very excited about. I think that math jokes are hilarious. I have a black belt in Tae Kwon Do, and I once killed a tiger with my bare hands. Needless to say, I had all the tiger-jerky I could ever want. I speak German and would like to live in Berlin for a while. My favorite movie is, in fact, the best movie ever made. When I was seven, I was hit by a bus. You may think that's a tragedy, but you should see the bus. Most importantly, I cook a damn good Pad Thai.

 So feel free to peruse my site and learn more about me. If you'd like to contact me, then I apologize, because I am currently and indefinitely unavailable.

Hi!
My name is Jeremy Kun, and I'm a pretty cool guy. I've got all sorts of neat talents. Check me out on Facebook, or LinkedIn.
About Me
In my spare time I like to play and write music. I play the piano, djembe, guitar, didgeridoo, and I would like to learn the violin. My favorite musician is John Lennon, and I like Death Cab For Cutie as well. I also enjoy reading, and I like parodies of literature. My apartment smells of rich mahogany, and I enjoy long walks on the beach. This summer I have an internship with Amazon, which I'm very excited about. I think that math jokes are hilarious. I have a black belt in Tae Kwon Do, and I once killed a tiger with my bare hands. Needless to say, I had all the tiger-jerky I could ever want. I speak German and would like to live in Berlin for a while. My favorite movie is, in fact, the best movie ever made. When I was seven, I was hit by a bus. You may think that's a tragedy, but you should see the bus. Most importantly, I cook a damn good Pad Thai.
So feel free to peruse my site and learn more about me. If you'd like to contact me, then I apologize, because I am currently and indefinitely unavailable.
Jeremy Kun :: What a guy!
http://users.csc.calpoly.edu/~jworkman/CSS/Jeremy/
https://www.idcrawl.com/jeremy-kun
Jeremy Kun's Instagram, Twitter & Facebook on IDCrawl
2011-06-24
Jeremy J Kun
<div> <div> <nav> <ul> <li><a href="https://www.idcrawl.com/">People Search</a></li> <li><a href="https://www.idcrawl.com/sitemap/j">J</a></li> <li><a href="https://www.idcrawl.com/abc/j1876">Jeremy...Landin</a></li> <li>Jeremy Kun</li> </ul> </nav> <div> <div> <p> <a href="#gl-accordion-spokeo-details"> <h2><i></i>Public Records</h2> </a> </p> <div> <p>Sponsored by Spokeo<i></i></p> </div> </div> <div> <p> <a href="#gl-accordion-emails-details"> <h2><i></i>Email Addresses</h2> </a> </p> <div> <p>Sponsored by Spokeo<i></i></p> </div> </div> <div> <p> <a href="#gl-accordion-tiktok-details"> <h2><i></i>TikTok</h2> </a> </p> <div> <div> <p> </p> </div> <div> <p> </p> </div> <div> <div> <p> </p> </div> <div> <h3> <a href="https://www.tiktok.com/@jeremykun?lang=en">jeremykun - @jeremykun</a> </h3> <p> Car Enthusiastic, Coffee Enthusiastic <br/>handsets is recommended for my video 🎧<br/>826 followers </p> </div> </div> <div> <p> </p> </div> <div> <p> </p> </div> <div> <p> </p> </div> <div> <p> </p> </div> <div> <p> </p> </div> <div> <p> </p> </div> </div> </div> <div> <p> <a href="#gl-accordion-youtube-details"> <h2><i></i>Youtube</h2> </a> </p> <div> <div> <p> </p> </div> <div> <p> </p> </div> <div> <p> </p> </div> <div> <p> </p> </div> <div> <p> </p> </div> <div> <p> </p> </div> <div> <p> </p> </div> <div> <p> </p> </div> <div> <p> </p> </div> <div> <p> </p> </div> <div> <p> </p> </div> <div> <div> <p> </p> </div> <div> <h3> <a href="https://www.youtube.com/@KukanDrama">KUKAN Drama Channel - @KukanDrama <i></i></a> </h3> <div><p> Welcome to subscribe to our channel for the latest Chinese TV drama, thanks for your support~</p><p>❤️New drama continues to be ...<br/>1.75M subscribers </p></div> </div> </div> <div> <p> </p> </div> <div> <p> </p> </div> <div> <p> </p> </div> <div> <p> </p> </div> <div> <p> </p> </div> </div> </div> <div> <p> <a href="#gl-accordion-linkedin-details"> <h2><i></i>LinkedIn</h2> </a> </p> <div> <div> <div> <p> <i></i> </p> </div> <div> <h3> <a href="https://www.linkedin.com/in/jeremy-kunzhou">Kun Zhou</a> </h3> <p> Seeking Next Challenge at blockprime </p> </div> </div> <div> <p> <i></i> </p> </div> <div> <div> <p> <i></i> </p> </div> <div> <h3> <a href="https://www.linkedin.com/in/twwbond">Tim Bond</a> </h3> <p> Program technical advisor (SETA) at DARPA I2O at ManTech </p> </div> </div> <div> <p> <i></i> </p> </div> <div> <div> <p> <i></i> </p> </div> <div> <h3> <a href="https://www.linkedin.com/in/kejinud">Ke Jin</a> </h3> <p> Programmer, PhD in Applied Math </p> </div> </div> <div> <p> <i></i> </p> </div> <div> <div> <p> <i></i> </p> </div> <div> <h3> <a href="https://www.linkedin.com/in/jeremy-portier">Jeremy P.</a> </h3> <p> Testconsultant Landelijke Meldkamer Samenwerking </p> </div> </div> <div> <p> <i></i> </p> </div> <div> <p> <i></i> </p> </div> <div> <p> <i></i> </p> </div> <div> <p> <i></i> </p> </div> <div> <p> <i></i> </p> </div> <div> <p> <i></i> </p> </div> <div> <p> <i></i> </p> </div> <div> <p> <i></i> </p> </div> </div> </div> <div> <p> <a href="#gl-accordion-reverse_whois-details"> <h2><i></i>Websites</h2> </a> </p> <div> <p>Websites owned by Jeremy Kun</p> <div> <h3> jeremykun.com </h3> <p>Registered on December 19, 2012</p> </div> </div> </div> <div> <p> <a href="#gl-accordion-archives-details"> <h2><i></i>Archives</h2> </a> </p> <div> <div> <p> </p> </div> <div> <p> </p> </div> <div> <div> <p> </p> </div> <div> <h3> <a href="https://archive.org/details/doingmathwithpython_202109/doingmathwithpython?q=%22jeremy+kun%22">doingmathwithpython</a> </h3> <p>Community Texts</p> <p> ... Seph Kramer and Tyler Ortman Technical Reviewer: Jeremy Kun Copyeditor: Julianne Jigour Compositor: Riley... </p> </div> </div> <div> <p> </p> </div> <div> <div> <p> </p> </div> <div> <h3> <a href="https://archive.org/details/impractical-python-project/Impractical%20Python%20Project?q=%22jeremy+kun%22">Impractical Python Project</a> </h3> <p>Folkscanomy Computer: Inbox and Miscellaneous</p> <p> ... Developmental Editor: Zach Lebowski Technical Reviewers: Jeremy Kun, Michael Contraveos, and Michele Pratusevich... </p> </div> </div> </div> </div> <div> <p> <a href="#gl-accordion-web-details"> <h2><i></i>Web results</h2> </a> </p> <div> <div> <h3> <a href="https://jeremykun.com/about/">About the Author – Math ∩ Programming</a> </h3> <p> I'm Jeremy Kun. I'm currently an engineer at Google and I live in Portland, Oregon. Books In 2018 I published A Programmer's Introduction to Mathematics. Currently I'm working on Practical Math for Programmers: A Tour of Math in Production Software. Schooling I earned a PhD in … See more </p> </div> <div> <h3> <a href="https://jeremykun.com/">Math ∩ Programming</a> </h3> <p> Posted on July 10, 2023 by Jeremy Kun Before I discovered math, I was a first year undergrad computer science student taking Electrical Engineering 101. The first topic I learned was what bits and boolean gates are, and the … </p> </div> <div> <h3> <a href="https://theconversation.com/profiles/jeremy-kun-183460">Jeremy Kun – The Conversation</a> </h3> <p> Jeremy Kun 1 Article 2 Comments PhD Student in Mathematics, University of Illinois Chicago Profile Articles Activity I am a theoretical computer scientist with broad interests, including... </p> </div> <div> <h3> <a href="https://scholar.google.com/citations?user=2tN47wQAAAAJ">‪Jeremy Kun‬ - ‪Google Scholar‬</a> </h3> <p> Jeremy Kun. Algorithmic Game Theory: 6th International Symposium, SAGT 2013, Aachen …. Distributed Computing: 29th International Symposium, DISC 2015, Tokyo, Japan …. Graph … </p> </div> <div> <h3> <a href="https://jeremykun.com/primers/">Primers – Math ∩ Programming</a> </h3> <p> Primers. As a fair warning to the reader, these primers are a bit more terse than what you’d find in your average textbook. I only introduce the bare minimum required to understand … </p> </div> <div> <h3> <a href="https://www.socialsciencespace.com/author/jeremykun/">Jeremy Kun, Author at Social Science Space</a> </h3> <p> Jeremy Kun. Jeremy Kun is a theoretical computer scientist at the University of Illinois at Chicago with broad interests, including complexity theory, graph theory and network … </p> </div> <div> <h3> <a href="https://jeremykun.com/main-content/">Main Content – Math ∩ Programming</a> </h3> <p> When Greedy is Good Enough: Submodularity and the 1 – 1/e Approximation. When Greedy Algorithms are Perfect: the Matroid. Linear Programming and Healthy Diets Part 1. Linear … </p> </div> <div> <h3> <a href="https://jeremykun.com/category/books/">Books – Math ∩ Programming</a> </h3> <p> Posted on May 14, 2022 by Jeremy Kun. This is a draft of a chapter from my in-progress book, Practical Math for Programmers: A Tour of Mathematics in Production … </p> </div> <div> <h3> <a href="https://www.amazon.ca/Books-Jeremy-Kun/s?rh=n%3A916520%2Cp_27%3AJeremy+Kun">Amazon.ca: Jeremy Kun: Books</a> </h3> <p> 4.7 (40) Paperback $5028 FREE delivery Fri, Mar 31 A Programmer's Introduction to Mathematics by Dr. Jeremy Kun | Nov 27 2018 4.4 (94) Paperback Need help? Visit the … </p> </div> </div> </div> </div> </div> <a href="#"><i></i></a> <div> <p>Continue</p> <p> </p></div> </div>||||I|||| * People Search
 * Username Search
 * Reverse Phone
 * Reverse Email
 Search

 New information found for Jeremy Kun. Click here to refresh the page.

 * People Search
 * J
 * Jeremy...Landin
 * Jeremy Kun

 Jeremy Kun

 Filter

 Found 4 people in North Carolina, Oregon, Montana and other states

 * +97
 * +96
 * +95
 * 
 * +93
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 
 * 

 Instagram

 Jeremy-Kun - @jeremy_kun_

 Jeremy Kun - @jeremykun168

 Jeremy Kun

 Sponsored by PeopleLooker Paid Service

 Unlock Results

 Search

 JEREMY - @jeremy__kun

 Ɉȅɍḝṃẙ Ǩʉȵ - @jeremy_kun_502

 Jeremy Kun - @jeremykun_

 Jeremy Kun - @onitsuka_2020

 Jeremy Kun - @jeremy_kun2003

 Jeremy Kun - @jeremy_tbe_

 Jeremy-kun - @jerrylooking

 Jeremy Kun - @jeremy_kuns

 J E R E M Y - @jeremykun._

 manito_de_grey_333 - @jeremy_kun_12

 Jeremy.kun_official - @jeremy.kun_official

 Jeremy-Kun - @jeremykun10

 Jeremy - @j.jeremy_kun

 Kenner Cáez - @jeremy_kun

 Ta Kun - @jeremy_kun_2016

 Jeremy Kun - @eahitsjeremy

 Jeremy Kun - @daniel_cerezo666

 Jeremy kun uwu - @jeremy_kun_uwu

 Jeremy_Kun12 - @jeremy_kun12

 A'tr Jeremmy Silva - @jeremykun_07

 Daniel Jeremy-kun - @danielljeremy

 Jeremy Dokuro-kun - @jeremydokurokun

 Jeremy Kunz - @kunz_jeremy

 Jeremy Kūn - @kazuki_750_

 @jeremy.kunzzz

 Jérémy Kun - @kun_jeremy

 jeremyk uniformes - @jeremykuniformes

 Jeremy Kunkle - @jeremy_kunkle19

 Jeremy Kühn - @travelgram308

 Jeremy - @jeremy_kungu_

 Jeremy - @jeremykundtz.photo

 Jeremy Kuntze - @jeremy_kuntze

 Jeremy Kunz - @jeremy179

 Jeremy Kunzman - @jeremy_kunzman

 Jeremy Küng - @bouclette_temporelle

 JeremyKundiri - @jeremykundiri7

 Jeremy Kunchandy - @jeremykunchandy

 Jeremy Biewer - @kunst.jeremy

 Jeremy Kundid - @jtkundid

 Jeremy Kungu - @jeremykungu

 Jeremy Kunen - @jeremykunen

 Jeremy Kunkle - @jeremykunkle

 Jeremy Kunaraz - @jeremykunaraz

 Jeremy Kuntz - @jeremy.kuntz1

 Jeremy - @jeremy.kungu

 Jeremy kühn - @jeremy.opnv

 Jeremy Kunigiskis - @jeremyfit_official

 Jeremy Kung - @jeremykung

 Jeremy Kunz - @jeremy.kunz

 Jeremy Kunert - @jxremy_1604

 nguyễn ngọc trà my (阮 玉 茶 媚） - @jeremykuns

 Show all results...

 Twitter

 Jeremy Kun (j2kun@mathstodon.xyz) - @jeremyjkun

 Portland, OR

 jeremykun.com

 Author @MathProgramming, book: pimbook.org. Homomorphic encryption @Google. PhD from UI Chicago. Newsletter: buttondown.email/j2kun

 Jeremy kun - @boywish2015kun

 Taiwan

 喜愛運動、聊天、風景、電影、音樂、美食、網路

 jeremy kun - @jeremykun123

 hi please tip me on brave browser anything helps

 Jeremy Kún - @JeremyKun99

 Viet Nam

 facebook.com

 nothing to say...=)))

 Jeremy kun - @Jeremykun4

 Me gusta aser imagenes no soy muy bueno pero me divierte

 jeremy kún - @JeremyKun

 Eldaiki1 - @JeremyKun3

 Jeremy Kun - @JeremyKun1

 Jeremy Kun - @JeremyKun29

 Xdd..

 Uchi-san - @jeremy_kun

 Jeremy - @Jeremy_kun2003

 Jeremy Kun Bosman - @bbpiie

 Toulouse, Midi-Pyrénées

 ex cod4 pro player and battalion

 Jeremy Kun - @JeremyKun177799

 Jeremy Albero - @Jeremy__Kun

 Jeremy-Kun - @JeremyKun17

 Nose

 Jeremy kun - @lamaruangi

 Kota Manado, Sulawesi Utara

 Penyendiri😁
 suka anime😍
 suka musik☺️
 suka blackpink😎

 jeremy kun mendez - @MendezKun

 Math ∩ Programming - @MathProgramming

 jeremykun.com

 A blog by Jeremy Kun @jeremyjkun

 Jeremy_kun_oficial - @Jeremykunofici1

 un chico de once que suele comer maruchan

 Jeremy~Kun - @Jeremy21780857

 Show all results...

 Background Check

 Public Records

 Sponsored by Spokeo Paid Service

 Jeremy J Kun, age 33

 K*****@ymail.com — (925) 255-****

 ***** Macarthur Blvd, Apt 5, Oakland, CA

 View full report

 Email Addresses

 Sponsored by Spokeo Paid Service

 jerem****@gmail.com

 Search secret profiles for jerem****@gmail.com

 Search

 jerem****@yahoo.com

 Search secret profiles for jerem****@yahoo.com

 Search

 Public Records

 Jeremy Kun

 Sponsored by PeopleLooker Paid Service

 Search for contact info, address history, relatives, jobs, education & more

 Search public records

 Relatives

 Facebook

 Jeremy Kun

 Jeremy Kun

 Jeremy Kun

 Sponsored by PeopleLooker Paid Service

 Unlock Results

 Search

 Jeremy Kun

 Jeremy Kun

 Jeremy Kun

 Jeremy Kun

 Jeremy Kun

 Jeremy Kun

 Jeremy Kun

 Jeremy Kun

 Jeremy Kūn

 Jrmy Kun

 Ɉȅɍḝṃẙ Ǩʉȵ

 Works at Marketing

 Jeremiah Kun.

 Jeramy Kun

 Show all results...

 TikTok

 Jeremy Kun - @jeremyjkun

 https://jeremykun.com
 2,799 followers

 Jeremy Kun - @jeremykun502

 Se la mejor versión de ti mismo, solo entrarán las personas indicadas
 66 followers

 jeremykun - @jeremykun

 Car Enthusiastic, Coffee Enthusiastic
 handsets is recommended for my video 🎧
 826 followers

 jeremykun_3 - @jeremykun_3

 1 follower

 Jeremykun - @jeremy.kun

 S💓
 77 followers

 Hîrø Kun - @jeremy_kun75

 hola
 68 followers

 jeremykun_ - @jeremykun_

 4 followers

 Jeremy Kun - @jeramykun

 5 followers

 Jeremy Kuhn - @jeremykuhn1200

 Join the beginning of our adventure ❤️

 Snapchat: jeremy_klol
 1,280 followers

 Show all results...

 Youtube

 Jeremy Kun - @mathprogramming

 Math Intersect Programming.
 183 subscribers

 Jeremy Kun - @jeremykun-jm6un

 Jeremy Kun - @jeremykun4926

 11 subscribers

 Jeremy Kun - @jeremykun934

 4 subscribers

 Jeremy -kun - @jeremy-kun1827

 5 subscribers

 Jeremy Kun - @jeremykun4085

 13 subscribers

 Jeremy Kun - @j2kun

 17 subscribers

 Jeremy-Kun - @jeremy-kun6756

 Jeremy prox.
 22 subscribers

 Jeremy Andrew Kun Hendrawan 1911077 - @JeremyAndrewKunHendrawan

 4 subscribers

 Natsumi-kun - @Kunushi28

 ChideCaptaino❤️ *not a ship*
 41 subscribers

 Jeremy10 - @Jeremy-mp1lm

 Minecraft!
 892 subscribers

 Jeremy Yap - @jeremyyap2309

 1 subscriber

 KUKAN Drama Channel - @KukanDrama

 Welcome to subscribe to our channel for the latest Chinese TV drama, thanks for your support~

 ❤️New drama continues to be ...
 1.75M subscribers

 Jeremy Plays - @JeremyPlaysYT

 Go follow me into instagram @jeremy.antton
 94 subscribers

 Frisk The Human - @dreamthespeedrunner9366

 5 subscribers

 Stanford Blockchain Club - @StanfordBlockchainClub

 2.24K subscribers

 Jeremy Kiehlmann - @JeremyKiehlmann

 29 subscribers

 Terry kun Jeremy - @terrykunjeremy5269

 YUZIN - Kun - @yuzin-kun3760

 Aye guys its me Jeremy please subscribe to my channel.

 jem-k un preso en el mundo real - @jemkunpresoenelmundoreal

 Un preso en el mundo real, hago videos desde prisión, para mostrarles un mundo que muchos no conocen, mi diario de vivir en ...
 1.56M subscribers

 Show all results...

 Usernames

 jeremykun
 jeremy__kun
 jeremykun_
 jeremy_kun2003
 jeremy_kun
 jeremykuns
 jeremyjkun
 mathprogramming
 jeremy_kun_
 jeremykun168
 jeremy_kun_502
 onitsuka_2020
 jeremy_tbe_
 jerrylooking
 jeremy_kuns
 jeremykun._
 jeremy_kun_12
 jeremy.kun_official
 jeremykun10
 j.jeremy_kun
 jeremy_kun_2016
 eahitsjeremy
 daniel_cerezo666
 jeremy_kun_uwu
 jeremy_kun12
 jeremykun_07
 danielljeremy
 jeremydokurokun
 kunz_jeremy
 kazuki_750_
 jeremy.kunzzz
 kun_jeremy
 jeremykuniformes
 jeremy_kunkle19
 travelgram308
 jeremy_kungu_
 jeremykundtz.photo
 jeremy_kuntze
 jeremy179
 jeremy_kunzman
 bouclette_temporelle
 jeremykundiri7
 jeremykunchandy
 kunst.jeremy
 jtkundid
 jeremykungu
 jeremykunen
 jeremykunkle
 jeremykunaraz
 jeremy.kuntz1
 jeremy.kungu
 jeremy.opnv
 jeremyfit_official
 jeremykung
 jeremy.kunz
 jxremy_1604
 boywish2015kun
 jeremykun123
 jeremykun99
 jeremykun4
 jeremykun3
 jeremykun1
 jeremykun29
 bbpiie
 jeremykun177799
 jeremykun17
 lamaruangi
 mendezkun
 jeremykunofici1
 jeremy21780857
 frankin.asnate
 jeremy.el.cangri.xd
 jeremy.kun.10
 jeremy.kun.96
 jeremy.kun.33
 jeremy.kun.14
 jeremy.kun.58
 jeremy.kun.777
 jeremy.laqui
 jeremykun502
 jeremykun_3
 jeremy.kun
 jeremy_kun75
 jeramykun
 jeremykuhn1200
 jeremykun4926
 jeremykun934
 jeremykun4085
 j2kun
 jeremyandrewkunhendrawan
 kunushi28
 jeremyyap2309
 kukandrama
 jeremyplaysyt
 dreamthespeedrunner9366
 stanfordblockchainclub
 jeremykiehlmann
 terrykunjeremy5269
 jemkunpresoenelmundoreal
 meki_kun
 jkun
 jeremyturismo
 jeremyvgt49
 jeremykunb
 jeremykunlikesmemes
 jerzamca2007
 jeremyd1005
 alexalvarado23450323
 malkahjere
 jeremykun04
 jedebesa09
 jeremykun9029
 jeremykun004
 jeremykun85
 danieljeremy28
 yamato_1005
 jeremykun24
 brandondeblv
 galax403yt
 carranzamedinajeremyfederico
 jeremyampaimorales
 jrmykn
 Show all results...

 LinkedIn

 Jeremy Kun

 Kun Zhou

 Seeking Next Challenge at blockprime

 Vinod Vaikuntanathan

 Massachusetts Institute of Technology

 Tim Bond

 Program technical advisor (SETA) at DARPA I2O at ManTech

 Mathematics Faculty

 Mathematics Faculty at Clackamas Community College

 Ke Jin

 Programmer, PhD in Applied Math

 Uzumaki Jeremy Kun Uchiha

 Perú

 Jeremy P.

 Testconsultant Landelijke Meldkamer Samenwerking

 Boni Aditya

 Julian Moon

 Los Angeles

 Calvin Rueb

 Student at Illinois State University

 Sergey Iakovlev

 Piyush Dadlani

 AI Engineer - Project Specialist

 Adam Lelkes

 Senior Software Engineer - Google

 John Armstrong

 Senior Software Engineer - Stealth

 Shruthi Gorantala

 Silvano Bonacina

 Software Engineer at Google

 Ro Cammarota

 Marco Bonvini

 Senior Software Engineer - Google

 Miguel Guevara

 Kevin Lui

 Audrey Addison

 Zahra Bizhani

 Back End Developer - Radintech

 Show all results...

 Address History

 Jeremy Kun

 Sponsored by PeopleLooker Paid Service

 Search for Jeremy Kun's address history

 Search address history

 Obituary

 No Results

 Websites

 Websites owned by Jeremy Kun

 jeremykun.com

 Registered on December 19, 2012

 News

 Big data algorithms can discriminate, and it's not clear what to do about it

 The Conversation - Thu, 13 Aug 2015

 New algorithm cracks graph problem László Babai

 Science News Magazine - Wed, 11 Nov 2015

 Understanding Two's Complement with Group Theory

 Math ∩ Programming - Mon, 10 Jul 2023

 We're Knot Friends – Math ∩ Programming

 Math ∩ Programming - Sat, 01 Apr 2023

 Jeremy Kun

 Uses This - Tue, 19 Feb 2019

 Jeremy Kun

 Google - Fri, 23 Oct 2015

 General – Math ∩ Programming

 Math ∩ Programming - Sat, 01 Apr 2023

 polynomial interpolation – Math ∩ Programming

 Math ∩ Programming - Wed, 16 Nov 2022

 Probability – Math ∩ Programming

 Math ∩ Programming - Sat, 14 May 2022

 “Practical Math” Preview: Collect Sensitive Survey Responses Privately

 Math ∩ Programming - Sat, 14 May 2022

 Singular Value Decomposition Part 1: Perspectives on Linear Algebra

 Math ∩ Programming - Mon, 18 Apr 2016

 Markov Chain Monte Carlo Without all the Bullshit

 Math ∩ Programming - Mon, 06 Apr 2015

 A Good Year for “A Programmer's Introduction to Mathematics”

 Math ∩ Programming - Sun, 01 Dec 2019

 Jeremy Kun | Writers

 EdSurge - Tue, 06 Oct 2015

 Topology – Math ∩ Programming

 Math ∩ Programming - Tue, 24 Jul 2018

 Jeremy Kun Agenda Contributor | World Economic Forum

 World Economic Forum - Mon, 18 Jan 2016

 Table of Contents for PIM – Math ∩ Programming

 Math ∩ Programming - Sat, 20 Oct 2018

 When Greedy Algorithms are Good Enough: Submodularity and the (1 – 1/e)-Approximation

 Math ∩ Programming - Mon, 07 Jul 2014

 The Quantum Bit – Math ∩ Programming

 Math ∩ Programming - Mon, 15 Dec 2014

 games – Math ∩ Programming

 Math ∩ Programming - Sun, 31 Aug 2014

 The Reasonable Effectiveness of the Multiplicative Weights Update Algorithm

 Math ∩ Programming - Mon, 27 Feb 2017

 Computing Homology – Math ∩ Programming

 Math ∩ Programming - Wed, 10 Apr 2013

 Kolmogorov Complexity – A Primer – Math ∩ Programming

 Math ∩ Programming - Sat, 21 Apr 2012

 Learning Programming — Finger-Painting and Killing Zombies

 Math ∩ Programming - Thu, 15 Mar 2012

 The Gadget Decomposition in FHE – Math ∩ Programming

 Math ∩ Programming - Sat, 11 Dec 2021

 Support Math ∩ Programming by becoming a patron! – Math ∩ Programming

 Math ∩ Programming - Mon, 10 Aug 2015

 A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details

 Math ∩ Programming - Thu, 12 Nov 2015

 Encryption & RSA – Math ∩ Programming

 Math ∩ Programming - Fri, 29 Jul 2011

 What does it mean for an algorithm to be fair?

 Math ∩ Programming - Mon, 13 Jul 2015

 DIY Tracking Apps with Google Forms – Math ∩ Programming

 Math ∩ Programming - Fri, 08 Mar 2019

 Formulating the Support Vector Machine Optimization Problem

 Math ∩ Programming - Mon, 05 Jun 2017

 Searching for RH Counterexamples — Exploring Data – Math ∩ Programming

 Math ∩ Programming - Mon, 14 Jun 2021

 A Programmer's Introduction to Mathematics by Jeremy Kun

 Goodreads - Tue, 27 Nov 2018

 Searching for RH Counterexamples — Setting up Pytest

 Math ∩ Programming - Fri, 11 Sep 2020

 How to Take a Calculus Test – Math ∩ Programming

 Math ∩ Programming - Thu, 20 Oct 2011

 Methods of Proof — Diagonalization – Math ∩ Programming

 Math ∩ Programming - Mon, 08 Jun 2015

 The Welch-Berlekamp Algorithm for Correcting Errors in Data

 Math ∩ Programming - Mon, 07 Sep 2015

 Cocktails – Math ∩ Programming

 Math ∩ Programming - Fri, 01 Apr 2022

 vc-dimension – Math ∩ Programming

 Math ∩ Programming - Mon, 21 Sep 2015

 A parlor trick for SET – Math ∩ Programming

 Math ∩ Programming - Sun, 25 Mar 2018

 When Greedy Algorithms are Perfect: the Matroid

 Math ∩ Programming - Tue, 26 Aug 2014

 A Spectral Analysis of Moore Graphs – Math ∩ Programming

 Math ∩ Programming - Thu, 03 Nov 2016

 mandelbrot set – Math ∩ Programming

 Math ∩ Programming - Mon, 26 May 2014

 Regression and Linear Combinations – Math ∩ Programming

 Math ∩ Programming - Mon, 29 Mar 2021

 The Boosting Margin, or Why Boosting Doesn't Overfit

 Math ∩ Programming - Mon, 21 Sep 2015

 video games – Math ∩ Programming

 Math ∩ Programming - Mon, 17 Mar 2014

 randomized algorithm – Math ∩ Programming

 Math ∩ Programming - Sat, 14 May 2022

 The Many Faces of Set Cover – Math ∩ Programming

 Math ∩ Programming - Mon, 04 May 2015

 Singular Value Decomposition Part 2: Theorem, Proof, Algorithm

 Math ∩ Programming - Mon, 16 May 2016

 Tiling a Chessboard with Dominoes (Opposite Colors Removed)

 Math ∩ Programming - Fri, 18 Nov 2011

 docker – Math ∩ Programming

 Math ∩ Programming - Mon, 04 Jan 2021

 Depth- and Breadth-First Search – Math ∩ Programming

 Math ∩ Programming - Tue, 22 Jan 2013

 geographic profiling – Math ∩ Programming

 Math ∩ Programming - Wed, 20 Jul 2011

 Zero Knowledge Proofs — A Primer – Math ∩ Programming

 Math ∩ Programming - Tue, 05 Jul 2016

 Earthmover Distance – Math ∩ Programming

 Math ∩ Programming - Mon, 05 Mar 2018

 Area of a Triangle – Math ∩ Programming

 Math ∩ Programming - Fri, 24 Jun 2011

 graph isomorphism – Math ∩ Programming

 Math ∩ Programming - Tue, 05 Jul 2016

 proofs without words – Page 2 – Math ∩ Programming

 Math ∩ Programming - Tue, 05 Jul 2011

 homomorphic encryption – Math ∩ Programming

 Math ∩ Programming - Mon, 10 Jun 2013

 Conway's Game of Life in Conway's Game of Life – Math ∩ Programming

 Math ∩ Programming - Thu, 03 Nov 2011

 torus-quotient – Math ∩ Programming

 Math ∩ Programming - Sun, 11 Nov 2012

 The Mathematics of Secret Sharing – Math ∩ Programming

 Math ∩ Programming - Mon, 23 Jun 2014

 The Codes of Solomon, Reed, and Muller

 Math ∩ Programming - Mon, 23 Mar 2015

 A Working Mathematician's Guide to Parsing – Math ∩ Programming

 Math ∩ Programming - Sat, 20 Apr 2019

 The Complexity of Communication – Math ∩ Programming

 Math ∩ Programming - Mon, 10 Nov 2014

 My LaTeX Workflow: latexmk, ShareLaTeX, and StackEdit

 Math ∩ Programming - Sat, 10 Jan 2015

 salvador dali – Math ∩ Programming

 Math ∩ Programming - Mon, 29 Sep 2014

 multiplicative weights update algorithm – Math ∩ Programming

 Math ∩ Programming - Fri, 08 Nov 2013

 NP-hard does not mean hard – Math ∩ Programming

 Math ∩ Programming - Fri, 29 Dec 2017

 Hanabi: a card game for logicians – Math ∩ Programming

 Math ∩ Programming - Fri, 10 Aug 2018

 Binary Search on Graphs – Math ∩ Programming

 Math ∩ Programming - Wed, 08 Nov 2017

 wasserstein metric – Math ∩ Programming

 Math ∩ Programming - Mon, 05 Mar 2018

 Mathematical Genealogy – Math ∩ Programming

 Math ∩ Programming - Thu, 22 Jun 2017

 Determinism and Finite Automata – A Primer – Math ∩ Programming

 Math ∩ Programming - Sat, 02 Jul 2011

 A Programmer's Introduction to Mathematics: Second Edition: 9798625373425: Kun, Jeremy: Books

 Amazon.com - Thu, 21 May 2020

 low-complexity art – Math ∩ Programming

 Math ∩ Programming - Mon, 13 May 2013

 A Motivation for Quantum Computing – Math ∩ Programming

 Math ∩ Programming - Mon, 08 Dec 2014

 Other Complexity Classes – Math ∩ Programming

 Math ∩ Programming - Wed, 29 Feb 2012

 introspection – Math ∩ Programming

 Math ∩ Programming - Sun, 26 Jun 2011

 topological invariant – Math ∩ Programming

 Math ∩ Programming - Wed, 03 Apr 2013

 coproducts – Math ∩ Programming

 Math ∩ Programming - Fri, 24 May 2013

 Programming is not math, huh?

 Svbtle - Fri, 18 Jul 2014

 Show all results...

 Flickr

 Jeremy Solang - @Jayy-kun

 Jeremy Irabagon - @meki_kun

 Pinterest

 Jeremy Kun - @jkun

 15 followers

 Jeremy Kun - @jeremyturismo

 8 followers

 Jeremy -kun - @jeremyvgt49

 0 followers

 Jeremy Kun Bosman - @jeremykunb

 0 followers

 Jeremy Kun - @jeremykunlikesmemes

 0 followers

 Jeremy Kun - @jeremykun

 0 followers

 Jeremy-kun - @jerzamca2007

 0 followers

 Jeremy -kun - @jeremyd1005

 0 followers

 Jeremy kun - @alexalvarado23450323

 0 followers

 Jeremy Kun - @malkahjere

 0 followers

 Jeremy Kun - @jeremykun04

 0 followers

 jeremy kun benites - @jedebesa09

 0 followers

 Jeremy Kun - @jeremykun9029

 0 followers

 Jeremy Kun - @jeremykun004

 0 followers

 Jeremy Kun - @jeremykun85

 0 followers

 Daniel Jeremy-kun - @danieljeremy28

 0 followers

 Jeremy- Kun - @yamato_1005

 0 followers

 Jeremykun - @jeremykun24

 0 followers

 Jeremy Kun - @brandondeblv

 0 followers

 Jeremy_Kun - @galax403yt

 0 followers

 JeremyKun Carranza Medina - @carranzamedinajeremyfederico

 0 followers

 ᄬ꧁jeremykun꧂ツ - @jeremyampaimorales

 0 followers

 Jeremy Kun's - @jeremykuns

 0 followers

 Jérémy Kún Masia - @jrmykn

 5 followers

 Show all results...

 Quora

 Jeremy Kun

 Computer scientist

 Jeremy Kun

 Knows Indonesian

 Jeremy Kun

 Jeremy Bagto-Kun

 Jeremy Kunnings

 Knows French

 Trunks Kun Jeremy

 Knows German

 Show all results...

 Other Profiles

 Jeremy KUN

 researchgate.net

 Archives

 Price of Anarchy for Graph Coloring Games with Concave Payoff

 Arxiv.org

 ... 404—413,1999. doi:i0.i007/3-540-49ii6-3_38. [25] Jeremy Kun, Brian Powers, and Lev Reyzin. Anti-coordination...

 Interception in Distance-Vector Routing Networks

 Arxiv.org

 ... of Pittsburgh Franklin Renter Rice University Jeremy Kun University of Illinois at Chicago Feng Shi University...

 doingmathwithpython

 Community Texts

 ... Seph Kramer and Tyler Ortman Technical Reviewer: Jeremy Kun Copyeditor: Julianne Jigour Compositor: Riley...

 The Times News (Idaho Newspaper) 1992-12-09

 The Times News (Idaho Newspaper)

 ... 456.307 in 1992. ^mcs. Nikki Fife. Kclh Fries. Jeremy Kun/lcr. Carrie m. ..ews. Holland. Todd Leone. Baraquicl...

 Impractical Python Project

 Folkscanomy Computer: Inbox and Miscellaneous

 ... Developmental Editor: Zach Lebowski Technical Reviewers: Jeremy Kun, Michael Contraveos, and Michele Pratusevich...

 Web results

 About the Author – Math ∩ Programming

 I'm Jeremy Kun. I'm currently an engineer at Google and I live in Portland, Oregon. Books In 2018 I published A Programmer's Introduction to Mathematics. Currently I'm working on Practical Math for Programmers: A Tour of Math in Production Software. Schooling I earned a PhD in … See more

 Math ∩ Programming

 Posted on July 10, 2023 by Jeremy Kun Before I discovered math, I was a first year undergrad computer science student taking Electrical Engineering 101. The first topic I learned was what bits and boolean gates are, and the …

 Jeremy Kun – The Conversation

 Jeremy Kun 1 Article 2 Comments PhD Student in Mathematics, University of Illinois Chicago Profile Articles Activity I am a theoretical computer scientist with broad interests, including...

 ‪Jeremy Kun‬ - ‪Google Scholar‬

 Jeremy Kun. Algorithmic Game Theory: 6th International Symposium, SAGT 2013, Aachen …. Distributed Computing: 29th International Symposium, DISC 2015, Tokyo, Japan …. Graph …

 A Programmer's Introduction to Mathematics Paperback

 A Programmer's Introduction to Mathematics is written by Jeremy Kun, who has been writing about math and programming for 8 years on his blog "Math Intersect Programming." As of …

 Primers – Math ∩ Programming

 Primers. As a fair warning to the reader, these primers are a bit more terse than what you’d find in your average textbook. I only introduce the bare minimum required to understand …

 Jeremy Kun, Author at Social Science Space

 Jeremy Kun. Jeremy Kun is a theoretical computer scientist at the University of Illinois at Chicago with broad interests, including complexity theory, graph theory and network …

 Main Content – Math ∩ Programming

 When Greedy is Good Enough: Submodularity and the 1 – 1/e Approximation. When Greedy Algorithms are Perfect: the Matroid. Linear Programming and Healthy Diets Part 1. Linear …

 Jeremy Kun — Curriculum Vitae - University of Illinois Chicago

 Jeremy Kun. Research summary. I am a theoretical computer scientist with broad interests, including complexity theory, graph theory and network science, learning theory, …

 My next book will be “Practical Math for Programmers”

 Posted on March 16, 2022 by Jeremy Kun tl;dr: I’m writing a new book, sign up for the announcements mailing list. I’ve written exactly zero new technical blog posts this …

 A Programmer's Introduction to Mathematics - Google Books

 Jeremy Kun. , May 17, 2020 - Computer science - 400 pages. 0 Reviews. A Programmer's Introduction to Mathematics uses your familiarity with ideas from …

 Jeremy Kun (Author of A Programmer's Introduction to Mathematics)

 Jeremy Kun is the author of A Programmer's Introduction to Mathematics (4.06 avg rating, 78 ratings, 11 reviews), Abstract Algebra, A Primer (2.00 avg ra...

 Jeremy Kun - Agenda Contributor | World Economic Forum

 Jeremy Kun is a PhD Student in Mathematics at University of Illinois at Chicago. Most Popular Data Science Do big data algorithms discriminate? 17 Aug 2015

 A Programmer's Introduction to Mathematics: Second Edition …

 A Programmer's Introduction to Mathematics is written by Jeremy Kun, who has been writing about math and programming for 10 years on his blog "Math Intersect …

 Books – Math ∩ Programming

 Posted on May 14, 2022 by Jeremy Kun. This is a draft of a chapter from my in-progress book, Practical Math for Programmers: A Tour of Mathematics in Production …

 Jeremy Kun - University of Illinois Chicago

 Benjamin Fish, Jeremy Kun, Adam Lelkes, Lev Reyzin, and Gyorgy Turan. On the Computational Complexity of MapReduce. Submitted. Submitted. Rajmonda Caceres, Kevin …

 Amazon.ca: Jeremy Kun: Books

 4.7 (40) Paperback $5028 FREE delivery Fri, Mar 31 A Programmer's Introduction to Mathematics by Dr. Jeremy Kun | Nov 27 2018 4.4 (94) Paperback Need help? Visit the …

 A Programmer's Introduction to Mathematics Paperback …

 A Programmer's Introduction to Mathematics is written by Jeremy Kun, who has been writing about math and programming for 8 years on his blog …

 A Programmer's Introduction to Mathematics

 In short, this book will teach you to engage with mathematics. A Programmer's Introduction to Mathematics is written by Jeremy Kun, …

 Jeremy KUN | University of Illinois at Chicago, IL | UIC | Department ...

 Jeremy Kun University of Illinois at Chicago | UIC · Department of Mathematics, Statistics, and Computer Science Connect with experts in your field Join ResearchGate to contact this …

 Show all results...

 Search people online

 All states Alabama Alaska Arizona Arkansas California Colorado Connecticut Delaware District of Columbia Florida Georgia Hawaii Idaho Illinois Indiana Iowa Kansas Kentucky Louisiana Maine Maryland Massachusetts Michigan Minnesota Mississippi Missouri Montana Nebraska Nevada New Hampshire New Jersey New Mexico New York North Carolina North Dakota Ohio Oklahoma Oregon Pennsylvania Rhode Island South Carolina South Dakota Tennessee Texas Utah Vermont Virginia Washington West Virginia Wisconsin Wyoming
 Search
 Related searches: Tim Bond - Julian Moon - John Armstrong - Miguel Guevara - Kevin Lui - Audrey Addison
 Show more...

 Search Filters

 First and Last Name State Filter
 Close Menu

 Search People

 Popular social networks, phone numbers, criminal records and more.

 All states Alabama Alaska Arizona Arkansas California Colorado Connecticut Delaware District of Columbia Florida Georgia Hawaii Idaho Illinois Indiana Iowa Kansas Kentucky Louisiana Maine Maryland Massachusetts Michigan Minnesota Mississippi Missouri Montana Nebraska Nevada New Hampshire New Jersey New Mexico New York North Carolina North Dakota Ohio Oklahoma Oregon Pennsylvania Rhode Island South Carolina South Dakota Tennessee Texas Utah Vermont Virginia Washington West Virginia Wisconsin Wyoming Search

 Related searches

 * Tim Bond
 * Julian Moon
 * John Armstrong
 * Miguel Guevara
 * Kevin Lui
 * Audrey Addison

 Popular searches

 * Scott Heithoff
 * Zachary Charters
 * Gordon Baldwin
 * Valeria Vaughn
 * Scott Haylett

 Search Username

 Uncover social media profiles and real people behind a username.

 Search
 Close Menu

 People Search:

 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
 Follow us!
 * 
 * 
 * 

 About

 * About us
 * People search
 * Username search
 * Reverse phone
 * Reverse email
 * Popular searches
 * Trending searches
 * New searches
 * Updated pages
 * Sitemap
 * Terms
 * Privacy
 * Remove my information
 * Contact us

 Latest Searches

 * Grant Tharaldson
 * Angela Zuccaro
 * Andrew Giovinazzo
 * Angela Zubiri
 * Popat Patil
 * Shaila Patil
 * Angela Zornes
 * Neerja Thakur
 * Aarushi Patil
 * Rohini Hiremath
 * Angela Zonin

 Popular Searches

 * Scott Helman
 * Ethiopia Jackson
 * Evangeline Brady
 * Scott Helvey
 * Marjorie Page
 * Bin Duan
 * Nancy Suddoth
 * Sandra Ramsdell
 * Carlo Guanlao
 * Sandy Page
 * more...

 DISCLAIMER: IDCrawl is not a consumer reporting agency, and IDCrawl products do not constitute a "consumer report" as defined by the Fair Credit Reporting Act (FCRA). IDCrawl products may not be used to determine eligibility for credit, insurance, employment or used for any other purpose governed by the FCRA.


 Copyright © 2024 IDCrawl LLC. All rights reserved

 Continue
 We use cookies to enhance your experience. By continuing to visit this site you agree to our use of cookies. More info
People Search   J   Jeremy...Landin  Jeremy Kun         Public Records    Sponsored by Spokeo          Email Addresses    Sponsored by Spokeo          TikTok                   jeremykun - @jeremykun   Car Enthusiastic, Coffee Enthusiastic handsets is recommended for my video 🎧826 followers                                   Youtube                                                       KUKAN Drama Channel - @KukanDrama       Welcome to subscribe to our channel for the latest Chinese TV drama, thanks for your support~ ❤️New drama continues to be ...1.75M subscribers                                LinkedIn             Kun Zhou   Seeking Next Challenge at blockprime                   Tim Bond   Program technical advisor (SETA) at DARPA I2O at ManTech                   Ke Jin   Programmer, PhD in Applied Math                   Jeremy P.   Testconsultant Landelijke Meldkamer Samenwerking                                                           Websites    Websites owned by Jeremy Kun   jeremykun.com  Registered on December 19, 2012         Archives                   doingmathwithpython  Community Texts  ... Seph Kramer and Tyler Ortman Technical Reviewer: Jeremy Kun Copyeditor: Julianne Jigour Compositor: Riley...               Impractical Python Project  Folkscanomy Computer: Inbox and Miscellaneous  ... Developmental Editor: Zach Lebowski Technical Reviewers: Jeremy Kun, Michael Contraveos, and Michele Pratusevich...           Web results      About the Author – Math ∩ Programming   I'm Jeremy Kun. I'm currently an engineer at Google and I live in Portland, Oregon. Books In 2018 I published A Programmer's Introduction to Mathematics. Currently I'm working on Practical Math for Programmers: A Tour of Math in Production Software. Schooling I earned a PhD in … See more     Math ∩ Programming   Posted on July 10, 2023 by Jeremy Kun Before I discovered math, I was a first year undergrad computer science student taking Electrical Engineering 101. The first topic I learned was what bits and boolean gates are, and the …     Jeremy Kun – The Conversation   Jeremy Kun 1 Article 2 Comments PhD Student in Mathematics, University of Illinois Chicago Profile Articles Activity I am a theoretical computer scientist with broad interests, including...     ‪Jeremy Kun‬ - ‪Google Scholar‬   Jeremy Kun. Algorithmic Game Theory: 6th International Symposium, SAGT 2013, Aachen …. Distributed Computing: 29th International Symposium, DISC 2015, Tokyo, Japan …. Graph …     Primers – Math ∩ Programming   Primers. As a fair warning to the reader, these primers are a bit more terse than what you’d find in your average textbook. I only introduce the bare minimum required to understand …     Jeremy Kun, Author at Social Science Space   Jeremy Kun. Jeremy Kun is a theoretical computer scientist at the University of Illinois at Chicago with broad interests, including complexity theory, graph theory and network …     Main Content – Math ∩ Programming   When Greedy is Good Enough: Submodularity and the 1 – 1/e Approximation. When Greedy Algorithms are Perfect: the Matroid. Linear Programming and Healthy Diets Part 1. Linear …     Books – Math ∩ Programming   Posted on May 14, 2022 by Jeremy Kun. This is a draft of a chapter from my in-progress book, Practical Math for Programmers: A Tour of Mathematics in Production …     Amazon.ca: Jeremy Kun: Books   4.7 (40) Paperback $5028 FREE delivery Fri, Mar 31 A Programmer's Introduction to Mathematics by Dr. Jeremy Kun | Nov 27 2018 4.4 (94) Paperback Need help? Visit the …            Continue
Jeremy Kun's Instagram, Twitter & Facebook on IDCrawl
https://www.idcrawl.com/jeremy-kun
https://www.linkedin.com/in/jeremy-guo-342571a0
Jeremy Guo - Amazon Web Services (AWS) | LinkedIn
2024-01-01
Jeremy Guo
<div><div>
<section>
<section>
<figure>
</figure>
</section>
<div>
<h2>
 Activity
 </h2>
</div>
<section>
<h2>
 
 Experience &amp; Education
 
 </h2>
<div>
<ul>
<li>
<div>
<h3>
 
 Amazon Web Services (AWS)
 
 </h3>
<h4>
</h4>
</div>
</li>
</ul>
<div>
<h2>View Jeremy’s full experience</h2>
<h3>See their title, tenure and more.</h3>
</div>
</div>
</section>
<section>
<h2>
 Courses
 </h2>
<div>
<ul>
<li>
<div>
<h3>
 
 Artificial Intelligence
 
 </h3>
<h4>
 
 CS 221
 
 </h4>
</div>
</li>
<li>
<div>
<h3>
 
 Computer Systems and Organization
 
 </h3>
<h4>
 
 CS 107
 
 </h4>
</div>
</li>
<li>
<div>
<h3>
 
 Data Management and Data Systems
 
 </h3>
<h4>
 
 CS 145
 
 </h4>
</div>
</li>
<li>
<div>
<h3>
 
 Design and Analysis of Algorithms
 
 </h3>
<h4>
 
 CS 161
 
 </h4>
</div>
</li>
<li>
<div>
<h3>
 
 Fundamentals of Real Analysis
 
 </h3>
<h4>
 
 Math 171
 
 </h4>
</div>
</li>
<li>
<div>
<h3>
 
 Linear Algebra and Matrix Theory
 
 </h3>
<h4>
 
 MATH 113
 
 </h4>
</div>
</li>
<li>
<div>
<h3>
 
 Machine Learning
 
 </h3>
<h4>
 
 CS 229
 
 </h4>
</div>
</li>
<li>
<div>
<h3>
 
 Operating Systems
 
 </h3>
<h4>
 
 CS 140
 
 </h4>
</div>
</li>
<li>
<div>
<h3>
 
 Optimization and Algorithmic Paradigms
 
 </h3>
<h4>
 
 CS 261
 
 </h4>
</div>
</li>
<li>
<div>
<h3>
 
 Principles of Computer Systems
 
 </h3>
<h4>
 
 CS 110
 
 </h4>
</div>
</li>
<li>
<div>
<h3>
 
 Programming Abstractions (Accelerated)
 
 </h3>
<h4>
 
 CS 106X
 
 </h4>
</div>
</li>
</ul>
</div>
</section>
<section>
<p>
<h2>
 More activity by Jeremy
 </h2>
</p>
<div>
<ul>
<li>
<div>
<p><a href="https://www.linkedin.com/posts/joceykn_this-week-was-my-last-at-asana-and-im-still-activity-6945857435081351168-M47D?trk=public_profile">
</a></p>
<p>
<h3>
 
 This week was my last at Asana, and I’m still processing a mix of emotions as I embark on my next adventure. I feel truly sad to leave behind an…
 
 </h3>
<h4>
 
 Liked by <a href="https://www.linkedin.com/in/jeremyguo2000?trk=public_profile_actor-name">Jeremy Guo</a>
</h4>
</p>
</div>
</li>
<li>
<div>
<p><a href="https://www.linkedin.com/posts/nicholashevans_sabbatical-adobe-covid-activity-6939637497102561282-AL9w?trk=public_profile">
</a></p>
<p>
<h3>
 
 Today is the last day of my first #sabbatical at #Adobe so I wanted to take a few minutes to reflect on it. Because of #covid, I delayed my 5-year…
 
 </h3>
<h4>
 
 Liked by <a href="https://www.linkedin.com/in/jeremyguo2000?trk=public_profile_actor-name">Jeremy Guo</a>
</h4>
</p>
</div>
</li>
<li>
<div>
<p><a href="https://www.linkedin.com/posts/harvard-business-review_a-3-step-process-to-break-a-cycle-of-frustration-activity-6771885437251272704-u0Cp?trk=public_profile">
</a></p>
<p>
<h3>
 
 To interrupt the frustration-stress-conflict cycle, begin by recognizing what causes you to feel thwarted, scared, or threatened.
 
 </h3>
<h4>
 
 Liked by <a href="https://www.linkedin.com/in/jeremyguo2000?trk=public_profile_actor-name">Jeremy Guo</a>
</h4>
</p>
</div>
</li>
<li>
<div>
<p><a href="https://www.linkedin.com/posts/mikebloomberg_im-honored-to-serve-as-united-nations-special-activity-6763418790907658240-TaC9?trk=public_profile">
</a></p>
<p>
<h3>
 
 I’m honored to serve as United Nations Special Envoy for Climate Ambition and Solutions, and the first Global Ambassador for the UNFCCC's Race to…
 
 </h3>
<h4>
 
 Liked by <a href="https://www.linkedin.com/in/jeremyguo2000?trk=public_profile_actor-name">Jeremy Guo</a>
</h4>
</p>
</div>
</li>
</ul>
</div>
</section>
</section>
<section>
<section>
<h2>
 People also viewed
 </h2>
</section>
<section>
<p>
<h2>
 Explore collaborative articles
 </h2>
</p>
<p>
 We’re unlocking community knowledge in a new way. Experts add insights directly into each article, started with the help of AI.
 </p>
<a href="https://www.linkedin.com/pulse/topics/home/">
 Explore More
 </a>
</section>
<section>
<h2>
 Others named <strong>Jeremy Guo</strong> in <strong>United States</strong>
</h2>
<div>
<p>
 12 others named Jeremy Guo in United States are on LinkedIn
 </p>
<p><a href="https://www.linkedin.com/pub/dir/Jeremy/Guo/us-0-United-States?trk=public_profile_samename-see-all">
 See others named <strong>Jeremy Guo</strong>
</a>
</p></div>
</section>
</section>
</div></div>||||I||||Skip to main content
LinkedIn
 * Articles
 * People
 * Learning
 * Jobs
 Join now Sign in

 Jeremy Guo

 Sign in to view Jeremy’s full profile

 Sign in

 Welcome back

 Email or phone

 Password
 Show

 Forgot password? Sign in

 or

 By clicking Continue to join or sign in, you agree to LinkedIn’s User Agreement, Privacy Policy, and Cookie Policy.

 New to LinkedIn? Join now

 or

 By clicking Continue to join or sign in, you agree to LinkedIn’s User Agreement, Privacy Policy, and Cookie Policy.

 New to LinkedIn? Join now

 Greater Seattle Area Contact Info

 Sign in to view Jeremy’s full profile

 Sign in

 Welcome back

 Email or phone

 Password
 Show

 Forgot password? Sign in

 or

 By clicking Continue to join or sign in, you agree to LinkedIn’s User Agreement, Privacy Policy, and Cookie Policy.

 New to LinkedIn? Join now

 or

 By clicking Continue to join or sign in, you agree to LinkedIn’s User Agreement, Privacy Policy, and Cookie Policy.

 New to LinkedIn? Join now

 136 followers 134 connections

 See your mutual connections

 View mutual connections with Jeremy

 Sign in

 Welcome back

 Email or phone

 Password
 Show

 Forgot password? Sign in

 or

 By clicking Continue to join or sign in, you agree to LinkedIn’s User Agreement, Privacy Policy, and Cookie Policy.

 New to LinkedIn? Join now

 or

 By clicking Continue to join or sign in, you agree to LinkedIn’s User Agreement, Privacy Policy, and Cookie Policy.

 New to LinkedIn? Join now

 Join to view profile
 Message

 Sign in to view Jeremy’s full profile

 Sign in

 Welcome back

 Email or phone

 Password
 Show

 Forgot password? Sign in

 or

 By clicking Continue to join or sign in, you agree to LinkedIn’s User Agreement, Privacy Policy, and Cookie Policy.

 New to LinkedIn? Join now

 or

 By clicking Continue to join or sign in, you agree to LinkedIn’s User Agreement, Privacy Policy, and Cookie Policy.

 New to LinkedIn? Join now

 Amazon Web Services (AWS)
 Stanford University
 * Report this profile

 Activity

 Follow

 Sign in to view Jeremy’s full profile

 Sign in

 Welcome back

 Email or phone

 Password
 Show

 Forgot password? Sign in

 or

 By clicking Continue to join or sign in, you agree to LinkedIn’s User Agreement, Privacy Policy, and Cookie Policy.

 New to LinkedIn? Join now

 or

 By clicking Continue to join or sign in, you agree to LinkedIn’s User Agreement, Privacy Policy, and Cookie Policy.

 New to LinkedIn? Join now

 * We made many improvements to Havana over the last few weeks. It's had a big impact on our user satisfaction 👇 First, some context: Havana is an…

 We made many improvements to Havana over the last few weeks. It's had a big impact on our user satisfaction 👇 First, some context: Havana is an…

 Liked by Jeremy Guo

 * Atlassian's sales and marketing costs are a fraction of their peers. Here's how they grew to $30B on an efficient GTM budget 👇 At IPO, Atlassian…

 Atlassian's sales and marketing costs are a fraction of their peers. Here's how they grew to $30B on an efficient GTM budget 👇 At IPO, Atlassian…

 Liked by Jeremy Guo

 * Hi friends -- I know it has been a tough month in the tech world with dozens of companies announcing layoffs. If you or someone you know is looking…

 Hi friends -- I know it has been a tough month in the tech world with dozens of companies announcing layoffs. If you or someone you know is looking…

 Liked by Jeremy Guo

 Join now to see all activity

 Experience & Education

 * Amazon Web Services (AWS)

 ******** *********** ********

 * ********* **

 ******** *********** ******

 * *********** ******* **********, ********** ** ********** ***********

 ******** *********

 * ******** **********

 ******** ** ******* (*.*.), ******** ******* ******** *******

 2014 - 2018

 View Jeremy’s full experience

 See their title, tenure and more.

 Sign in

 Welcome back

 Email or phone

 Password
 Show

 Forgot password? Sign in

 or

 By clicking Continue to join or sign in, you agree to LinkedIn’s User Agreement, Privacy Policy, and Cookie Policy.

 New to LinkedIn? Join now

 or

 By clicking Continue to join or sign in, you agree to LinkedIn’s User Agreement, Privacy Policy, and Cookie Policy.

 Courses

 * Artificial Intelligence

 CS 221

 * Computer Systems and Organization

 CS 107

 * Data Management and Data Systems

 CS 145

 * Design and Analysis of Algorithms

 CS 161

 * Fundamentals of Real Analysis

 Math 171

 * Linear Algebra and Matrix Theory

 MATH 113

 * Machine Learning

 CS 229

 * Operating Systems

 CS 140

 * Optimization and Algorithmic Paradigms

 CS 261

 * Principles of Computer Systems

 CS 110

 * Programming Abstractions (Accelerated)

 CS 106X

 More activity by Jeremy

 * This week was my last at Asana, and I’m still processing a mix of emotions as I embark on my next adventure. I feel truly sad to leave behind an…

 This week was my last at Asana, and I’m still processing a mix of emotions as I embark on my next adventure. I feel truly sad to leave behind an…

 Liked by Jeremy Guo

 * Today is the last day of my first #sabbatical at #Adobe so I wanted to take a few minutes to reflect on it. Because of #covid, I delayed my 5-year…

 Today is the last day of my first #sabbatical at #Adobe so I wanted to take a few minutes to reflect on it. Because of #covid, I delayed my 5-year…

 Liked by Jeremy Guo

 * To interrupt the frustration-stress-conflict cycle, begin by recognizing what causes you to feel thwarted, scared, or threatened.

 To interrupt the frustration-stress-conflict cycle, begin by recognizing what causes you to feel thwarted, scared, or threatened.

 Liked by Jeremy Guo

 * I’m honored to serve as United Nations Special Envoy for Climate Ambition and Solutions, and the first Global Ambassador for the UNFCCC's Race to…

 I’m honored to serve as United Nations Special Envoy for Climate Ambition and Solutions, and the first Global Ambassador for the UNFCCC's Race to…

 Liked by Jeremy Guo

 View Jeremy’s full profile

 * See who you know in common
 * Get introduced
 * Contact Jeremy directly
 Join to view full profile

 Sign in

 Stay updated on your professional world

 Sign in

 By clicking Continue to join or sign in, you agree to LinkedIn’s User Agreement, Privacy Policy, and Cookie Policy.

 New to LinkedIn? Join now

People also viewed

 * Mian Guan

 United States
 Connect

 * Manli Mary Gu

 Software Development Engineer 2 at Amazon

 Bellevue, WA
 Connect

 * Aozixuan (Priscilla) Guan, CISSP

 Austin, TX
 Connect

 * tom G.

 Seattle, WA
 Connect

 * Wenjia Guan

 Software Engineer at Amazon

 Sammamish, WA
 Connect

 * Peter Guan

 California, United States
 Connect

 * Yichen Gu

 Software Engineer

 Sunnyvale, CA
 Connect

 * Mingyun Guan

 Greater Seattle Area
 Connect

 * Chao Gui

 New York, NY
 Connect

 * Steven Guan

 San Francisco Bay Area
 Connect

 Explore collaborative articles

 We’re unlocking community knowledge in a new way. Experts add insights directly into each article, started with the help of AI.

 Explore More

Others named Jeremy Guo in United States

 * Jeremy Guo

 Enterprise Sales Engineering Manager at Motive

 Everett, WA

 * Jeremy Guo

 New York City Metropolitan Area

 * Jeremy Guo

 Production Manager at Reichhold

 El Segundo, CA

 * Jeremy Guo

 machine learning at University of Alberta

 San Francisco Bay Area

 12 others named Jeremy Guo in United States are on LinkedIn

 See others named Jeremy Guo
 * LinkedIn © 2024
 * About
 * Accessibility
 * User Agreement
 * Privacy Policy
 * Your California Privacy Choices
 * Cookie Policy
 * Copyright Policy
 * Brand Policy
 * Guest Controls
 * Community Guidelines
 * 
 + العربية (Arabic)
 + Čeština (Czech)
 + Dansk (Danish)
 + Deutsch (German)
 + English (English)
 + Español (Spanish)
 + Français (French)
 + हिंदी (Hindi)
 + Bahasa Indonesia (Indonesian)
 + Italiano (Italian)
 + 日本語 (Japanese)
 + 한국어 (Korean)
 + Bahasa Malaysia (Malay)
 + Nederlands (Dutch)
 + Norsk (Norwegian)
 + Polski (Polish)
 + Português (Portuguese)
 + Română (Romanian)
 + Русский (Russian)
 + Svenska (Swedish)
 + ภาษาไทย (Thai)
 + Tagalog (Tagalog)
 + Türkçe (Turkish)
 + Українська (Ukrainian)
 + 简体中文 (Chinese (Simplified))
 + 正體中文 (Chinese (Traditional))
 Language

 Agree & Join LinkedIn

 By clicking Continue to join or sign in, you agree to LinkedIn’s User Agreement, Privacy Policy, and Cookie Policy.

 Sign in to view Jeremy’s full profile

 Sign in

 Welcome back

 Email or phone

 Password
 Show

 Forgot password? Sign in

 or

 By clicking Continue to join or sign in, you agree to LinkedIn’s User Agreement, Privacy Policy, and Cookie Policy.

 New to LinkedIn? Join now

 or

 By clicking Continue to join or sign in, you agree to LinkedIn’s User Agreement, Privacy Policy, and Cookie Policy.

 New to LinkedIn? Join now

Activity
 
 
 Experience &amp; Education
 
 
 
 Amazon Web Services (AWS)
 
 
View Jeremy’s full experience
See their title, tenure and more.
 Courses
 
 
 Artificial Intelligence
 
 
 
 CS 221
 
 
 
 Computer Systems and Organization
 
 
 
 CS 107
 
 
 
 Data Management and Data Systems
 
 
 
 CS 145
 
 
 
 Design and Analysis of Algorithms
 
 
 
 CS 161
 
 
 
 Fundamentals of Real Analysis
 
 
 
 Math 171
 
 
 
 Linear Algebra and Matrix Theory
 
 
 
 MATH 113
 
 
 
 Machine Learning
 
 
 
 CS 229
 
 
 
 Operating Systems
 
 
 
 CS 140
 
 
 
 Optimization and Algorithmic Paradigms
 
 
 
 CS 261
 
 
 
 Principles of Computer Systems
 
 
 
 CS 110
 
 
 
 Programming Abstractions (Accelerated)
 
 
 
 CS 106X
 
 
 More activity by Jeremy
 
 
 
 
 This week was my last at Asana, and I’m still processing a mix of emotions as I embark on my next adventure. I feel truly sad to leave behind an…
 
 
 
 Liked by Jeremy Guo
 
 
 
 Today is the last day of my first #sabbatical at #Adobe so I wanted to take a few minutes to reflect on it. Because of #covid, I delayed my 5-year…
 
 
 
 Liked by Jeremy Guo
 
 
 
 To interrupt the frustration-stress-conflict cycle, begin by recognizing what causes you to feel thwarted, scared, or threatened.
 
 
 
 Liked by Jeremy Guo
 
 
 
 I’m honored to serve as United Nations Special Envoy for Climate Ambition and Solutions, and the first Global Ambassador for the UNFCCC's Race to…
 
 
 
 Liked by Jeremy Guo
 People also viewed
 
 Explore collaborative articles
 
 We’re unlocking community knowledge in a new way. Experts add insights directly into each article, started with the help of AI.
 
 Explore More
 
 Others named Jeremy Guo in United States
 12 others named Jeremy Guo in United States are on LinkedIn
 
 
 See others named Jeremy Guo
Jeremy Guo - Amazon Web Services (AWS) | LinkedIn
https://www.linkedin.com/in/jeremy-guo-342571a0