nov 2010

Bigint-libraries for Javascript

Having a leet second here.

Arithmetic on arbitrarily big natural numbers in Javascript is my current pet project (guess where this is going). Not a lot of people are doing it, because it tends to be slow. I've found four implementations floating around the Web so far:

• by David Shapiro: http://ohdave.com/rsa/
• by Leemon Baird: http://www.leemon.com/crypto/BigInt.html
• by Tom Wu, notably used by Google as one of their V8 benchmarks: http://www-cs-students.stanford.edu/~tjw/jsbn/
• by Masanao Izumo: http://www.onicos.com/staff/iz/amuse/javascript/expert/BigInt.txt

A bunch of nice pointers for possible optimizations can be found in a post on StackOverflow by someone apparently looking to implement something Diffie-Hellmanish:

• http://stackoverflow.com/questions/1450608/fastest-modular-exponentiation-in-javascript

Specifically:

• Hasenplaugh (gotta love the name) et al. have a faster variant of Barret reduction. (Also: talk slides.)
• A run-down of performance characteristics of different reduction methods by Johnson et al.
• Microsoft Research combines Karatsuba and Montgomery on FPGAs

Unrelated but discovered along the way:

• The Stanford Javascript Crypto Library appears to have a nice implementation of AES and some friends: http://bitwiseshiftleft.github.com/sjcl/