Ten Little Algorithms, Part 4: Topological Sort

Jason Sachs July 5, 20151 comment

Other articles in this series:

Today we’re going to take a break from my usual focus on signal processing or numerical algorithms, and focus on...

Ten Little Algorithms, Part 2: The Single-Pole Low-Pass Filter

Jason Sachs April 27, 201516 comments

Other articles in this series:

I’m writing this article in a room with a bunch of other people talking, and while sometimes I wish they would just SHUT UP, it would be...

Ten Little Algorithms, Part 1: Russian Peasant Multiplication

Jason Sachs March 21, 20156 comments

This blog needs some short posts to balance out the long ones, so I thought I’d cover some of the algorithms I’ve used over the years. Like the Euclidean algorithm and Extended Euclidean algorithm and Newton’s method — except those you should know already, and if not, you should be locked in a room until you do. Someday one of them may save your life. Well, you never know.

Other articles in this series:

  • Part 1:

Polynomial Inverse

Mike November 23, 20152 comments

One of the important steps of computing point addition over elliptic curves is a division of two polynomials.  When working in $GF(2^n)$ we don't have large enough powers to actually do a division, so we compute the inverse of the denominator and then multiply.  This is usually done using Euclid's method, but if squaring and multiplying are fast we can take advantage of these operations and compute the multiplicative inverse in just a few steps.

The first time I ran across this...

Linear Feedback Shift Registers for the Uninitiated, Part IX: Decimation, Trace Parity, and Cyclotomic Cosets

Jason Sachs December 3, 2017

Last time we looked at matrix methods and how they can be used to analyze two important aspects of LFSRs:

  • time shifts
  • state recovery from LFSR output

In both cases we were able to use a finite field or bitwise approach to arrive at the same result as a matrix-based approach. The matrix approach is more expensive in terms of execution time and memory storage, but in some cases is conceptually simpler.

This article will be covering some concepts that are useful for studying the...

Elliptic Curve Digital Signatures

Mike December 9, 2015

A digital signature is used to prove a message is connected to a specific sender.  The sender can not deny they sent that message once signed, and no one can modify the message and maintain the signature. The message itself is not necessarily secret. Certificates of authenticity, digital cash, and software distribution use digital signatures so recipients can verify they are getting what they paid for.

Since messages can be of any length and mathematical algorithms always use fixed...

Polynomial Math

Mike November 3, 20152 comments

Elliptic Curve Cryptography is used as a public key infrastructure to secure credit cards, phones and communications links. All these devices use either FPGA's or embedded microprocessors to compute the algorithms that make the mathematics work. While the math is not hard, it can be confusing the first time you see it.  This blog is an introduction to the operations of squaring and computing an inverse over a finite field which are used in computing Elliptic Curve arithmetic. ...