Nathan Karst
  • Home
  • Teaching
  • Research

Great article on low energy transfers

5/21/2014

0 Comments

 
I found this great article on Digg about moving objects over large distances in space with relatively tiny amounts of energy. I do wish, though, that the article had compared these null cline trajectories with old school gravity assists. Even still, it's a super cool intersection of nonlinear dynamics, engineering, and physics. 
0 Comments

Powers modulo n in Matlab

3/8/2014

1 Comment

 
Many modern cryptographic techniques rely on modular powers. In order for these schemes to be secure, the base, exponents, and modulus are often quite large. I'm currently using Matlab in the cryptography course I'm teaching, and double precision overflow was immediately a problem for even relatively small examples. I've coded up an implementation of the left-to-right binary method that allows us to do so more realistic examples: 
function rem = powMod(base,exponent,modulo)
% POWMOD(BASE,EXPONENT,MODULO) computes BASE^EXPONENT mod MODULO using the
% right-to-left binary method.
if (modulo^2 > bitmax)
    error('Modulos is too large!')
end

rem     = 1;
base    = mod(base,modulo);
e   = fliplr(str2num(dec2bin(exponent)')'); % this is the best/worst line ever; lsb in e(1).
n   = length(e);
for i = 1:n
    if e(i) == 1
        rem = mod(rem*base,modulo);
    end
    base = mod(base^2,modulo);
end
The method itself is really neat. I think it would make a great project for an undergraduate with a little prior coding experience. 

Notice that even here we could have double precision overflow if the square of the modulus is too large. I've been thinking about either implementing a variable precision method, or switching out of Matlab entirely the next time I run the course. I think a natural alternative would be Python. If anyone has any thoughts, feel free to post or email. 
1 Comment

Research update: blood flow

2/19/2014

0 Comments

 
John, Brian, and I recently had a piece of work examining oscillations in simple fluid networks accepted to SIAM Journal on Applied Dynamical Systems. I presented a short version of the work at the Joint Mathematics Meeting this January, and it's looking like I'll give a longer version aimed at undergraduates at Wellesley's mathematics colloquium in April. I'm particularly excited about this last one, because there's so much cool stuff in the project that you can think of as an extension or modification of classic undergraduate topics. Should be fun!
0 Comments

Modular multiplicative inverses in Matlab

1/30/2014

4 Comments

 
I'm teaching a introductory cryptography and coding theory course this semester in which we're using Matlab to implement a bunch of different cryptosystems. I was a little surprised to see that Matlab doesn't have a built-in function (that I could find, at least) that computes in the inverse of $x$ modulo $n$ if it exists.

There's actually a fairly pretty solution. Bezout's identity tells us that for any integers $x$ and $y$ not both zero, there exist integers $a$ and $b$ such that a linear combination gives the greatest common divisor of $x$ and $y$. $$ax + by = gcd(x,y).$$ Matlab actually gives us hooks to compute $a$ and $b$ in it's gcd function: 
>> help gcd
 GCD    Greatest common divisor.
    G = GCD(A,B) is the greatest common divisor of corresponding elements
    of A and B.  The arrays A and B must contain integer values and must be
    the same size (or either can be scalar). GCD(0,0) is 0 by convention;
    all other GCDs are positive integers.
 
    [G,C,D] = GCD(A,B) also returns C and D so that G = A.*C + B.*D.
    These are useful for solving Diophantine equations and computing
    Hermite transformations.
So suppose we want the multiplicative inverse of $x$ modulo $n$. We know (or could show from first principles with relatively little work) that $x$ has a multiplicative inverse modulo $n$ if and only if $gcd(x,n) = 1$. So Bezout's identity tells us that there exist integers $a$ and $b$  such that $$ax + bn = 1.$$ Since $bn \equiv 0 \bmod n$, we're left with $ax \equiv 1$, which shows that $x^{-1} \equiv a \bmod n$. 

Here's my implementation in Matlab:
function xInv = modInv(x,n)
% ModInv(x,n) computes the multiplicative inverse of x modulo n if one
% exists; errors if no such inverse exists
if gcd(x,n) ~= 1
    error('x has no inverse modulo n')
end

[d, a, b]   = gcd(x,n);
xInv        = mod(a,n);
end
4 Comments

Major progress on Steiner systems

1/17/2014

0 Comments

 
As reported by Gil Kalai, some major progress has been made on Steiner systems. The question is: can you find a collection of subsets , each with size $k$, drawn from an ambient set of size $n$, such that each each subset of size $r \leq k$ appears in exactly $\lambda$ subsets in the collection? These designs have a special place in my heart; my thesis work centered on applying them to dynamic rekeying in smart grid systems.

This is problem has been more or less completely open for over 150 years. There have been some good results for $r =2$ and sporadic constructions for $r \geq 3$. Evidently Peter Keevash has cracked the problem wide open by solving the case of general $q$ and $r$. I'm not sure that anyone saw this sort of generalized construction coming. What's more, it seems that there is a new probabilistic construction technique at the heart of the proof. Incredible!
0 Comments

Cuz, ... science!

1/15/2014

0 Comments

 
Young people doing science is awesome. That is all. 
0 Comments

Gompentz law

1/10/2014

0 Comments

 
I found a quick and interesting article on /r/math this morning about the Gompentz law of human mortality. The basic idea is that the probability that you will die in a given year doubles roughly every 8 years. This could turn into a grisly but interesting exam question in my first-year applied mathematical methods class. 
0 Comments

Polynesians and base 2

12/17/2013

0 Comments

 
I just saw an interesting article on /r/math detailing how Polynesians had invented binary notation 600 years ago. I love when these fundamental concepts are rediscovered over and over. I've been reading a lot of Iain Banks' science fiction lately, and one great passage of his says something along the lines of "one of the few things that all sufficiently developed species can agree upon is that integers should be represented in base 2." It wouldn't even require so much conversion: a week becomes 8 days, a month 32 days, a "thousand" becomes 1024, and so on. Somehow I don't think this is going to get much popular support...
0 Comments

Great article on the recent twin prime progress

12/1/2013

1 Comment

 
I read a great article in Quanta about the recent flurry of progress on the twin prime conjecture. I'm not a number theorist, and the article did a good job of relating the big ideas at a high level for a wide mathematical audience. I absolutely love that Polymath8, and now Polymath8b, have had so much to contribute. It'll be interesting to see how far the current approach can bring down the bound. 
1 Comment

Antoni Gaudi and mathematics

10/18/2013

0 Comments

 
It's been forever since my last post! It's been a busy semester so far, with a new curriculum rollout and some good research stuff going on. I wanted to take a quick moment and plug an awesome project that Shivani Janani, an honors program student I'm co-advising with Danielle Krcmar, will be working on next semester and ask for any resources that someone might know of. 


Read More
0 Comments
<<Previous
Forward>>

    Archives

    June 2015
    May 2015
    February 2015
    December 2014
    October 2014
    September 2014
    August 2014
    July 2014
    May 2014
    March 2014
    February 2014
    January 2014
    December 2013
    October 2013
    July 2013
    June 2013
    May 2013
    April 2013
    March 2013
    February 2013
    January 2013

    Nathan Karst

    Doing and teaching mathematics. 

    Categories

    All

    RSS Feed

Powered by Create your own unique website with customizable templates.
Photo from ByoLogyc