2e:null 2f:["$","title",null,{"children":"Lattice reduction | Bryan Gin-ge Chen | Observable"}] 34:T122c,viewof pic = { const SQRT3_2 = Math.sqrt(3)/2; const context = DOM.context2d(width, height); const frames = new Map(); function initLattice() { const ax = Math.random()*100; const ay = Math.random()*100; const bx = Math.random()*100; const by = Math.random()*100; const latt = ({ax,ay,bx,by}); [[latt.ax,latt.ay], [latt.bx,latt.by]] = reduceBasis([ax,ay],[bx,by]); const n = Math.min(height,width)/Math.max(Math.abs(latt.ax),Math.abs(latt.ay), Math.abs(latt.bx),Math.abs(latt.by)) / 4; latt.ax *= n; latt.ay *= n; latt.bx *= n; latt.by *= n; return latt; } let state = this ? this.value.state : ({}); let lattice = this ? this.value.lattice : initLattice(); function render(context, state, lattice) { context.fillStyle = `#333`; context.fillRect(0, 0, width, height); state.particles = getParticles(object.m, object.n, lattice); renderVoronoi(context, state, lattice); renderLattice(context, state); renderBasis(context, lattice, state.clicked); const {ax,ay,bx,by} = lattice; const fontSize = Math.min(20, Math.sqrt(ax*ax+ay*ay)/3, Math.sqrt(bx*bx+by*by)/3); if (object.labelPoints) renderTextLattice(context, state, {textFunc:({i,j}) => `(${j},${i})`, fontSize, shift:fontSize*3/2}); context.canvas.value = {state, lattice}; context.canvas.dispatchEvent(new CustomEvent('input')); } function testDist(x1,y1,x2,y2,r) { const dx = x1-x2; const dy = y1-y2; const dist = dx*dx+dy*dy; return dist < r*r; } function dragSubject() { const {x,y} = d3.event; const x0 = x - width/2; const y0 = height/2 - y; const dd0 = x0*x0 + y0*y0; const ang0 = Math.atan2(y0,x0); const {ax,ay,bx,by} = lattice; let type, dx, dy; if (testDist(x0,y0, ax,ay, 10)) { state.clicked = type = 'a'; // lattice vector a renderBasis(context, lattice, 'a'); dx = x0-ax; dy = y0-ay; } else if (testDist(x0,y0, bx,by, 10)) { state.clicked = type = 'b'; // lattice vector b renderBasis(context, lattice, 'b'); dx = x0-bx; dy = y0-by; } else type = 'B'; // background return {type, dd0,ang0, ax,ay,bx,by, dx,dy}; } function dragged() { const {x,y, subject:{type, dd0,ang0, ax,ay,bx,by, dx,dy}} = d3.event; const x1 = x - width/2; const y1 = height/2 - y; switch (type) { case 'a': { lattice.ax = x1-dx; lattice.ay = y1-dy; break; } case 'b': { lattice.bx = x1-dx; lattice.by = y1-dy; break; } case 'B': { // zoom and rotate const ang = Math.atan2(y1,x1); const scale = Math.sqrt((x1*x1 + y1*y1) / dd0); const c = Math.cos(ang-ang0); const s = Math.sin(ang-ang0); lattice.ax = scale*(c*ax - s*ay); lattice.ay = scale*(s*ax + c*ay); lattice.bx = scale*(c*bx - s*by); lattice.by = scale*(s*bx + c*by); break; } } render(context, state, lattice); } function dragEnd() { const {ax,ay,bx,by} = lattice; [[lattice.ax,lattice.ay], [lattice.bx,lattice.by]] = reduceBasis([ax,ay],[bx,by]); state.clicked = null; render(context, state, lattice); } d3.select(context.canvas).call( d3.drag().subject(dragSubject) .on("drag", dragged) .on("end", dragEnd) ); function tick(it, f, key) { render(context, state, lattice = it(d3.easeCubic(f / 90))); if (f < 90) frames.set(key, requestAnimationFrame(() => tick(it,f,key))); f++; } function cancelAll() { for (const frame of frames) cancelAnimationFrame(frame); } context.canvas.addEventListener('reset', () => { cancelAll(); const finLattice = initLattice(); const it = d3.interpolate(lattice, finLattice); let f = 0; tick(it, f, 'reset'); }); context.canvas.addEventListener('square', () => { cancelAll(); const finLattice = Object.assign({}, lattice); finLattice.bx = -lattice.ay; finLattice.by = lattice.ax; const it = d3.interpolate(lattice, finLattice); let f = 0; tick(it, f, 'square'); }); context.canvas.addEventListener('triangular', () => { cancelAll(); const finLattice = Object.assign({}, lattice); finLattice.bx = lattice.ax/2 - lattice.ay*SQRT3_2; finLattice.by = SQRT3_2*lattice.ax + lattice.ay/2; const it = d3.interpolate(lattice, finLattice); let f = 0; tick(it, f, 'triangular'); }); render(context, state, lattice); invalidation.then(cancelAll); return context.canvas; }35:T661,function renderBasis(context, {ax, ay, bx, by}, clicked=null) { context.save(); context.translate(width / 2, height / 2); // draw parallelogram context.beginPath(); context.moveTo(0,0); context.lineTo(ax,-ay); context.lineTo(ax+bx,-ay-by); context.lineTo(bx,-by); context.lineTo(0,0); context.lineWidth = '3'; context.strokeStyle = 'rgba(255,0,255,1)'; context.stroke(); context.lineWidth = '2'; // a context.beginPath(); context.arc(ax, -ay, clicked === 'a' ? 11 : 8, 0, 2 * Math.PI); context.fillStyle = 'rgba(128,255,128,1)'; context.fill(); if (clicked === 'a') context.stroke(); context.beginPath(); context.arc(ax, -ay, 3, 0, 2 * Math.PI); context.fillStyle = 'rgba(0,150,0,1)'; context.fill(); // b context.beginPath(); context.arc(bx, -by, clicked === 'b' ? 11 : 8, 0, 2 * Math.PI); context.fillStyle = 'rgba(128,128,255,1)'; context.fill(); if (clicked === 'b') context.stroke(); context.beginPath(); context.arc(bx, -by, 3, 0, 2 * Math.PI); context.fillStyle = 'rgba(0,150,0,1)'; context.fill(); // a+b context.beginPath(); context.arc(ax+bx, -ay-by, 5, 0, 2 * Math.PI); context.fillStyle = 'rgba(255,128,128,1)'; context.fill(); context.beginPath(); context.arc(ax+bx, -ay-by, 3, 0, 2 * Math.PI); context.fillStyle = 'rgba(0,150,0,1)'; context.fill(); // origin context.beginPath(); context.arc(0, 0, 5, 0, 2 * Math.PI); context.fillStyle = 'rgba(255,0,0,1)'; context.fill(); context.beginPath(); context.arc(0, 0, 3, 0, 2 * Math.PI); context.fillStyle = 'rgba(0,150,0,1)'; context.fill(); context.restore(); }36:[] 32:{"id":"0d0d4e55f05ea8aa","slug":"lattice-reduction","title":"Lattice reduction","thumbnail":"5386f409387e1976844feaa5a20f3c2bd3d99ff33f3915684956c4dbbc94fb93","access_level":"public","create_time":"$D2019-01-30T19:05:57.883Z","update_time":"$D2019-03-06T01:22:45.359Z","view_time":null,"first_public_time":"$D2019-01-30T22:46:52.106Z","has_unpublished_edits":null,"fork":false,"stars":20,"starred":false,"owner":{"type":"team","id":"d2fd23101beb2a61","login":"bryangingechen","name":"Bryan Gin-ge Chen","avatar_url":"https://avatars-next.observableusercontent.com/73f0dccc0b7fc5c845e6a52a58e01a2ae432cc529aaada0d10ab602137e603c0","tier":"starter_2024"},"version":223,"publish_version":223,"role":null,"authored":false,"authors":[{"type":"individual","id":"5c13a1a27cf52564","login":"bryangingechen","name":"Bryan Gin-ge Chen","avatar_url":"https://avatars-next.observableusercontent.com/73f0dccc0b7fc5c845e6a52a58e01a2ae432cc529aaada0d10ab602137e603c0","tier":null}],"members":[{"type":"individual","id":"5c13a1a27cf52564","login":"bryangingechen","name":"Bryan Gin-ge Chen","avatar_url":"https://avatars-next.observableusercontent.com/73f0dccc0b7fc5c845e6a52a58e01a2ae432cc529aaada0d10ab602137e603c0","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":5,"collection":{"id":"1bd9754ae5c8b895","slug":"morsels","title":"Morsels","owner":{"id":"d2fd23101beb2a61","login":"bryangingechen","name":"Bryan Gin-ge Chen"}},"type":"notebook","body":{"title":"Lattice reduction","cells":[{"id":0,"value":"md`# Lattice reduction`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":32,"value":"md`Lattice basis vectors (in pixels):
\n${lilDot('rgba(128,255,128,1)')} ${tex`\\vec{a}=(${pic.lattice.ax.toPrecision(4)},${pic.lattice.ay.toPrecision(4)})`},
\n${lilDot('rgba(128,128,255,1)')} ${tex`\\vec{b}=(${pic.lattice.bx.toPrecision(4)},${pic.lattice.by.toPrecision(4)})`}. \n\nDrag these two dots below to modify the basis vectors, or drag anywhere else to rotate / zoom. After releasing, the lattice basis is [reduced](https://en.wikipedia.org/wiki/Lattice_reduction), resulting in an equivalent, but shorter basis.\n\n*Algorithm used here taken from Chapter 17 of Steven Galbraith's book [\"Mathematics of Public Key Cryptography\"](https://www.math.auckland.ac.nz/~sgal018/crypto-book/crypto-book.html).*`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":28,"value":"{\n const div = html`

`;\n const resetButton = html`

${md`Sometimes the Voronoi cells show spurious lines. Sorry about that. See [this Delaunator issue](https://github.com/mapbox/delaunator/issues/43).`}

\n`);\n div.addEventListener('uncheck', () => {\n div.m.valueAsNumber = 15;\n div.n.valueAsNumber = 15;\n div.labelPoints.checked = true;\n div.dispatchEvent(new CustomEvent('input'));\n });\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":177,"value":"md`**See also:** I stole some tricks from Mike Bostock's [\"Regular plane tilings\"](/@mbostock/regular-plane-tilings/2) in the update of this notebook, namely, using [d3-interpolate](https://github.com/d3/d3-interpolate) to animate the \"randomize\", \"square\" and \"triangle\" buttons & adding random jitter to fix the Voronoi cells.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":69,"value":"md`## Appendix`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"height = 720","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"// Algorithm 23 in Chapter 17: Lattice Basis Reduction \n// from version 2.0 of the book “Mathematics of Public Key Cryptography”\n// by Steven Galbraith\n// https://www.math.auckland.ac.nz/~sgal018/crypto-book/crypto-book.html\nfunction reduceBasis(b1,b2) {\n // dot product\n function dp(u,v) {\n return u[0]*v[0] + u[1]*v[1];\n }\n let B1 = dp(b1,b1);\n let mu = Math.round(dp(b1,b2)/B1);\n b2[0] -= mu * b1[0];\n b2[1] -= mu * b1[1];\n let B2 = dp(b2,b2);\n while (B2 < B1) {\n [b1,b2] = [b2,b1];\n B1 = B2;\n mu = Math.round(dp(b1,b2)/B1);\n b2[0] -= mu * b1[0];\n b2[1] -= mu * b1[1];\n B2 = dp(b2,b2);\n }\n return [b1,b2];\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"function getParticles(m,n, {ax, ay, bx, by}) {\n const particles = [];\n for (let j = -m; j <= m; ++j) {\n const xj = j * ax;\n const yj = - j * ay;\n for (let i = -n; i <= n; ++i) {\n const p = [xj + i*bx + (1e-6*Math.random()), yj-i*by]; // jitter\n p.i = i;\n p.j = j;\n particles.push(p);\n }\n }\n return particles;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"function renderVoronoi(context, {particles}, {ax, ay, bx, by}, extra=1) {\n const w = extra*Math.max(Math.abs(ax), Math.abs(bx));\n const h = extra*Math.max(Math.abs(ay), Math.abs(by));\n const delaunay = new d3.Delaunay.from(particles.filter(\n d=> d[0] >-width/2-w && d[0] < width/2+w && \n d[1] >-height/2-h && d[1] < height/2+h));\n const voronoi = delaunay.voronoi([-width/2, -height/2, width/2, height/2]);\n context.save();\n context.translate(width / 2, height / 2);\n context.strokeStyle = 'rgba(0,128,128,1)'\n context.lineWidth = '2';\n context.beginPath();\n voronoi.render(context);\n context.stroke();\n context.restore();\n return voronoi;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"function renderLattice(context, {particles}, style=null) {\n context.save();\n const w = width;\n const h = height;\n context.translate(w / 2, h / 2);\n const pp = particles.filter(([x,y]) => x+3 > -w/2 && x-3 < w/2 && y+3 > -h/2 && y-3 < h/2);\n for (const p of pp) {\n context.beginPath();\n context.arc(p[0], p[1], 3, 0, 2 * Math.PI);\n context.fillStyle = style ||\n \"rgba(0,150,0,1)\";\n context.fill();\n }\n context.restore();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"function renderTextLattice(context, {particles}, {shift,text,textFunc,font,fontSize,fillStyle}) {\n context.save();\n const w = width;\n const h = height;\n context.translate(w / 2, h / 2);\n context.font = font || `${fontSize || 25}px serif`;\n context.fillStyle = fillStyle || 'white';\n shift = shift || ((fontSize || 25)/ 2);\n const pp = particles.filter(([x,y]) => x+shift > -w/2 && x-shift < w/2 && y+shift > -h/2 && y-shift < h/2);\n for (const p of pp) {\n context.fillText(text || textFunc(p), p[0]-shift, p[1]+shift);\n }\n context.restore();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":38,"value":"function lilDot(color, fill=true) {\n return ``\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"d3 = require(\"d3@5\", \"d3-delaunay@4\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":51,"value":"import {form} from \"@mbostock/form-input\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W36","stdlib":"1","titling":"auto"}} 33:"$32:body"