The avatar for @bryangingechen
Bryan Gin-ge Chen
here to learn
Published
Morsels
Edited
Mar 6, 2019
20 stars
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
// Algorithm 23 in Chapter 17: Lattice Basis Reduction
// from version 2.0 of the book “Mathematics of Public Key Cryptography”
// by Steven Galbraith
// https://www.math.auckland.ac.nz/~sgal018/crypto-book/crypto-book.html
function reduceBasis(b1,b2) {
// dot product
function dp(u,v) {
return u[0]*v[0] + u[1]*v[1];
}
let B1 = dp(b1,b1);
let mu = Math.round(dp(b1,b2)/B1);
b2[0] -= mu * b1[0];
b2[1] -= mu * b1[1];
let B2 = dp(b2,b2);
while (B2 < B1) {
[b1,b2] = [b2,b1];
B1 = B2;
mu = Math.round(dp(b1,b2)/B1);
b2[0] -= mu * b1[0];
b2[1] -= mu * b1[1];
B2 = dp(b2,b2);
}
return [b1,b2];
}
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell

Purpose-built for displays of data

Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
Learn more