Superconductor

The group law on a hyperbola

And as described in the previous post, it's possible to define a group law for points on a circle and it's easy to generalize the geometric interpretation of this operation to points on other conics. Here's an example - of what adding the points (5/4,3/4) and (-5/4,-3/4) to get the point (-17/8,-15/8) on the hyperbola x² -y² = 1 looks like, using the point O = (1,0) as the additive identity, where we find the slope of the line through the two points we want to add, find the second point where the line through O with that slope intersects the curve and call that point the sum:

The group law on a parabola

As described in the previous post, it's possible to define a group law for points on a circle and it's easy to generalize the geometric interpretation of this operation to points on other conics. Here's an example - of what adding the points (-1,0) and (2,3) to get the point (1,0) on the parabola y = x² -1 looks like, using the point O = (0,1) as the additive identity:

(I used this particular curve instead of the simpler y = x² because the simpler curve is singular because of the repeated root at x = 0 and I wanted to avoid worrying about that.)

Tomorrow: the same thing for points on a hyperbola.

The group law on a circle

It's fairly well known that you can define way to add points on an elliptic curve - defining a so-called "group law" for the points. It turns out that it's not too hard to do the same thing for a circle. This shouldn't be too surprising: an elliptic curve is roughly the product of two circles, so we should expect the same structure on just a single circle. And as I previously mentioned, all quadratics are really just circles if we define our coordinates correctly, so we should even expect this idea to work on other conics than circles.

With a circle, it's easy to find an appropriate group law: given points P = e^ia and Q = e^ib, just define P + Q = e^i(a+b). That corresponds to adding the angles to the points. But if we think a bit more about what this means geometrically, it's easy to apply the same idea to adding points on parabolas or hyperbolas. 

The slope of the line through P and Q is just

m = (cos b - cos a) / (sin b - sin a)

Now let's draw a line through (1,0) with a slope of m. This line is given by

y = m (x -1)

Substituting that into the equation of the circle

x² + y² = 1

we find that

x² + m²(x - 1)² = 1

or

(1 + m²) x² - 2 m² x + m² = 0

One solution to this is obvious: x = 1.

Once we see that, we can factor out (x - 1) to get the other root: x = (m² - 1) / (m² + 1).

And if we then substitute the definition of m in terms of a and b and simplify things a bit we find that this other root  actually x = cos(a + b) so that the sum of the two points is (cos(a + b), sin(a + b)).

This leads to the following geometric way of thinking about the group law on a circle

1. Draw a line through the two points P and Q
2. Draw the line with the same slope that passes through the point (1,0)
3. Call the second point where that line intersects the circle the point P + Q.

And just like the point at infinity is the additive identity in an elliptic curve group, the point O = (1,0) is the additive identity in this case. (And just like with elliptic curves, there's nothing special about this point. Any other one would have worked just as well.)

What does this look like?

Here's a picture that shows what adding the points (3/5,4/5) and (-4/5,-3/5) to get (0,-1) looks like:

Tomorrow: a picture of what doing this with points on a parabola looks like.

The fundamental theorem of calculus

dF(x) / dx ≈ ΔF(x) / Δx

= (f(x) Δx) / Δx

= f(x)

Obvious, isn't it?

Too Random

I was playing cards (a variant of Gin Rummy) with some people recently. When it was my turn to shuffle, I would try to do a very good job of it. I wanted the cards to be well-randomized.

We all noticed that when I shuffled, it took longer for someone to win the round. We assumed that the more random the cards, the harder it would be to get triplets or straights. You see, after a round, when we collected the cards, they were bunched together (people had laid down triplets and straights, the cards in their hands were collected in partial groups). Before the shuffle, they were not random. So a quick shuffle meant, obviously, that there was less randomizing, the bunches tended to stay together just a bit more for the next round. A card in play was more likely to have a "partner" card in play nearby. And more likely to be only 2 or 3 cards away, which is what was needed for the same person to get both cards on the deal.

OK, there's nothing radical about this analysis. But what was interesting for me was that one of the players started asking me to shuffle less. She won more with fewer shuffles. My guess is that there are two overall strategies, play as if the deck is random and play as if it is not. She had learned (maybe subconsciously) how to play with a strategy of non-random cards and this was successful whenever she played. However, that strategy did not work with more random cards.

Intersections of lines from adding points on an elliptic curve

I was playing with a graphing program this morning and tried graphing an elliptic curve and all of the lines that you'd use to add the points on the curve with integer coordinates using the cord-and-tanget method of addition. Here's what I got for the elliptic curve y² = x³ + 1.

There must be something interesting that you can state and prove about the intersections of those lines.

 

What is i^i?

What is iⁱ? That's easy enough to figure out. What's slightly more difficult to understand is why I get asked questions like this. Something about giving answers, I suppose.

In any event, for any complex numbers a and b we have that

a^b = e^{b log a}

And for any complex z we have that

log z = ln |z| + i arg z

So that

log i = ln 1 + i (π/2 + 2nπ)

= i (π/2 + 2nπ)

So that we have that

iⁱ = e ^{i (i (π/2 + 2nπ))}

= e^–π/2 e^-2nπ

For the principle branch of the logarithm, this just reduces to

iⁱ = e^–π/2 ≈ 0.20788

but even in the cases where n ≠ 0 we still always have that iⁱ is a real number. In fact, if we plot the values of iⁱ for -2 ≤ n ≤ 2, here's what we get.

So in addition to having the principle value of e^–π/2, we can also make iⁱ either as big as we want to (by taking n<<0) or as close to 0 as we want (by taking n>>0), but in any case, it's still always a real number.

Approximating a circle with a polygon

A circle is the limiting case of a polygon with lots of sides, so a reasonable question to ask (like I was recently asked) is exactly how many sides a polygon has to have for its area to be a good approximation to the area of a circle. Here's my answer to this question.

Suppose that we have a regular polygon with n sides and that the distance from the center of the polygon to any of its vertices is r. If we look at the wedge formed by drawing lines from the edges of a single side of the polygon to the center, we get something that looks like this, where the angle in the center of the wedge is 2π/n.

 

If we divide this wedge into two right triangles, we can then use some trigonometry to find the lengths of the sides of each of the triangles in terms of the length r and the angle 2π/n. This gives us something like this:

 

This means that the area of each of the wedges is

(r cos π/n) (r sin π/n)

= r² cos π/n sin π/n

= (r²/2) sin(2π/n)

and the area of the entire polygon is

A = n (r²/2) sin(2π/n) = πr² (n/2π) sin(2π/n)

Now what happens we increase the number of sides of the polygon?

As n gets big, 2π/n gets close to 0 so that

(n/2π) sin(2π/n) = sin(2π/n) / (2π/n)

gets close to 1, so we have that A gets close to πr², just like we expected.

Now the area of the circle with radius r is πr², so the difference between the area of the circle and the area of the polygon is

πr² - πr² (n/2π) sin(2π/n)

= πr² (1 - (n/2π) sin(2π/n))

If we plot

f(n) = 1 - (n/2π) sin(2π/n)

we find that it looks like this:

 

so it’s clearly possible to get a good approximation with not too many sides.

We actually have that f(8) = 0.900316, so that using just 8 sides gives us less than 10 percent error. To get to 5 percent error it turns out that we need to use 12 sides and to get 1 percent error we need to use 26 sides. This means that it's probably reasonable to say that a 26-sided polygon (icosikaihexagon?) is a good approximation to a circle. Here's a 26-gon that I drew using Google Sketchup that seems to show that a 26-gon is fairly circle-like:

Polygons with fewer sides might also be OK, depending on exactly how good you want your approximation of a circle to be.

Smooth curves over finite fields

Once you’ve generalized the idea of the tangent space of a curve in a way that's useful for curves over finite fields, it’s easy to use that idea to generalize the idea of a smooth curve. In particular, we say that a curve is smooth at a point if the dimension of the tangent space (like described in the previous post) at the point is the same as the dimension of the curve itself. And because this definition also works for curves defined over a finite field, we can talk about such curves as being "smooth," in a meaningful way.

Here are some examples of why this definition makes sense. Note that even though the pictures show graphs of real-valued function, this also makes sense for curves defined over finite fields.

Example 1

Suppose we have the curve defined by

y² = x³ + 1

At the point (2,1), the tangent space is just the line

y = 0

Here's what this looks like:

Since the dimension of the tangent space (1) is equal to the dimension of the curve (1) at the point (0,0), the curve is smooth at that point.

Example 2

Suppose that we have the curve defined by

y² = x³

At the point (0,0) we have that the line

y = ax

intersects this curve. On this line we have that

y² = a²x²

Setting the two expressions for y² equal to each other to get the intersection of the line and the curve we get that

x³ = a²x²

or

x³ - a²x² = 0

or

x²(x – a²) = 0

This means that the intersection of this line and the curve has multiplicity greater than 1, so that any line of the form

y = ax

is tangent to the curve like shown in this picture:

This means that the tangent space at the point (0,0) has dimension 2 while the curve only has dimension 1, so the curve isn’t smooth at (0,0).

Example 3

Suppose that we have the curve

y² = x³ + x²

Just like in the previous example, at the point (0,0) the line

y = ax

intersects the curve and where this line intersects the curve we have that

x³ + x² = a²x²

or

x³ + (1 – a²)x² = 0

or

x² (x + (1 – a²)) = 0

This means that the intersection of this line and the curve has multiplicity greater than 1, so that any line of the form

y = ax

is tangent to the curve like shown in this picture:

This means that the tangent space at the point (0,0) has dimension 2 while the curve only has dimension 1, so the curve isn’t smooth at (0,0).

Why projective conics look like circles

In the previous posts that showed graphs of projective versions of a parabola and a hyperbola, it certainly looked like both of these really turned out to be circles in the projective plane. I've been asked about this a few times, so here's my explanation of why this is the case.

First, note that a circle looks like

x² + y² = 1

or

x² + y² = z²

In the case of the parabola defined by

y = x²

or

yz = x²

we can write

X = -ix

Y = (y + z) / 2

Z = (y – z) / 2

or

x = iX

y = Y + Z

z = Y – Z

to find that from

yz = x²

we have that

(Y + Z)(Y – Z) = (iX)²

or

Y² – Z² = -X²

or

X² + Y² = Z²

which is clearly a circle.

For the hyperbola defined by

xy = 1

or

xy = z²

we can do a similar change of variable, writing

x = X + Y

y = X – Y

z = iZ

to change

xy = z²

into

X² + Z² = Y²

which is also a circle.

It's even possible to generalize this to any conic. This means that it actually makes sense to say something vague like "with a suitable selection of coordinates" any complex projective conic can be written in the form

X² + Z² = Y²

so they're really all just circles in the projective plane.

Tangent lines for curves over a finite field

This morning I was talking to one of our core crypto team when one of our engineers walked by. When he heard what we were talking about he said something like, “Wait a minute, how can you talk about things like derivatives and smooth curves when you’re dealing with curves over a finite field? Don’t you need some sort of continuous function to talk about things like that?” This led to a discussion of tangent spaces for arbitrary curves.

Here’s roughly what we talked about.

If you have a curve which has points whose coordinates come from an arbitrary field, and you want a definition of a tangent to the curve that makes sense, one way to do it is to generalize what we have for the continuous case.

Here’s a picture of the tangent to the curve y = x² at the point (1,1). It’s the line

y = 2x – 1

At the point (1,1) if we set the two expressions for y equal to each other we get that

x² = 2x – 1

or

x² – 2x – 1 = 0

which we can write as

(x – 1)² = 0

In we look at the tangent to the curve y = x³ at the point (1,1) we get that it’s the line

y = 3x – 2

And if we set these two expressions for y equal to each other we get that

x³ = 3x – 2

or

x³ – 3x + 2 = 0

which we can write as

(x – 1)²(x + 2) = 0

In both cases we have a repeated root where the tangent line intersects the curve.

In the general case we say that a line is tangent to a curve at a point if the multiplicity of the intersection of the line and the curve at the point is greater than 1. And that definition even makes sense for cases where we don’t have anything close to the continuity that we have in the case of functions of a real variable. Like we have with finite fields.

And once you have the idea of a generalized tangent line, getting a generalized tangent space is easy: it's just the set of all tangent lines.

Coming next year - algebraic geometry in 500 words or less

For some reason I almost always get asked hard questions. That's probably because people can figure out the easy things by themselves. But I was particularly surprised by a question that one of our engineers recently asked me.

"What's the difference between a variety and a scheme?" he said.

"Ah," I said. "I'm not sure that there's an easy answer to that question, but let me try."

I'm not sure if what I said made sense, but I'm going to try to fit the high points of it into a single blog post that's not too long. So with any luck, the post "Algebraic geometry in 500 words or less" will be appearing here in January. And it might even be 500 words or less.

The discriminant of a singular elliptic curve

An elliptic curve defined by

y² = x³ + ax + b

has discriminant

D = 4 a³ + 27 b²

and is singular when D = 0.

When this happens we have that

b² = (-4/27) a³

If we think of that as a polynomial in a and b, that’s another singular elliptic curve, isn’t it? Now it's in a and b instead of in x and y.

I'll have to think about that for a while. It may or may not actually be interesting.

Why df/dz*=0 for analytic functions

After my recent post about quaternions, I was asked why we can characterize an analytic function of a complex variable by ∂f/∂z* = 0. Here's why this is true.

Let's write 

f(z) = f(x + i y) = u(x, y) + i v(x, y)

so that we have

z* = x – i y

x = (z + z*) / 2

y = -i (z – z*) / 2

Now

∂f/∂z* = (∂f/∂x) (∂x/∂z*) + (∂f/∂y) (∂y/∂z*)

= (∂u/∂x + i ∂v/∂x) (1/2) + (∂u/∂y + i ∂v/∂y) (i/2)

= (∂u/∂x - ∂v/∂y) (1/2) + (∂v/∂x – ∂u/∂y) (i/2)

But the Cauchy-Riemann equations tell us that we have

∂u/∂x = ∂v/∂y

and

∂u/∂y = -∂v/∂x

so that just leaves us with

∂f/∂z* = (0)(1/2) + (0)(i/2) = 0

An unbounded continuous pdf

In a discussion of probability today, the topic of unbounded pdfs came up. Many people hadn't seen an example of one. One such example is f(x) = 1 / (2 √x) for 0< x ≤ 1 and 0 otherwise. It's unbounded, but we have that ∫f(x)dx = 1. Here's what it looks like.

 
 

 

Unbiased estimators aren't always good

When people take their first class is statistics they usually learn to calculate the sample variance as

s² = Σ_i=1:n (x_i – m)² / (n - 1)

where m is the sample mean because the Unicode character for x-bar doesn't display well in most browsers.

This often seems counter-intuitive to the students, and the teachers usually explain that this expression is used instead of the more intuitive

s² = Σ_i=1:n (x_i – m)² / n

because the version in which you divide by n - 1 is an unbiased estimator, or that it's expected value is the variance of the distribution that's being sampled.

This leaves people with the impression that unbiased estimators are better in some way than biased estimators are, but that's not always the case. Here's the standard example of an unbiased estimator that's not as good as a biased estimator.

Suppose that we have a Poission distribution with mean λ, so that

p(x = n) = λⁿ e^-λ / n!

and that we want to estimate the statistic W = e^-3λ based on a single sample of the distribution. It's easy to see that (-2)^x is an unbiased estimator for W because

E(W) = Σ _x=0:∞ (-2)^x λ^x e^-λ / x!

= e^-λ Σ _x=0:∞ (-2λ)^x e^-λ / x!

= e^-λ e^-2λ

= e^-3λ

But this statistic isn't a very good estimator for W in some ways. In particular, it's actually negative when x is odd while the underlying distribution is always positive.

An estimator that makes more sense is max{W,0}, which happens to be a biased estimator. That's always at least as good estimate for the true value that we're trying to estimate and is actually never worse. So just because an estimator is unbiased doesn't necessarily mean that it's good. it just means that its expected value is whatever it's trying to estimate.

Visualizing the twisted cubic

The twisted cubic is a common example that's used in algebraic and differential geometry, but it can be hard to visualize. In particular, the twisted cubic can be parametrized as:

x(t) = t

y(t) = t²

z(t) = t³

What does this look like?

To find out, I used the graphing program on my son's iPad. This actually seemed to give more useful pictures than I got with other software that I have access to. Here's what this looked like, where we get the twisted cubic from the intersection of the curves

 y = x²

and

z = x³

 

 

 

That's not perfect, but it seems better than most pictures of the twisted cubic that I've seen in the past.

Isolated points on an elliptic curve

While watching the animation that I made of a family of elliptic curves I realized that it's possible for a curve of the form y² = x³ + ax + b to have an isolated point. An example of this is the curve

y² = x³ - 3x - 2

which looks roughly like this. There's an isolated point at (-1,0), even if it's hard to see in this picture.

 

But an isolated point is also either local maximum or minimum, so that the curve needs to be singular if it has an isolated point (its partial derivatives are zero at the isolated point). And because most people specifically define "elliptic curves" to only be non-singular curves, that probably explains why I've never come across any discussion of isolated points of elliptic curves. In this example, we have that

y² = x³ - 3x - 2 = (x + 1)²(x - 2)

so this curve is actually singular, just like it has to be.

Another animation of hyperelliptic curves

Here's what y² = x⁶ - 14 x⁴ + 49 x² - 36 + t looks like for -20 ≤ t ≤ 80. Just like the last post, this animated GIF is fairly big, so you need to click on the image below to view it.

 

An animation of hyperelliptic curves

It was so much fun animating a family of elliptic curves that I decided to do the same thing for hyperelliptic curves. Here's an animated GIF of y² = x⁵ - 5 x³ - 4 x + t for -5 ≤ t ≤ 50. The actual animation is on a separate page because it's a fairly big image so you'll need to click on the image below to see it.

 

An animation of elliptic curves

I thought it would be interesting to see what it wold look like if I created an animated GIF from graphs of elliptic curves as one of the coefficients in the Weierstrass form y² = x³ + ax + b changed.

Here's what I got with the curve y² = x³ - 2x + b for -4 ≤ b ≤ 8.

 
 

It's actually easy to create animations like these in Mathematica. In the older version (5.1) that I have, here's how you do it:

e = Table[ImplicitPlot[y^2 == x^3 - 2 x + t, {x, -4, 4}, PlotRange->{{-4,4}, {-4,4}}, AspectRatio->1], {t, -4, 8, 0.1}];

Export["C:\ec.gif", e, ConversionOptions->{"Loop"->True}]

It's even easier in the newer version, but I don't see a copy of Mathematica 8.0 as being in our budget any time soon.

Another graph of an elliptic curve

After playing with the graphing program on my son's iPad for a while, I tried using it to plot a few 3-dimensional graphs. The first thing that I tried was to look at the elliptic curve

y² = x³ - 2x +2

When you graph this curve it looks like this:

 
 

Another way to think of this curve is as the intersection of the surfaces defined by

z = y² - x³

and

z = 2x - 2

When I plotted those surfaces on the iPad, here's what I got (roughly looking down the y-axis):

 

Here's another point of view that shows a better view the intersection of the two surfaces (roughly looking down the x-axis):

 

And here's another point of view that's roughly looking down the z-axis:

 

I'm not sure that point of view really provides any useful insight into elliptic curves, but it seemed sort of interesting.

An unexpected trig identity

I was trying a graphing application on my son's iPad last night when I came across a trig identity that I hadn't seen before. Here's how this happened.

To test the graphing program on the iPad, the first few graphs that I made were of elliptic and hyperelliptic curves like this:

Then, for no apparent reason, I thought to graph

y = sin x + cos x

Here's what the graph looked like:

 
 

I found that a bit surprising. That sure looks like either a sine or cosine of some sort, so it looked like there was some sort of trig identity like

sin x + cos x = α sin(x + β)

that I hadn't seen before. When I tried to understand what's going on here, I thought that it would probably be just easy to find a slightly more general identity, something like

a sin x +  b cos x = c sin(x + d)

Such an identity is actually fairly easy to find.

We can write

c sin(x + d) = c sin x cos d + c cos d sin x

so that we have that

a sin x +  b cos x = c sin x cos d + c cos x sin d

Comparing that parts of the LHS and RHS that involve sin x and cos x, we find that we want

a sin x = c sin x cos d

and

b cos x = c cos x sin d

or that

cos d = a / c

and

sin d = b /c

Substuting those into

cos²d + sin²d = 1

we get that

(a / c)² + (b / c)² = 1

or that

a² + b² = c²

so that we have that

c = √(a² + b²)

Now that we have c, we can now find d as

d = sin^-1(b / c)

So in the case that I first came across I had a = b = 1, so that c = √2 and d = π / 4 giving

sin x + cos x =  √2 sin(x + π / 4)

which is exactly what we see in the graph.

I was a bit surprised that I hadn't seen that particular identity before. It doesn't appear in my CRC math tables book. Maybe it's one of the more obscure ones.

#voltagelive Voltage Customer Summit Video

Implications of fascinating ellipse trivia

In a previous post I mentioned how I had stumbled across some interesting properties of ellipses. One of them was the fact that if you square an ellipse that's centered at the origin you get another ellipse.

An alert reader pointed out an interesting implication of this, and that's the fact that you get elliptical orbits from either a force that's inverse to either the square of the distance between two objects or the distance itself.

There was even an article in the American Mathematical Monthly by Tristam Needham, "Newton and the Transmutation of Force," that described this. Newton was apparently quite surprised when he figured this out. Oddly enough, this was apparently one of the few times that Newton seemed surprised by anything.

Why they're called elliptic curves

 

Everyone who works with elliptic curves has probably heard that elliptic curves are called "elliptic curves" because they're connected to ellipses in some way, but not many people have actually taken the time to understand exactly what the connection really is. I just came across some notes that I made on this very topic several years ago and thought that the material might make a good blog post. It's tedious (perhaps even very tedious) stuff, but it's something that it's good to at least see once.

Let's see if I can write this up without introducing too many errors into it.

First, remember that elliptic curves in the Weierstrass form can be parameterized by the Weierstrass ℘-function. In particular, the ℘-function satisfies the differential equation

℘'(z)² = 4 ℘(z)³ - g₂ ℘(z) - g₃

and we have that

z - z₀ = _℘(z0)∫^℘(z) (4 w³ - g₂ w - g₃)^-1/2

so that the ℘-function is the inverse of a particular elliptic integral.

But why is that particular integral called an "elliptic integral?"

Suppose that we have an ellipse defined by

(x / a)² + (y / b)² = 1

which we can parameterize by

x(t) = a cos t

y(t) = b sin t

To get the length of this ellipse between t₁ and t₂ we need to calculate

_t1∫^t₂ ( (dx/dt)² + (dy/dt)² )^1/2 dt

The length of the entire ellipse is four times the length of just one quadrant of it, which we can find by calculating

L = 4 ₀∫^π/2 (a² cos²t + b² sin²t)^1/2 dt

Now

a² cos²t + b² sin²t = a² cos²t + a² sin²t – a² sin²t + b² sin²t

= a² (cos²t + sin²t) – (a² + b²) sin²t

= a² – (a² + b²) sin²t

= a² (1 – k² sin²t)

where

k = (a² – b²) / a²

Now let

cos t = (1 – u²)^-1/2

and

du = cos t dt

to get

L = 4 a ₀∫¹ (1 - k²u²) ((1 - u²) (1 - k²u²))^-1/2 du

= 4 a ₀∫¹ ((1 - u²) (1 - k²u²))^-1/2 du

- 4 a k² ₀∫¹ u² ((1 - u²) (1 - k²u²))^-1/2 du

So a reasonable first question to ask is how to evaluate the first of those two integrals, or how to find

∫ ((1 - u²) (1 - k²u²))^-1/2 du

To do this, let's write

v² = (1 - u²) (1 - k²u²) = (u - α) (u - β) (u - γ) (u - δ)

Dividing by (u - α)⁴ we get that

(v / (u - α)²)² = (1 + (α - β) / (u - α)) (1 + (α - γ) / (u - α)) (1 + (α - δ) / (u - α))

Changing variables to

x = 1 / (u – α)

y = v / (u – α)²

we get

y² = (1 + (α - β) x) (1 + (α - γ) x) (1 + (α - δ) x)

= x³ + A x² + B x + C

so that we find that we're interested in an integral that looks like

∫ (x³ + A x² + B x + C)^-1/2 dx

That's just one more change of variable (and if you've read this far it's one that I'm sure that you can easily figure out) away from being

∫ (4 x³ - g₂ x - g₃)^-1/2 dx

which is exactly the sort of integral that's the inverse of the Weierstrass ℘-function.

So there you have it - there really is a good reason for elliptic curves being called "elliptic curves." It's because they're connected to arc length integrals on an ellipse, and that's what the connection is.

Data-centric security for a data-centric world - #voltagelive 2011 in NYC

New innovation and emerging technology brings with it opportunities for streamlining costs, eliminating hurdles for end users and reducing risks to the business. However, implementing game changing solutions can be unique to your environment, policies and processes.

That's why I invite you to join Voltage Security at its first customer summit in New York City on November 9, 2011. The summit will focus on data-centric security and will feature top Voltage customers such as Amex, Wells Fargo, State Street and others, who will discuss how they implemented encryption projects for mail, data and payments. Also presenting will be Eric Ouellet, research vice president with Gartner Group, who is currently developing new analyses of how companies use encryption. The summit features customers talking to customers—at last count this includesAmerican Express, BJ's Wholesale Club, Citigroup, Deutsche Bank, Fidelity Investments, JPMorgan Chase, UBS, State Street Bank andWells Fargo. The goal of the summit is to enable Voltage customers to network with each other and pick up valuable best practices. If you're interested in attending, please visit www.voltage.com/live.

The theme is 'Data-centric Security for a Data-centric World,' it's an area of huge attention. Data is the lifeblood of industry, commerce and leisure, every business and every transaction. That's why protecting it is such a serious and difficult responsibility. 

Here's a quick scan of the Hot Topics we have on tap at Voltage Security Live 2011:

Cloud Data Security Data-centric Encryption Ecommerce Security

Email Encryption Mobile Data Security Payment Security

There's no question that every company continues to face a long serious of challenges related to these topics. The conference is designed to tackle specific issues and help formulate achievable solutions. The areas to be covered include:

• How to fund and integrate a data-centric strategy into your overall security program
• Best practices for data-centric encryption based on real-world implementation at a Fortune 50 Bank
• How to roll out encryption projects successfully across the organization and end-user community
• Successful phases for fast and non-disruptive implementation—what you need to do before during and after an implementation
• Elements of key management architecture and design
• The role of cloud and mobile data-centric security

Voltage Security Live 2011 will bring together the brightest minds in our field, all with considerable experience. There will be representatives from teams responsible for implementation, as well as enterprise and security architects looking for, and developing, best practices for data-centric encryption. 

The sessions will cover customer project case studies addressing issues such as how to maximize end-user adoption for your B2C implementations and implementing data-centric encryption projects, while the Customer Track focuses on panel discussions and presentations on topics such as protecting outsourced data, eDiscovery and Archiving and securing application emails. There's also an Architecture Track, featuring panel discussions and presentations on topics such as key management architecture, security policy, enterprise applications and the web services API and scalable design considerations. And there's the Security Panel, with a discussion and general Q&A featuring leaders from the security community—Gartner Security Analyst, Encryption Architects, QSAs. 

There's going to be a broad cross-section of security specialists attending, but some executives will find it particularly enlightening: CXOs and security leaders responsible for security strategy and programs; VPs/Directors responsible for security implementation; and architects responsible for security and application and enterprise architecture. If you have one of these roles, we think this conference is exactly right for you. 

We know there are constant demands on your time - we hope to see you there.

Register at www.voltage.com/live

Euler's theorem to the rescue

When I read cryptography papers I often get frustrated because what was obvious to the authors often isn't obvious to me. This means that I often spend lots of time trying to figure out exactly why it makes sense to go from one line of a calculation or proof to the next line. But I've come to the conclusion that more often than not, the reason that these things end up being true is because of Euler's theorem.

Euler's theorem says that if a and n are integers that are relatively prime then we have that

a^φ(n) ≡ 1 (mod n)

where φ is Euler's totient function.

It's fairly easy to see why this is true.

First, note that if a and n are relatively prime then we have that if we have the cancellation property, or that if we have

a b ≡ a c (mod n)

then we also have that

b = c (mod n)

This is true because if we have that

a b ≡ a c (mod n)

then

n | (a b – a c) = a (b - c)

If a and n are relatively prime then n ∤ a so we have to have that

n | (b – c)

or that

b ≡ c (mod n)

Now let

k₁, …, k_φ(n)

be φ(n) integers that are less than n and relatively prime to n. If a and n are relatively prime then the integers

k₁ a, k₂ a, ..., k_φ(n) a

are all different mod n because if we had

k_i a ≡ k_j a (mod n)

then we would have

k_i ≡ k_j (mod n)

by the cancellation property. 

Now because each k_i a is relatively prime to n and there are only φ(n) different positive integers relatively prime to n, the integers

k₁ a, k₂ a,…, k_φ(n) a

must be congruent to

k₁, k₂,…, k_φ(n)

If we multiply all of these congruences together we get that

k₁ a k₂ a … k_φ(n) a ≡ k₁ k₂… k_φ(n) (mod n)

or that

a^φ(n) k₁ k₂ … k_φ(n) ≡ k₁ k₂… k_φ(n) (mod n)

After using the cancellation property several times we're left with

a^φ(n) ≡ 1 (mod n)

just like we wanted.

Elliptic curves over GF(p^n)

When we implement pairing-based cryptography, we end up working in some extension GF(p^k) of GF(p). I get lots of questions about exactly what the difference is between these two cases, so here's a simple example of exactly what this looks like.

Suppose that we have the elliptic curve E: y² = x³ +1, which has embedding degree 2 over GF(p) when p ≡ 2 (mod 3). What does E(GF(11²)) look like compared to E(GF(11))?

Here are the points of E(GF(11)). Each of these points satisfies the equation y² = x³ +1. There are 11 finite ones plus O, for a total of 12 points.

(0,1)
(0,10)
(2,3)
(2,8)
(5,4)
(5,7)
(7,5)
(7,6)
(9,2)
(9,9)
(10,0)
O

It gets a bit complicated because a point in E(GF(11²)) looks like (x,y) = ((x₁,x₂),(y₁,y₂)), so that we have two coordinates, each of which has two different components. We usually combine the two components of each coordinate into a single complex number, so we think of ((x₁,x₂),(y₁,y₂)) as being (x₁+ix₂,y₁+ iy₂).

Here are the points of E(GF(11²)). Each of these points also satisfies the equation y² = x³ +1. The points of E(GF(11)) are still there, but we've also added quite a few more. There are 121 finite ones plus O, for a total of 122 points.

(0,1)

(0,10)

(1,3 i)

(1,8 i)

(1+3 i,1+6 i)

(1+3 i,10+5 i)

(1+4 i,1+8 i)

(1+4 i,10+3 i)

(1+7 i,1+3 i)

(1+7 i,10+8 i)

(1+8 i,1+5 i)

(1+8 i,10+6 i)

(2,3)

(2,8)

(2+10 i,5+5 i)

(2+10 i,6+6 i)

(2+4 i,5+3 i)

(2+4 i,6+8 i)

(2+7 i,5+8 i)

(2+7 i,6+3 i)

(2+i,5+6 i)

(2+i,6+5 i)

(3 i,4+9 i)

(3 i,7+2 i)

(3,4 i)

(3,7 i)

(3+10 i,2+2 i)

(3+10 i,9+9 i)

(3+2 i,3+i)

(3+2 i,8+10 i)

(3+3 i,4+7 i)

(3+3 i,7+4 i)

(3+8 i,4+4 i)

(3+8 i,7+7 i)

(3+9 i,3+10 i)

(3+9 i,8+i)

(3+i,2+9 i)

(3+i,9+2 i)

(4 i,2+6 i)

(4 i,9+5 i)

(4,10 i)

(4,i)

(4+10 i,4+3 i)

(4+10 i,7+8 i)

(4+3 i,1+i)

(4+3 i,10+10 i)

(4+4 i,1+2 i)

(4+4 i,10+9 i)

(4+7 i,1+9 i)

(4+7 i,10+2 i)

(4+8 i,1+10 i)

(4+8 i,10+i)

(4+i,4+8 i)

(4+i,7+3 i)

(5,4)

(5,7)

(5+10 i,2+i)

(5+10 i,9+10 i)

(5+3 i,3+6 i)

(5+3 i,8+5 i)

(5+4 i,3+8 i)

(5+4 i,8+3 i)

(5+7 i,3+3 i)

(5+7 i,8+8 i)

(5+8 i,3+5 i)

(5+8 i,8+6 i)

(5+i,2+10 i)

(5+i,9+i)

(6,5 i)

(6,6 i)

(6+2 i,3+4 i)

(6+2 i,8+7 i)

(6+3 i,1+7 i)

(6+3 i,10+4 i)

(6+4 i,4+6 i)

(6+4 i,7+5 i)

(6+5 i,4+10 i)

(6+5 i,7+i)

(6+6 i,4+i)

(6+6 i,7+10 i)

(6+7 i,4+5 i)

(6+7 i,7+6 i)

(6+8 i,1+4 i)

(6+8 i,10+7 i)

(6+9 i,3+7 i)

(6+9 i,8+4 i)

(7 i,2+5 i)

(7 i,9+6 i)

(7,5)

(7,6)

(7+2 i,5+4 i)

(7+2 i,6+7 i)

(7+5 i,3+2 i)

(7+5 i,8+9 i)

(7+6 i,3+9 i)

(7+6 i,8+2 i)

(7+9 i,5+7 i)

(7+9 i,6+4 i)

(8 i,4+2 i)

(8 i,7+9 i)

(8,2 i)

(8,9 i)

(8+3 i,5+10 i)

(8+3 i,6+i)

(8+8 i,5+i)

(8+8 i,6+10 i)

(9,2)

(9,9)

(10,0)

(10+10 i,5+9 i)

(10+10 i,6+2 i)

(10+2 i,2+3 i)

(10+2 i,9+8 i)

(10+4 i,2+4 i)

(10+4 i,9+7 i)

(10+7 i,2+7 i)

(10+7 i,9+4 i)

(10+9 i,2+8 i)

(10+9 i,9+3 i)

(10+i,5+2 i)

(10+i,6+9 i)

O

 

Telling the future with Cleverbot

It looks like we won't be using anything except elliptic curves or hyperelliptic curves for a while. At least that's what the almost-certainly-authoritative Cleverbot thinks will happen.

  

Probability is not the best the goal for undergraduate math education

I recently came across Arthur Benjamin's TED talk in which he claimed that math education needs a major change. He said that we need to refocus the goal of undergraduate education on probability and statistics instead of on calculus. I don’t agree with this, and here's why. Note that this doesn't mean that I think that probability and statistics isn't important. It just means that I disagree with the proposed change to math education.

Now it's certainly true that understanding some basic probability is an important part of a good education. Lots of the important policy decision that we make are based on data of some sort. It's easy for politicians and special interests to distort or misrepresent data (lie) to support their positions, and one way to be able to see through these distortions and misrepresentations (lies) is to understand how to interpret data, and that's what a basic understanding of probability gives you.

But to understand enough probability to see through the misrepresentations isn’t really that hard. It just takes the background of a one-semester class for which the prerequisite is nothing more than an understanding of basic algebra. That's probably not the sort of class that should be ultimate goal of an undergraduate education. It's really the sort of thing that should be taught in high school. That's where I first learned probability, and the class that I took probably provided all of the background that the average person needs to have.

Another reason that I disagree with this is that calculus is really the foundation for all engineering and science. It's also the foundation for probability. So if you want to understand pretty much anything technical at a non-trivial level, including probability, you really need to understand some calculus to do that. That's not true for probability. It's definitely important background to have, but it's not as fundamental as calculus. Calculus is the language used to describe all engineering and science. Probability isn't. And undergraduate calculus is also an important step on the way to other important tools.

Functions of a complex variable is a fascinating subject and is inherently interesting (at least to me) to learn about, and it's essentially just an extension of undergraduate calculus to functions of complex numbers instead of functions of real numbers. That's where elliptic curves come from, so there are definitely lots of practical applications of it.

Measure theory is also inherently interesting (same disclaimer here), and that's essentially what you get when you try to push the definitions of undergraduate calculus to their limits and a bit beyond. You then see how calculus can fall apart and find what it takes to fix it. And the most important application of measure theory actually seems to be probability. A statistic is a measurable function of a random variable, after all, and probability theory seems to be the most important example of where you actually need to worry about whether or not sets or functions are actually measurable.

So it seems to me that probability is important background that everyone should know, but it's also not the sort of material that should be the ultimate goal of undergraduate education. Calculus is a much better goal for that. It's both the language of science and engineering and the next step towards more advanced topics. Probability isn't.

(Although quantum mechanics involves some probability, it really seemed more like applied functional analysis than applied probability to me. And calculus may not be very helpful in understanding algebraic geometry, but then I'm not sure that anything's really very helpful for that. But then does anyone really understand algebraic geometry?)

Visualizing Bézout's theorem

Bézout's theorem says that two polynomials of degrees n and m intersect in nm points. But if we graph xy = 1 and y = x² it looks like they only intersect at the single point (1,1) instead of at four points.

 

To see all four points of intersection we need to look at the corresponding homogeneous curves xy = z² and yz = x². Here's what this looks like:

 

 

OMG! Category theory portal!

Holy cow! It looks like Wikipedia actually has enough entries about category theory to justify having a special category theory portal. For those fortunate enough to have avoided studying it, category theory is what mathematician Miles Reid once described as "surely one of the most sterile of all intellectual pursuits."

I realize that you can find pretty much anything on the Internet, but I can't quite believe that enough people care about category theory to justify its own portal on Wikipedia.

Ate pairing or ate pairing?

The ate pairing can be very useful for implementing pairing-based cryptography because it can be much faster that either the Tate or Weil pairing. It's what all of our shipping products are moving to for that very reason.

Note that the first letter of "ate" isn't capitalized while the first letters of "Tate" and "Weil" are. That's because the Tate pairing is named after John Tate and the Weil pairing is named after André Weil. The ate pairing isn't named after anyone, however, so the word "ate" isn't capitalized.

And that's a good thing. It turns out that if you capitalize it, you end up with the Greek goddess Ate. Here's how the Encyclopedia Mythica describes her:

The Greek personification of infatuation, the rash foolishness of blind impulse, usually caused by guilt and leading to retribution. The goddess of discord and mischief, she tempted man to do evil, and then lead him to ruin. She once even managed to entrap Zeus, but he hurled her down from the Olympus. Now she wanders the earth, as a kind of avenging spirit, but still working her mischief among mankind. Her sisters, the Litai, follow her and repair the damage she has wrought to mortals.

So never capitalize "ate." That may give you a pairing that you really don't want to use.

Another projective elliptic curve

Here's another visualization of a projective elliptic curve. This time it's the curve y² = x³ - (60/13) x² + (71/13) x. This particular curve is just one that I happened to have lying around that shows the "barbell" shape that you can get with some elliptic curves.

 

And as Forrest Gump might say, that's all I know about graphs of projective elliptic curves.

1001

After the gratuitous ASCII art for this blog's 1000th post, it's time to move on to number 1001. That's an interesting number because we can write it as

1001 = 7 x 11 x 13

The reason that I happen to know this is that I used 1001 to test a program that I wrote in high school that was supposed to find all the prime factors of an integer. Because 1001 *looks* prime, I used it to test the case where the input was actually a prime and was surprised to see something like this come out instead:

1001 is not prime

7

11

13

There's no real connection to cryptography of information security there at all, is there? Maybe there'll be some of that tomorrow.

World Record for finding the largest Non-trivial Gigantic Prime

 Posted by Terence Spies, CTO of Voltage Security:  

Just a quick note to congratulate one of our intrepid engineers, Tom Wu.  He's now a world record holder for finding the largest Non-trivial Gigantic Prime (which is also the largest "generalized repunit" prime.)  There's a large community of people competing to find really, really large primes using various mathematical techniques -- a competition that suits people that work on things like cryptography.  The primes that these folks are working with are even more gigantic than the primes that are used in cryptography.  In Tom's case, he got his record by proving that  (34120^11311-1)/34119 is prime (which is to say, it can't be evenly divided by any number but 1 and itself.)  How big is that number?  It's over 51,000 digits long.  If you want to check Tom's work, you are welcome to do some trial divisions on the number, which I've included below.  Just to get you started, I've verified that 2 and 5 don't work.

The last four digits are 6521 --  having word wrap issues with the number :)

2148113144331884020240740202538593736542798642541159883242933148518626062734696

7482251874816305000213886141475725482006177265158884624210764636520825941743374

0020655220012483597468525750693374008686770236185285560156433674204900545125358

8535626600953884925605871782665547527990639894731154430466901982685718729660486

4881369886141453004098981298912124269668420975657731805167769706658865564400487

2985048301786874040776399408593887318771648233738526328648257086879429582825753

5618052464284594947182552118866969637409623368759754058413544349424479429944238

1453366100204018476267730436220497916402494405788738528648736021078435253136151

7221171963014964372932655229548939162418946825005859899350224301930274634753020

0684494954828308831152192742278833971826220347054551466100595325861149025154876

3672199795312801583498409563729827948921032581308182964332339144176566665042149

6537476986749576942866749228558450645686991802785539256065294514437338404574296

0581331753921690498721832447164340888676652634002213991227881527449919104387357

7714112701020723693173437557360353486408207016861410061847705906827947328787099

0338587646357879171075768166706869979077383366132722341443467314751436477687326

8564320727999910848074754684093502669318849084214843691619574370967153540046164

3890040248522310477784199951373598788743549851799177851422951669850913577026632

7820776247256276324832854904768964216408291993892546368828111262651880527178492

4021471609879802918453502709224570818417375789564100533842372182327010737429302

9341677402308184080347222587930987514937877627473191227970699649139039394165726

0708385520691526113694936166004577577587114224437644076543936490785659381680141

5314277165257570973696286109859929694209323103262593801973661493029696184313897

5546093983815718627771060159699461773993711699051722659420789323215165168321628

0379610663704747481331009787998105998355988455151229732167683133905343230173260

5617068761973449453255106017837632886918193790195500113756840561556821567564844

5358359527969139956774404068939754551340847875237626391196005991239633640169576

2088320476292796243829829014042499596669808217003372152782129396290076673055685

6452733557890821404400870808625349053504209190097099116990783830306482148977057

0280224065596773811777869210042210847401271222070182068117602977590148539491228

4451319429831469022723515804952432670980977526596413589668913565483977974421666

7174734678177820726963610251276935412253869260133088544966591485080753611111001

4377471951016900302640125969316898630940161576777345391199434550942960896638971

0870484768518403596900938161019780588657271082778844823998204467180624324989472

7424420192457838263181659119047403732641695091450638991917135466056363340328975

8846397152835772968589118385280277442372426828842245397667969034235044482750272

5397103180516682859669954313525846361092620590787635141369496849623427305651094

0193640006617275290500922032553439908799972027428157522053460023990380732452904

7375097692009070816560425843881364842548899463026226603114587053702147128948491

0953954109860130287303937422540579234078371135834293368631752859878503376855040

2031465643811943173485054028093243916123479562705438024735962264847848507906629

8337452721700531869177195514935268723433083101419822250104822536439662115520634

1324153566030257061395725562639787753978764416251574410801376842835170296038166

6069517951668931899334188623751084964492633344850737150625248310189657737396964

6224365199270425061095651586786711752323344806649546571830785135844655544581851

9943584207838127622962304413211338939235014402029218119152027464410553087571535

9819509437383929400693822006993787283557395270865543089843265309082398968964910

4609897120068583286073543433387986427592490172970911980491147698394154333527971

0647137885608315574415563949234625618695411457357634968244288027311495818896405

7099543581303185435785494831411001523198973273933363760529547696865774759243387

2470137034383252526665218498934966513258487103890264921396303017730499110431555

7784578164256645248036805645498504810691105493123261898444260781144332383147727

0390860677712890318832473355818918903108275518278576398728080503296982698580209

0325493861271224628817678474066424469522292108166190961795660400693541183393732

2018771919593990208099122718700831116186802832791784784647287106532282338636933

6177371936516082323169983682860868309709483726038296022401110212900197683157490

6317967003390999043709396972917997382500962535677915362119357165770410445837442

7012246311969283737666209187585178607123107967345990874244114932034790391686369

6575845493506958188188799398586631064769035820397923640012422074554812074958650

7786549783342061339081669620788694009196009973335611774918351654244575349837388

5967531175110142755172490721273772079975257592575476591143555498009488198294136

0426246020837422162594831118973440195517576675496270644015096257924828894175919

9503175512404080078879168240584310357544642252280241570235498972457527696402423

2845009331733707733553401458342575248377620548689571186506143135603188310280351

3383600976595532774164205259990282685470623352229126949069782524524239995594035

9138531745199785543315508542916721300740703646298958592474356324366656916468064

1310527469342728171608904921878538542833387102944038740561316088932013626775413

4962643552639832526836903106282079505703127879363222897276551672405243897844670

4572255635890328027198080051503255081578867967160883868806065955044756142650096

1192632219815828990795201170373804965149526975804464328597606374128417263209284

8452818460407651502442461215891079363939692876214993744737571153021443464313764

0228123634084636032801936043649733646528148308540040894244006381588700863713297

4605156414149314697482321261139617081427156455501369186369293822894006675796264

6644873303929724487381169448010520606528527718100430290445698655379939105434853

8521393110096944750788726100733132939630983719158549375405459490933813261312242

5105172758256560393849304845781185748383436452834826184026690560461243094064592

1202564101811263829307932244791696540661731421804674558011579725584308277390346

8886436647443740946169115083638970730800676436320246617012033348500952726295560

3277571029168434594205521639310148100371766284538023895656250879482499803321445

8957399029132779068325694142796470328864354798306513041214205846123145789607268

0119131001959259207114176430960777073080439400091214671722046947284559720821596

9235778369956086652964828726007642186125913349646995958071084726390989327793489

2769490010872738710707040978675601351627979607449339019148643138914669842790910

5069671420172177667618671532010199084101351160872147750133393921975716674567637

2875351676005755516427557379868615511941551326940023030018327103767273759511694

9792879600205731487989868123007979581830135272743837373111868069688300900565954

3192204082808218380114328104365906680020083986420725741814865336674308370285236

7096020643636182685582919290727146075719331034135086743836254942816389873325136

3191562303902262036116660130903871611322405540622229470297813026841511221606249

7634724991367284079893338464380437520783928407700300631778700412491384111051230

1500407073629558033456078796650886303138616037033045149803502645366108846309445

9250132860973078634558163467860590401104140577059023058628769566097807011711022

2696478363371515138316994902474220623329984562097783141971316698645785644326170

6601908395479610073941108735222708024886451738779593887486585540333633259229887

2813495970453973807836568079951264466748827012856061718902361263108625026646630

1682103053724459537775358196018056505704126078609243356101248154612007665989799

7426286161488229795633815319438709904609470717825563572888251172714057633637366

1813802351445826623358872655012909705896001791161621086715937589626378889940253

3942529979367743908611190114653770971627733031428424457973968719204202125392287

8257972099565762354542266121255776039410642466889721489084395263697907839147572

9812730781792535159454619181391549058633601921369054903942431790638025358570386

8958387451596173547218395126698510716866646289839775950839846633032592257608990

2622911882511576074156443311850393700879656751683713093076379641609822731290315

7052069933674095873180478762968599743025056664813923197435913873844263682531817

7771956886680197293709034047521671323682206271430604917364101875697961905187716

2411503063617368755864752448934103587750209733203053375404317369184529426421374

1200109771024216714528647376905203456097683627155186581118175408517658430679457

0563435753230030641260589410622808320370528661793347330130807612040586770388578

1515460045647130438073157536702418281396469266861913940461052517148057590219901

3974504207422162540319444086683745403630618160858287323058430650568956932874917

2517955256151516516656576106984405371892212074034791998741291454436402004138023

4404984563849519817670300352509988849291016910426194411645965111395177756584094

5704951940961217290283545092574923239463890686203737339158768267004123786389540

1424056158835347716003170816485123421624251026827493878212978490891175207786431

3097605420952306321549316579499803890900635559957436984611341505638314443824201

7868054970745531599598790239798562304723737831635862859648003885078322193763194

6479760872189885715792501621743200607245653211726445067409419189628251446064124

7860508892861396135664819753143964861444591262662890974072572975989700036192059

0776281014520407799420734843630667360807968853856861884763512265203382843236722

8179747723979952835667221156317645517832241044679704158374673291021012042079496

9358839589636590448791405416026915975340840925159105124465656000752489677630267

0666189415687615252646020801504187853622979705478576214033100903269006494051036

8714743816078282114690988833396145603269479777367204381584445784968265203115459

5195291159466244420992789779516859598031747943208485741982640020822857016099208

0108970224167962726701775218638428609029776292817158517677424002195677300684332

9235019024901188924482953315260942158146069198964164326300800129273849500463083

0224226543512470375927753142484077398000339775220444585574016023694476661651278

6447273004109386930190166875491657127352872457301519983708153632531985822161687

8049936234005094888211179399062106935640792952435687549667767955241911996363085

9848086319141823841113910798453836788196178725546646985298442125223133948783712

4816542607023471028520778186894633367187959400024450112155823420057511217439181

1113496952102348891388756107507308468229186906200613572926093737873984855786572

2708111442705938786394328220617070697754902330809701383537942949048425730015392

2606114622222613450497580810040627866828403080124469641165160909422552720178880

1227959834295380992862272217074068890699937821433775023139723961916044361118849

5558371887188231447454384764548054334305855950441873655425336350838911688394640

3044476592750599370085419502659297508523289605767879381589071919426128689929655

2599032244115565101629745345036327443597655683643092402549260085145580000196965

7436991250136071766972998112848471957712562381631716978671643152430150631149649

0549209854448753978939775730752224181807678848533551024266555530949921046658530

5054169824682105662802534942886835704222893970559978110553868120279727876916227

2945472309482568037832186729433760594278223266020375840067702699433748759277800

6591494944448791840714807130757370694639362773479760039563677979488315945893648

0119693743208828816942433934426300444325010003190752155241714774994395575599769

5786450096716783976481037039600084863142245798508543444564800064265310480589478

2596634169303430864895915142853660571343645083631598112152666254070412535121894

0945332119271475559424835640320831603554808105235099059696202754320833523279645

7840710738780935471616634843666606767496577163573282019781407188965905422841844

2334524966955966397103297301946868193400085030440639511249871818471031527063989

0956622675632894153371442867573220239745419037761140988772041708136900146134527

7428053823581580745793303867242248596950949311334627489763508019196097536859355

5366434207983893549858418682721321627598492914293654554486841281782129129348048

2178547609514398745090731452939161399064034653829739286770095968353822811349124

4655865699559419588388126419868214491231737549906286010140620834000244477408987

8734676683664560288337681340594217136452569183428682722224092889736678587265433

1945451193821384587852280826589661383327709712749741674261082841572771785231145

4382816100599540467405304034976689963276068362205710072786367698599341491484975

9144779437646443298201708157103435011512225052686685937712060992916147400255564

5735205419793751417481487729167498960375248763720563131448849933207570390642197

7421839828571448187383754234200574804028669947666020675807748671343815114356001

3768289985154733264976729301970138207243226377211475686963762433517652853461566

0024381109240923294626500577418704639597156754566726105039269474665015269517416

2501936712737122663959693599766510102348164036278402432533756438165442727390401

1642592939267583031489411455165324817614514898640389835546695547324199111968497

8764953461644164750961640493747800322188216796927701831917951451485836978789208

3495885082932476613421074173926286679532445562815128994773671600394973613651483

6344133838818189940207757156030648321382078704650126655321739826249475555720983

2232556127380528683746399393777788054937258399588605327000827021908239855502536

3966760038582499179109017939990047289984288400166894806832304190617167740917664

1852145447439869719782802934987783493177365581304922065433900500723284026922392

6206067417559518486515860848712736477055822406621711995665858688462399557194526

3007500702419665204158832769627992141411521836841891883492878023271103719349417

8344421583832454113957661871087702069417239688911002192802045287263726544894629

1497661561398536923881521220902147652782884265569579556957967925186889874327649

4022637298044011877154403599467099645091404931239563076637638763213213742216554

9587207469430701273550768878348958246730037514648701255820302018834550751555985

6133989098393821346662003413158717245357630078452561312535850009659458990911145

9830997995249057222648726947775307552229226775700738517122782672614618153249330

9968648949490245586189441961187160123933096389706410734106710838222397859599170

1273122535910765612838276793143122147672058900964559544291956050638827125639169

3199881196822218904520586527018191564265069250269814940767061011753130771678824

9454859711111515511464132015224098140573007822536894262437731108820139735925640

3040686391996721087642604451460839899579170597240963668455700902387770890463675

4143828843558648744421793863462116078956102183468564618716376082122470939970994

4297404245986086613827938286672822193712293425080899751728785447288506914448267

4976923130035865523398870483981752037622238962661780834279217348377821764030780

8957406640803489401611276748845785633165451751937808530964258176260036492188523

3636879939377855691553066169754567311435819562588161714301195220410147645812962

2141783222075792110594580027190190364170638254442171385183189813236016521973378

7423596928543750504829639286763228394804223431692648522813275714024590207341686

8994446414502596182249154838808342521008765459409320863867269518914642491373302

8633422387361273929388080546018634398947097864847234963063296629987825916366581

8744620339578498502132977128620606660487057362769137751063459358661081739503650

6929545960871575873647036333559958714892711037742189293934108778184943813652805

5795080031974986663048641394734901784293379059383572295875224670393128370148246

0686291401148140851397199085732275694111615897799103981865118971096024051176175

5229057258594278141978100734058516282171994898182775607402254339186726887265403

9754633353490293507586111371621329542834985260541294610791097891576793929848354

9941717618176887402980851875272683589309763906307994188238001824379177552773117

4097363507658540667351715376361844114888280871001969330801856706899768693795570

5282789827379767514886577442164159518487116428184087184624015987350870407559551

7497621262427293912659114660192411129017019069121742242173424719916227439008461

5331290925552783124993248952049149749228864645985386187672709736641807677659064

9353094823879208294615638086319280867999868704801630443424460938280708092231875

3290435669790320554803123537221450528963399211864795680283303681777283883402108

6574891941288719299997132870121416210526546879270877038392860530173305410270354

8851479381768542921232941035282722164919070919888929008448335935333502170264442

0984113817216954281820948345686685307586160595091249420528871435522368772337458

9410603143263341253471750406529583405623764960405594631367703386810457441672852

1735885143636971101066684150142442320729033333538495638071116649970500177075423

0798794701927735362870690163851439200628142180141074251516107666911462586479695

7788061500138337405846360698731060365552589209442876808811744402256661026503969

2089942101050368295113676426172785920425259172694948530211931235221108257856333

1765127551609618385179924882244085404378889164374746644033934860374618640112301

3497580429378562423755236398872968926806300491342281641215955032748362881519861

6415812049088151645309142190216602307639102812965643764983156853218108744016531

5420523619106115209462924386803173447548706432648055976070779065820103711947502

8738146614186665422970642344824586221051140169890161848775994917201618777988112

2525811157773175439947037848285892815692135477473651640922514875305109160529159

9134483762724042466224965994299728700977727728276794625932431786019399763907431

2595992593845416207251556468205682297002800523375164402899678763769093408614113

9965537847287218173566296579459608927883599934935445765290562799427114013470698

5026394297611632611341157539578528514859113499472133801241999877137395706897551

8678451110268183289498319494513331689052008321295232276276853659856688809501846

2958000244882971719596028131551470712047357888835835309973393906135099417694817

2273600875119176498337855891033152338956329973312409112099646058780418788750864

8453845432673855409146574587275076787507251181013698202257290575998241050819452

3293054961327506171125331841321579756530397636246950888284450519416975127783425

9446713950905812813684666254538954574240477094887719011763001358350290002470210

1641999795058879399949962423359592709779584935130101457524438401430363988216186

5469825544060931661221311249034436664894896145510129120181421374032463170049917

3143747653424886026183295617371450043235838813979222148281114109175064628008965

2592299171634731563402776102946229273958278149811675106901928697296550845927339

4163540357877479553545720365471108449107069564616429249045841028543972775806611

9075433903230210879002470144260422591582712208071509410862958391020313654069096

7968971288035398037276960126235688981022740848631167302982570465700569179623403

1503672714388508142873981062076262625672778302352060778967740152924373311643951

6030291461202569790931220338619630527934384799532706482636285362100379259943298

9836066870983308408372811805913103758781828661190397030188094412622261610527975

0509405808049512527786711809203058870935633009806226870335111363682869855455160

6083467220988695791686309003957801298579047444776786949305509670393340546061694

0950464863510060840072274017506076874931863667936838154533074714681516963040358

5955144328141796181384285765041416996821743218845670430861814417258368303429055

8652639434771131579438369756443706622595738046083841100165400799893590982207035

3336838602584316731104434398519406622950632810474757371153218703878853187058138

9433064289599238386335703063615895244666361851081532993349768013589525682322063

1418851342739965331982649857171301009327631529576862021193535322737949674847987

9752038093973670626543870464145154114084441873744094495700299173341746219425103

3102796182460410018866885432649733243384065061656542359142829770239122699987143

6798287760725879473027290279381822443743412922239690683871336562029934806743992

7916681365625207889180882122362488960403830926111771978342780649477093127783429

5862414239167235230636538835103413088254717078461232474326635702356581390510965

8020495650269396369480086759359233395899542372831957124136624288483010676672366

9101274974710800170650439107027708027502523791200782525704543230116059637877789

3944489064322076363937260752421479067296019304126309423969850239840152458991237

7440010772907607411707052436979670204733196458688716071740105524362569543392181

0584472673363291472010553416989990832459073804973042733285876459652998345885394

3914956763334038110710058504175223686638471326453275704385485014065282284121309

4287064459622915064195955905725275847213070738329312496201518647613599611031191

3900036386278236983336963092411751433528723567807931283370554180167943163051807

4936673237067521091013750329810292793977802092248377833541972256078464621890087

2022481505204821273840220161835640981986073478614209906397436690878016460657452

6809391968845167910710826174193791560706600283284991332963579500815418337138368

9465420069175401185514037088689175474832705759773849356188884588528947196449650

2150428487733552971175062374838357964984597717759517491511269348395298355499345

7691264276838676313105724580371048468605088938159410597026932063687673403166421

0390226939550501450039575586992105047907654502869079677637762135439864572114651

2128158142015865726564829651238195970951009966944224852421233511178910975707355

0864180475348211326685669397735997463444897348247444394476799764750383876581880

8341910013977665571064092664094548114499182289681766831271250623096502232400451

3729570921614686741786736726946948072014666720136766199414191342299968472216331

6515833856446053358439068897611050719992678158596464788679297830726315721993281

8125317667341346781148632551393430224155807640355560319385141475777520204626610

9892232047602918218820779889287960816123959237833899945372249874865794806330704

1909013931019216624088683208632711313717761484323416287676235296212707417134556

0968293468510253620095046081125467919810827241862670375688910866198475360131619

1926351150938636485266471864013694718080940843337338509681403770440512275618015

3318757696998963183851540351295008160382347079319866243352079609240456531121777

4235805658604449769528496732586351317576192042073180855371926057168509183775071

2010269843855668804726973186652766521621388645728272038246799299497448567842507

5420804075012303591099577931873624082880455052272541634584670352299425171075771

1868061425011154287902563711933542835117970696882691505333653436783311037371224

8085712356565245392808662065082637044815107707963389398532365140720414747479885

6089167411573508746909300292330292459746226396343508952816998048522255092504232

0715898931611045976802195817051818325997182902576165768983551809705013734973324

1909301024331672165245492873576686703751351577276632137432940565739466439841933

36226351485850295389563216642694511034102398106695053965418379363686927298516155899330554516758722022522468240241533442048060732629578012508539642915727700565162981577933043944660114471061662315055564178786740809242905020879352157918806515781970662915885789638946906300498581957236354869371857719880909683488382609846101235486575073611198520117484367734617717414908520938018413174674404216165389463181802407410103187994797409146891717736112820846390306629254953165820978137025417773374959756228633246993047590075337912929546637745598347364545777939925464014326067645462637414191417359178753419236285455982161805277434230830583516471931330423904593693850141167684369176449095196353220738392120005708973699762309212744556739433650241922292542383390740476412593712561729299155457948342772434268103467543354301111734837238528240537023983491950507052672232648335406809995090122982204164041501499856545476368393156531285452886914158637814487719937972382000229518806538953102488075505664075567823189836871756276153247350167669408482568123284123893045982857471957265723397983096611441508361610332648742089592817875555326803158318648175435420610470301904888669364453680952547968065862314744773658083558979161543844648800016345313068553296246660126428782467347543333176808811986485623947140972232356888395727858210484301730894721532444517844319359527871281422942339258560494734002258824860641437106076487733292273309030710729821698182199818405958356966120613653785453049200272886438400329202273441924568730343236080548660601315707598141941049675297875972911115903553578049520128306548839406691789188751304072577631085319260236976893288924130435679886287124694538735384647173017698831423252766438393514780494226897034407781030925617778683940496275101316812000547567770394629554776200877370414763580991686580153526700879901811365863199447571491347719969109698560222483679860513161880564298900034745334325190828940128906306444348747702743710471719160223697310188290758572043554689957357902295105662998183306784899631902052349421698914285422327814631565718370777377484516459574363048142096732525494180800676565281190800545996591594916857133595699432564343197624023687506236503528646207418838663962300220421991992723382021550800705763638597860815373985270006729338027190912821360181527443475993355598232969550280295969175118439377189401003247310356167250747252883075650484896954222808444974693272308353019106892176023394389439301360523858692509776940700961033335992400758476503707515209338859169188532116028575654496730687226118859918256539210554362403009116833662194172776361261304541105794485842127722422737950550149966560849142155657680496736347990665010666991911765685498482266929213216249584878552333049748317301569972062220377118369513468436827661056949895264194360563171488335251082975250568393623139965829540668004824848743062015606277041138165062667320959861700299107608954969370012850836153230659927758130208555821449074925805197147725240742965793107004854572582753251962557971331967601602561088408125134437393479829024156436045116468557986358437911748145290432617790743777115072409115254271490709636257388397170371174053110176360407931356825327075673215182693984112574796881059798482735664210695269604066514975167051683025545865472485703879402067245230308663168421898545240580131471928472221495144796535055791115751043205483603224803589564220851117025073812218301805151358225769440855422268643456507824499154733318368511581898938308935223064688487156789070607010216479644478886091515893593862911169092977363345099182054728921651810060713394497865365181316563755598181917547144754604922857891944675541463420643909617563392284319426485071709398627656222742633602001547053324692684513006317652346726283842536718436534717650223034393932542927797102931039370440114186825953884917519933504266045300643945663213110993826776827888083584466722577338081802522321472072149272894418727963925587981728084820546921439203549203443347342466387042278862069872148237790546208871200961546508407869857090521572775432904327500149059178453343369772584850638587208217917687741246162032028184239603948674397081500796223097127525530406654346688790232551905845701524936374869317691908990594698194799279633583192381019505704582849165288729666878767643916649794829167185272148703608729053530557373074867058022271663557808898119933628867839311751100644187543909469734179939089325904204905039311193584689457245616514223368034969034697856934939281249273025313897455903475091530498549009826240386484824110552580812498308698090531278370306011201982277821464657748565532519239282381343342298694473269592958133756315386992363566919611394326442851978664885378009524704245190041598221133047281921075727937136305512944012146315037482764528767340149942507223863910983657836581675563263042679503934419881159424802296458484795905098841484255818739919796181681116110645425352636899383227708451754586882104077657638487737316068139043761567337709401093304484573666119521922762819624524763232474747379989573491594007984024569482911143990358789514026573112158873240158689068597296432377831116006469214846033010758294470978902214112541296358960660195527641244065851968716282795233111422220021644888377322091805368548948860456114289079477333921641893466827996821130090281952265682327514845872400627492478787217106405327934061340006298127038459872496918915506203840251187853946265528369824990903991367700225945566785208740293851110015030211294409772215880373804635710227293576068375010768099365145243005310331872372336097465813485216735183893403267810604564171145644160683682273737231752476473596014458874459984550269785677696797341920650796636002249110981634762040450821109582821023362202650146667561807650330214103318924677979172487705227873781833357673789858982499770753298968577752166039074244082247302346792357595163598399369888498208415856163401978965878671070445316446454707002635527096081399727188121297059967690147343812348095214023755208293187157859899147889061890236636772594200413602833481993585438131428180765202851630350919504906268799676095048507300576755660816436662333274651872502058089342427034272192999988876124118611033724106216075176410345732312286655353827981376579863667079192953537185261587535684242708499179796227833679089749772392564413891255021960360972912040845910374668412392878222119434282838069815720528020025103325913655028001348926854683342921195268315711609901920599847699140603950836024756607927328517839135166493151811820590734447142969905757276003415785584986820705388735563950186211068952434977822468113703414337947963977196285729967275519244358134908640962289963818442436146354171935680275538881687580465738410819136186117031532558299671655643874259799718525660259853660151549738704126833476912196854997304326214759636278109752704859271246383306135086109664283539023707374262177288982677498319010225735211561434590991905471430863009834869552156643162410895491132695886587804371491178765735693550247815573915500991738493663928264637826258213366785365026463463839500537437134933675280562488878595759694976433577988328433842661706589428747156571117135999674936444551580258714486587258385991303844329901427645521440591947903667941319289660253859884254561620088125028052644974421456233409235718772498129833149397112383371079683271552290430258219060408230627476230144212672600444871314883322767765766091056317180646626817737369884039041148771459442299758323139830421332839838789265556071819609550654666601713958375801906074618714984976006421235702717758350486273749274370760077144404040220528058262497939395102663369613380439628759545174185879222650362418049908832887243236665761331458383321899717194958660755312635064254664872675983864235973712089389557418265616392488021596151797224135482105308986389962030366904851813771046935415498730782406381405479407447245754868653158118715287352976507671661958139378778576720022991004237807210894348583985443532241276112070567747222256165616205710788653945519828213935462044147661749938753930525805399815066227453201650388549101768649444921267008365042046870557500008823041951554890675904529900449696956480965989539696817120078770059792925781287086329263515453693954915158075113034251847772044183810791519975394751748689898558643184755405049918895166279673309822931228293858836566706111387755782303153570817649245833032333667842054213757871730349932868292661584780873597066086136442389500475912839216088119841108486391662347062079731254672902674899029699518214058301200750777457011564438182922511442521001995984268256138869931497593880179638256871879617036192483407270454061630517638158243184932640074214448300636762825787790465815764668563496463913308208132649995698735373141415390555852291483484500815988321185085562036902145706789438017907028808993756697737206455275037792438934509173298108120513315559906171631198421284029587594147719363885827441478167145011032769468120924289202232778393912078642897540227099609458372421165141758866287932646170989185314106431149591700094802514858897396699041758339425844464240751057119983473322446616721212147223992580174334557007350960927881867315943334332642940695491969768994404326500028357416077645018208735522571909743009983949514969295187942127329404378677160832336519960825318142197155416340731851260645919302725137544555071001587138361865913869610020046813964288029628639325661944045018679990069117482062667408540078159665476792627727609464378827651542989195295835403415358975420864630649750305992709504305141593468292092307592752869922835502177491274209137425439200221874228995506897015156680511844355698459518412040452728567718750564796432436799348432449300656838463943674982675989477173707352258231743887543890370831923847776897456520636369969092162091745184280276681337290313540310668113227494245314959225865818545519011541766570779681148761193626210642580789249778213667294624434882544083197407549937774724839437798731587141866021779391252395615312782332443779641927867803117304489103054464862680262795383267726188610971192940894213790537294071416726730205471594883721433228376368504612954199281875682722354008368008829216104419411714695859365833919253478762063071643602977518389063782720656357223263241216313572361820175847504844252982987057874164220068040521672328469836464592306793563154877571296188609627034496460131947166538446212919012254668810716374688399318031589528394929563408334799865216916243791743292626558266244742675075043141932261617981129892565665403574343308622614146084017230663331431137651925433876315986267153634604550662950415824747502480466200610391051247440726964692808094793279111690973369958080448664084602168747329814256346908188025350988408755023149023602234381202521094110880045708602978279330585186682370543005483078934421374866586755895231208160088337158986419693355203319013239353078282774833577690956059207864500518287095906947620924029949931753175874435562143765874716124766415127825824615964432848815965950113554908986881667925222069954770436458538642679415426223849782999352673372300095587692034470424817584920835606592005416232142163063811860675226296801628422602496931550282926839192741178956088321254006700753736528365299660401666186057191762832685319951394146399607257198492487552743966275236823358167652345263736845328484728962813506911677057297344263147565172028990923218154374743977986972557154364071686473729120755158098972466164764364174723133739831308749148351607578967167663731642496027598324205449254589569774347797934529348095761991902758597274492714453270008449468177717198558778352897227881317343727862576226683933781009530996463859261721029999232400182859683045569675689735564094220702015200532046757936625767824609574931301140459239519684061215107082750501896927776713568402432626024600037023933362926950572772013241524813551821903918397206414228549609670803975191716443967844951716388728998794031421473735272231299350398015910385361092729651151821698880417945410904078093868101292729686432317134463009920469994588036725518880142735026353443813377718027829505406020624209320516950636677115883541647482379301527827030253893878228533896114934272449887723804178647377070069808576675658862297453768426962115387027831563204856272369832797357524987369951239975394955849991577244396810640025116294721467113309859207527611647172656504666617827100723436255716296340560241791965508380968356492760826619030380149527386679096483387561985627580858698213417544448939324693779903856883193047224074969472304371204815924557386789016238955669917078387526743293422471110798098307919295149698351690292060051768664517835400139440707737153058708374942067914479625653489576221046689102009583275990204420727805525315247763297778390457107854590999922504706533957000281201223037333439582075941217389294007004066228407908176981361152483226774502966345419401520839294164812371688599617061478145851244472595740106111531126050972692112692324644536696638829969755610748492196140526907371579847164359718930654380117174564116306831745525782917696293720614897329567329847914295782004996339608616869335314666310016440449847214080731141333305155228943212236108983815659854488788078415177433713420510131880751373939562070224033826755521057164550382364221770661807737043059665863333551478726681347075391418811989255578959247961513921243511530125570650428018856937528494461104532764853810609396585001355653985407411971100475390919632964463672445959557457316002789630701017761321356552901619335099334034371455919806718070050888430056215415504982059082680608785695024278673325597797460244564709641721764953930807121092176788023261067425229978329080484937119885452370363051174931016571226844501107817257430825095424413699735724942085067083284971345452271827117283080408199610648148305501801351699625666460747552644253733890102992155243068719740706302340978296277916446265891939505815036700437934710820597209891819380845803824373489405580453012602245923228588711964946433066030953971971940726184440457797771365704779180310842476894514626961919420313211174669240180339308707450745435849908238566480931820239396730844939834159539835520365267652153109493744024602572710936711447676793298001499843222206198367461362347443037872840867921337938513402921174599532803337419028941655713258044768482911085148208410745269128322164000964905588586025196626195346493383740849886376838798884171705552284357465574582902339807327385681157197969227967377019522131080539543034046120480759590211097940468197260495377003414278259886498284246796924083372699586047446369939350821679452021759406025102905584703517564709383595844548101684484394096722500733676149770342361688603190659208887448890673918839047238846825182209476344686168575662725171573788089428415878135155838571682175854021220641275734074531752025264273573353362002692709626613363628040612095017751241392114250780529989276473540848610640853332598425521767056764449412150944751983885702497659471745443317315326762070293557486490566097599542027753335469792061948019822613893652258138329386322030221086341121027358266736646396884636053705080988724657400690447840464461461655773380677100421272040268300850789844436092907857017920831684079866210083194383283959542451315166154938620443885757999713343989481730906306101467777016786953480987235750765706642409603195947957572164509632624718647282469393536094494559725835337508503161948059663336909847500227766196098215716445354027542069363013940360081057556406094725833098044011921095111108671389310110869292437654624015532758230108133532483194377417408982878993872197598487636503136242605945485141963728200823295338695822957359295406286581242623104959501964437473377721541066580951762907166567392524118942474796051531937120784344465538392838353702462237955463684895450508205402401766767538326373746046937439965119262653567034347184780064145230921129638556652684502897579905585208928585747724767509459453630062651344263778526708169731103463469029300549829916910486447092931869667139450365273176011129537329641226603894387230876234252863587032037294497909614671567591683038432511824686524393452013042528020324099278170984025125521954167858727517775421062571076622388296439715949837814459985000596806352968776586416979499735952173317368678825428347211164933730040751336059936782202087844841661115151355920999466237763185723650898196669757691556653256399954282915008382136400871203749859120576135422447241406715382248054714493907863050043660697414965962952153768688260782042348988535877235813817006037728000053860045017391983732828315009252255823745973350136670517193303793462190677305622791707032085838152898331912985755306438140782184066321762736305366258795271643685148227730986303639279998134896895177801704036216738218942642541095164479750959275399314287907236027708919481514446366700606740920457583015564213511500237179555539207028906525729971887457720492627272333012936945586431353293995986086638853410256025735957214693070600978906817314309405811762362647805826201329803497706023697984322142490797201509076645723680744743760476438459885290221154928780008701480693132998096463728871468846529674424122480294810088090593385769565974020112928573277939654479610870501248910980516161842145414681810570331478220295814616402947621143869657158784949113210174909599176265259116881606619023047918591671916880454181950910455139278813495233693220129047496879813104666178141108257981223074602515165936108175532839367254471605681047640818037797698555820832865575935084003380946863079979636705097178341959975234839106924745231810116701586366793200263785493953669561284714416081071612984016961273884785877704390477890088462915555691321683623723043487135348091016616511316510035238831270323996684545268032474574284123215803511240071514405463231630469826196547378293619390955186259855212638119522846507810897154078372754183885811424719364576921949646824350068876579032210791641021131920630733608839649462176499897417861015856267768691931182039332923004777396758404408101058061490665025352442920366950965737565579295993434743105014801137196283595650517307072305753392537882118467715935402561622556346903484861807204197074943579823558720947272780562150121633107652627568217122424455581933819865763943843606201823031155661068612796389108707758140625457955977607784518889768164365895835165157243764471408892405990796916673993962308391218968902957296521000029309182566898209208945162519417333450570063600926170169113983411002667135613587737038014009789266977344001875787684281485389372490401242709340836484070459274890823294938304170696679269615170432896626513086550016120050411794015064919839385679533397813534980509393593012690876051466924587473255370907705384096837539201031683226354816964154869720683490137460066238752601189952812216067293883173598288343738093144582197602508866027726486708285705911662123743368797444239280166476156979981828306808523110290453999237961253260646560567425774495149330285178346375919575603036431313930654474046718837011635745479058589055951229520208681379876315249567689557138251414168058852838594331604091561886338990005568744687710659749699580878689293355608312084175972332131656848090506755766581670037222661859960725695360356399660013482223980773176236114774758931973387262229256426038277792432369061226882382250359037486444503062809578240862862334769483279111345584571646296784782672411266449778715671619918520472464022978399132448196019813007415223189425246929863126117412585362994226091034321052785837802983674785310237697470617544476684545268032474574284123215803511240071514405463231630469826196547378293619390955186259855212638119522846507810897154078372754183885811424719364576921949646824350068876579032210791641021131920630733608839649462176499897417861015856267768691931182039332923004777396758404408101058061490665025352442920366950965737565579295993434743105014801137196283595650517307072305753392537882118467715935402561622556346903484861807204197074943579823558720947272780562150121633107652627568217122424455581933819865763943843606201823031155661068612796389108707758140625457955977607784518889768164365895835165157243764471408892405990796916673993962308391218968902957296521000029309182566898209208945162519417333450570063600926170169113983411002667135613587737038014009789266977344001875787684281485389372490401242709340836484070459274890823294938304170696679269615170432896626513086550016120050411794015064919839385679533397813534980509393593012690876051466924587473255370907705384096837539201031683226354816964154869720683490137460066238752601189952812216067293883173598288343738093144582197602508866027726486708285705911662123743368797444239280166476156979981828306808523110290453999237961253260646560567425774495149330285178346375919575603036431313930654474046718837011635745479058589055951229520208681379876315249567689557138251414168058852838594331604091561886338990005568744687710659749699580878689293355608312084175972332131656848090506755766581670037222661859960725695360356399660013482223980773176236114774758931973387262229256426038277792432369061226882382250359037486444503062809578240862862334769483279111345584571646296784782672411266449778715671619918520472464022978399132448196019813007415223189425246929863126117412585362994226091034321052785837802983674785310237697470617544476684545268032474574284123215803511240071514405463231630469826196547378293619390955186259855212638119522846507810897154078372754183885811424719364576921949646824350068876579032210791641021131920630733608839649462176499897417861015856267768691931182039332923004777396758404408101058061490665025352442920366950965737565579295993434743105014801137196283595650517307072305753392537882118467715935402561622556346903484861807204197074943579823558720947272780562150121633107652627568217122424455581933819865763943843606201823031155661068612796389108707758140625457955977607784518889768164365895835165157243764471408892405990796916673993962308391218968902957296521000029309182566898209208945162519417333450570063600926170169113983411002667135613587737038014009789266977344001875787684281485389372490401242709340836484070459274890823294938304170696679269615170432896626513086550016120050411794015064919839385679533397813534980509393593012690876051466924587473255370907705384096837539201031683226354816964154869720683490137460066238752601189952812216067293883173598288343738093144582197602508866027726486708285705911662123743368797444239280166476156979981828306808523110290453999237961253260646560567425774495149330285178346375919575603036431313930654474046718837011635745479058589055951229520208681379876315249567689557138251414168058852838594331604091561886338990005568744687710659749699580878689293355608312084175972332131656848090506755766581670037222661859960725695360356399660013482223980773176236114774758931973387262229256426038277792432369061226882382250359037486444503062809578240862862334769483279111345584571646296784782672411266449778715671619918520472464022978399132448196019813007415223189425246929863126117412585362994226091034321052785837802983674785310237697470617544476684545268032474574284123215803511240071514405463231630469826196547378293619390955186259855212638119522846507810897154078372754183885811424719364576921949646824350068876579032210791641021131920630733608839649462176499897417861015856267768691931182039332923004777396758404408101058061490665025352442920366950965737565579295993434743105014801137196283595650517307072305753392537882118467715935402561622556346903484861807204197074943579823558720947272780562150121633107652627568217122424455581933819865763943843606201823031155661068612796389108707758140625457955977607784518889768164365895835165157243764471408892405990796916673993962308391218968902957296521000029309182566898209208945162519417333450570063600926170169113983411002667135613587737038014009789266977344001875787684281485389372490401242709340836484070459274890823294938304170696679269615170432896626513086550016120050411794015064919839385679533397813534980509393593012690876051466924587473255370907705384096837539201031683226354816964154869720683490137460066238752601189952812216067293883173598288343738093144582197602508866027726486708285705911662123743368797444239280166476156979981828306808523110290453999237961253260646560567425774495149330285178346375919575603036431313930654474046718837011635745479058589055951229520208681379876315249567689557138251414168058852838594331604091561886338990005568744687710659749699580878689293355608312084175972332131656848090506755766581670037222661859960725695360356399660013482223980773176236114774758931973387262229256426038277792432369061226882382250359037486444503062809578240862862334769483279111345584571646296784782672411266449778715671619918520472464022978399132448196019813007415223189425246929863126117412585362994226091034321052785837802983674785310237697470617544476684545268032474574284123215803511240071514405463231630469826196547378293619390955186259855212638119522846507810897154078372754183885811424719364576921949646824350068876579032210791641021131920630733608839649462176499897417861015856267768691931182039332923004777396758404408101058061490665025352442920366950965737565579295993434743105014801137196283595650517307072305753392537882118467715935402561622556346903484861807204197074943579823558720947272780562150121633107652627568217122424455581933819865763943843606201823031155661068612796389108707758140625457955977607784518889768164365895835165157243764471408892405990796916673993962308391218968902957296521000029309182566898209208945162519417333450570063600926170169113983411002667135613587737038014009789266977344001875787684281485389372490401242709340836484070459274890823294938304170696679269615170432896626513086550016120050411794015064919839385679533397813534980509393593012690876051466924587473255370907705384096837539201031683226354816964154869720683490137460066238752601189952812216067293883173598288343738093144582197602508866027726486708285705911662123743368797444239280166476156979981828306808523110290453999237961253260646560567425774495149330285178346375919575603036431313930654474046718837011635745479058589055951229520208681379876315249567689557138251414168058852838594331604091561886338990005568744687710659749699580878689293355608312084175972332131656848090506755766581670037222661859960725695360356399660013482223980773176236114774758931973387262229256426038277792432369061226882382250359037486444503062809578240862862334769483279111345584571646296784782672411266449778715671619918520472464022978399132448196019813007415223189425246929863126117412585362994226091034321052785837802983674785310237697470617544476684545268032474574284123215803511240071514405463231630469826196547378293619390955186259855212638119522846507810897154078372754183885811424719364576921949646824350068876579032210791641021131920630733608839649462176499897417861015856267768691931182039332923004777396758404408101058061490665025352442920366950965737565579295993434743105014801137196283595650517307072305753392537882118467715935402561622556346903484861807204197074943579823558720947272780562150121633107652627568217122424455581933819865763943843606201823031155661068612796389108707758140625457955977607784518889768164365895835165157243764471408892405990796916673993962308391218968902957296521000029309182566898209208945162519417333450570063600926170169113983411002667135613587737038014009789266977344001875787684281485389372490401242709340836484070459274890823294938304170696679269615170432896626513086550016120050411794015064919839385679533397813534980509393593012690876051466924587473255370907705384096837539201031683226354816964154869720683490137460066238752601189952812216067293883173598288343738093144582197602508866027726486708285705911662123743368797444239280166476156979981828306808523110290453999237961253260646560567425774495149330285178346375919575603036431313930654474046718837011635745479058589055951229520208681379876315249567689557138251414168058852838594331604091561886338990005568744687710659749699580878689293355608312084175972332131656848090506755766581670037222661859960725695360356399660013482223980773176236114774758931973387262229256426038277792432369061226882382250359037486444503062809578240862862334769483279111345584571646296784782672411266449778715671619918520472464022978399132448196019813007415223189425246929863126117412585362994226091034321052785837802983674785310237697470617544476684545268032474574284123215803511240071514405463231630469826196547378293619390955186259855212638119522846507810897154078372754183885811424719364576921949646824350068876579032210791641021131920630733608839649462176499897417861015856267768691931182039332923004777396758404408101058061490665025352442920366950965737565579295993434743105014801137196283595650517307072305753392537882118467715935402561622556346903484861807204197074943579823558720947272780562150121633107652627568217122424455581933819865763943843606201823031155661068612796389108707758140625457955977607784518889768164365895835165157243764471408892405990796916673993962308391218968902957296521

 

A projective hyperbola

After making the graphs of projective curves that I recently did with POV-Ray, I realized that I didn't make a graph of a hyperbola. To take care of that oversight, here's the projective version of xy = 1, or xy = z². The blue line is the hyperbola. The red line is where z = 0. This shows how thinking of a hyperbola as a circle that happens to run through the point at infinity seems to be a reasonable idea.

  

 

 

 

Celebrating Ten Years of Identity-Based Encryption (IBE)

Over the past 10 years, IBE has become the one of the fastest deployed encryption technologies as measured by the commercial adoption of Voltage SecureMail™ and the use of IBE as a general purpose key management solution used across the Voltage Security product line. Since its commercial launch 8 years ago, Voltage SecureMail has become one of the most widely adopted secure email products in the world with over one billion secure business emails sent annually and over 50 million worldwide users; those numbers are expected to double by 2014.

IBE was first introduced on Tuesday August 21 at the 2001 Crypto conference in a seminal paper by Dan Boneh, Stanford University, and Matt Franklin, University of California Davis. The paper, entitled “Identity-Based Encryption from the Weil Pairing,” set forth a simple but powerful approach for encrypting information with identity-based keys. This cryptography breakthrough became the founding technology for Voltage Security that was incorporated in 2002 by three Stanford students working with Professor Boneh: Matt Pauker, Rishi Kacker and Guido Appenzeller. In July 2003, the new company launched Voltage SecureMail, an email encryption product using IBE to secure messages without the difficulties and expenses of traditional certificates.

Key metrics in the 10 year history of IBE:

• 50 million Voltage SecureMail users worldwide.
• Approximately one billion IBE secured business emails will be sent in 2011.
• By 2014, it is estimated there will be 100 million Voltage SecureMail licensed users and over two billion secure emails will be sent that year.
• All the messages protected by IBE in 2011, if printed out, would circle the globe seven times.
• Nearly a third of the world’s 20 biggest public companies (per the Forbes Global 2000) have standardized on Voltage SecureMail.

 World’s Biggest Companies Standardize on Voltage SecureMail

Nearly 30% of the world’s 20 biggest public companies (as listed by Forbes Global 2000) have standardized on Voltage SecureMail powered by IBE including four of the world’s largest global financial institutions; one of the world’s largest retailers, one of the largest U.S. managed healthcare providers and several large regional healthcare providers.

 

 

 

Notable Voltage SecureMail customers from the last year include:

• One of the largest Wall Street banks with over 230,000 employees standardizes on Voltage SecureMail
• A major Wall Street bank and Fortune 100 financial services provider with global operations chooses Voltage SecureMail for its 100,000 employees around the world.
• A major credit card brand with over 60,000 employees standardizes on Voltage SecureMail
• An award-winning regional health care organization replaces a non-functioning email security solution from one of the largest technology companies in the world with a policy-based encryption solution from Voltage SecureMail

• A Fortune 50 global financial services company deploys Voltage SecureMail to over 320,000 internal and several million external users across 86 countries, replacing an aging PKI-based encryption technology.

In addition, over 1000 enterprise companies have standardized on Voltage SecureMail, and thousands of mid-size to smaller business use the cloud-based Voltage SecureMail Cloud™ solution to protect private and confidential information.

More information at www.voltage.com

A projective imaginary hyperelliptic curve

As if the previous post showing a picture of a projective elliptic curve wasn't bad enough, I had to tweak the POV-Ray scene file a bit to get it to plot a projective imaginary hyperelliptic curve. Here's what y² = x⁵ + x looks like. As before, the red curve shows where z = 0 and the blue is the hyperelliptic curve.

 

 

 

A projective elliptic curve

I finally managed to get a reasonable projective graph of an elliptic curve. Here's what it looks like. The elliptic curve y² = x³ + x is blue and the line where z = 0 is red.  As before, these were created using POV-Ray. It's interesting to see the inflection point of the elliptic curve on these graphs.

The projective curve

y²z = x³ + axz² + bz³

meets z = 0 at (0,1,0), and if we set y = 1 in the projective curve we're left with 

z = x³ + axz² + bz³

Out close to  z = 0, this looks roughly like z = x³, which gives us the inflection point that we see in these graphs.

 

 

 


 

More projective graphs

 
I still haven't been able to get a graph of a projective elliptic curve that looks the way I want it to, but I've learned a few things about making projective graphs with POV-Ray. In particular, it seems useful to show a circle that shows where z = 0 is. If you add this to the graphs of a few simple polynomials, here's what you get.

Here's the graph of y = x².

 

Here's the graph of y = x³.

 
 

Here's the graph of y = x⁴.

 
 

Here's the graphy of y = x⁵.

 
 

Hyperbolic numbers on Jack Bauer day

On our recent Jack Bauer day, I was trying to implement the Tate pairing using hyperelliptic curve groups when I came across a bug in the program that I was working on. In one place I had accidentally implemented complex numbers in an incorrect way. For a complex number z = x + i y I had implemented i² = 1 instead of i² = -1.

I found this bug fairly quickly, but then I started thinking about the properties of numbers the form z = x + i y where i² = 1 instead of i² = -1. I followed this tangent for a while and never actually got back to the Tate pairing.

I didn’t know this at the time, but numbers of the numbers the form z = x + i y where i² = 1 are sometimes called "hyperbolic numbers." They're probably not as useful as the complex numbers because they’re not a field. That’s easy to see because they have zero divisors because we always have

(x + x i)(x – x i) = 0

But you get something sort of interesting if you look at what you get for the analog of an analytic function in the hyperbolic numbers. In the complex numbers, if we have an analytic function

f(z) = f(x + i y) = u(x,y) + i v(x,y)

then the Cauchy-Riemann equations tell us that we have

∂u/∂x = ∂v/∂y

and

∂u/∂y = -∂v/∂x

A quick corollary of the CRE is that u and v satisfy Laplace’s equation, or that

∂²u/∂x² + ∂²u/∂y² = 0

and

∂²v/∂x² + ∂²v/∂y² = 0

What about the case where we use hyperbolic numbers instead of complex numbers?

It turns out that the CRE aren’t true for functions of hyperbolic numbers, but we find that we now have

∂u/∂x = ∂v/∂y

and

∂u/∂y = ∂v/∂x

A quick corollary of these is that u and v now satisfy the wave equation, or that

∂²u/∂x² = ∂²u/∂y²

and

∂²v/∂x² = ∂²v/∂y²

After thinking about hyperbolic numbers for a while I looked around the Internet and found "Hyperbolic Analysis" by Andrei Khrennikov and Gavriel Segre and "Hyperbolic Cauchy Integral Formula for the Split Complex Numbers" by Matvei Libine, at which point I stopped thinking about them and started fighting with HTML to write this post. I never did get back to the Tate pairing on hyperellitpic curves. Maybe I'll try that next Jack Bauer day.

More on probability distributions without a mean

After some more discussion about probability distributions without a mean, I made some graphs that might show what's going on. In particular, consider the pdf

f(x) = 1 / (π (1 + x²))

Here's what that distribution looks like. It certainly looks like it might have mean zero.

 

But just like the example in last week's post, this pdf has the property that although

_-∞∫^∞ f(x) dx = 1

we also have

_-∞∫^∞ x f(x) dx

diverges, so the mean of this distribution doesn't exist.

We can get a rough idea from its graph why this particular distribution has no mean. If we compare it (red) to a (0,1) normal distribution (blue), this is what we see:

 
So it looks like the problem is roughly that the tails of the red distribution are too big, so that their contribution to the mean is too much for the mean to exist.

Events that are independent of themselves

Another interesting bit of probability trivia came up today in a discussion of random versus deterministic encryption. In particular, it's possible to have an event that's independent of itself. Here's why.

Two events A and B are independent if we have

P(A ∩ B) = P(A) P(B)

So an event A is independent of itself if we have

P(A ∩ A) = P(A) P(A)

or

P(A) = P(A)²

That's true if either P(A) = 0 or P(A) = 1, in which case the event A is independent of itself.

Why quaternions flopped

After last week's post about the relationship between quaternions and the dot and cross products of vectors, I was asked why I thought quaternions didn't end up being very useful. I'd guess that the short answer is that they really don't model the real world very well.

It definitely isn't because multiplication of quaternions isn't commutative. Matrix multiplication also isn't commutative, yet matrices have ended up being very useful.

Instead, I'd guess that the problem with quaternions is that calculus doesn't work very well with them. With the complex numbers, there's a nice, clean way to characterize analytic functions: df/dz* = 0. But that doesn't seem to extend to the quaternions very well.

If we have a quaternion

q = q₀ + q₁ i + q₂ j + q₃ k

and its conjugate

q* = q₀ - q₁ i - q₂ j - q₃ k

then we have

qq* = q₀² + q₁² + q₂² + q₃²

which looks about right.

But we also find that we can write

q* = -(q + i q i + j q j + k q k) / 2

And because q and q* are connected in this way, we can never find a nice condition like df/dq* = 0 to characterize functions of a quaternion variable like we can for analytic functions. So I'd guess that's also part of why they haven't ended up being very useful.

Probability distributions without a mean

While talking about random versus deterministic encryption this morning, we got into an interesting digression about probability. In particular, about the fact that not all probability distributions have a mean. Here's an example of this.

Let f(x) = 1 / x² for x ≥ 1 and 0 otherwise.

We have

∫_x≥0 f(x) dx = 1

so this f(x) makes sense as a pdf. But we find that the expected value

E(X) = ₁∫^∞ x f(x) dx

= ₁∫^∞ dx / x

This integral diverges, so the mean does not exist in this particular case.

(If you're familiar with Lebesgue integrals, you might want to define f(x) to be 1 / (2x²) for |x| ≥ 1. That gives a mean of ∞ - ∞ which is even undefined for Lebesgue integrals.)

It's also easy to create examples of discrete random variables that don't have a mean. We have that

∑_n≥1 1 / n² = π² / 6

so f(n) = 6 / (π² n²) makes sense as a discrete pdf. But we find that the expected value is

E(N) = ∑_n≥1 n f(n)

= (6/π²) ∑_n≥1 1 / n

This sum diverges, so the mean does not exist.

The origin of dot and cross products

I was reading about quaternions last night when I came across an interesting bit of history.

Quaternions are generalizations of the complex numbers with four components instead of just two. We can write a quaternion a as being

a = a₀ + a₁ i + a₂ j + a₃ k

where i, j and k satisfy

i² = j² = k² = -1

i j = k = -j i

j k = i = -k j

k i = j = -i k

Note that multiplication of quaternions isn't commutative, so if a and b are quaternions then we don't necessarily have that ab = ba. Quaternions were apparently the first significant example of a structure where this was the case. But there's more to their history than that.

Let's split a quaternion a into a "scalar part" a₀ and a "vector part"

a_v = a₁ i + a₂ j + a₃ k

When we do that, we find that we can write the product of two quaternions a and b as

ab = (a₀ + a_v)(b₀ + b_v)

= a₀ b₀ – a_v ⋅ b_v + a₀b_v + b₀a_v + a_v × b_v

If a and b are "pure vectors," or that a₀ = b₀ = 0 then this reduces to

ab =  a_v × b_v – a_v ⋅ b_v

The first time that the dot product and cross product of vectors were defined was apparently to write multiplication of quaternions like this. The concepts didn't turn out to be very useful for understanding quaternions, but physicists soon realized that the operations were useful. They took the ideas and ran with them, and their future development ended up being totally independent from where they were originally invented. That’s something that I hadn't heard before.

Visual group theory

Nathan Carter's book Visual Group Theory tries to help you understand group theory through a set of pictures. Some of these made sense to me while others didn't. Here's the illustration of the structure of dihedral groups from a presentation that Carter gave before the book was available. That seems to show their structure in a very useful way.

 

Carter's book runs 297 pages, many of which are illustrations like this one. It's a book that I would have found very useful back when I was taking classes in group theory. It would have definitely helped to make some concepts clearer. If you're interested in group theory, this is probably a book that you'll want to have a copy of.

Carter has also developed software that lets you create visualizations of groups. This is Group Explorer, and it's something that I wish I had time to actually try. Maybe I'll do that on Voltage's next Jack Bauer Day.

The spectrum of a ring

Because the machinery that Voltage's IBE algorithms use comes from algebraic geometry, the engineers who work on our core cryptography need to understand at least a little of it. So I wasn't too surprised this morning when I was asked what the connection is between the spectrum of a ring and the spectrum of a matrix. Here’s the totally non-rigorous answer that I came up with.

Suppose that we have an n x n matrix A over the complex numbers ℂ. The spectrum of A is the set of eigenvalues of A, or the solutions to

f(x) = det(A – x I) = 0

The spectrum of a ring is the set of prime ideals of the ring.

These two ideas sound like they’re totally unrelated at first, but there’s actually a connection. Here’s an example that shows this.

The Cayley-Hamilton theorem tells us that the matrix A satisfies f(x). So if we write

f(x) = a₀ + a₁ x + a₂ x² + … + a_n-1 x^n-1 + xⁿ

then we also have that

f(A) = a₀ I + a₁ A + a₂ A² + … + a_n-1 A^n-1 + Aⁿ = 0

To make things simpler, let's suppose that A has n distinct eigenvalues, and let's write

f(x) = (x - λ₁) (x - λ₂) ... (x - λ_n)

Now consider the ring ℂ[A] where

ℂ[A] = {z₀ + z₁ A + z₂ A² + …, z_i∈ℂ}

Because we have that

f(A) = a₀ I + a₁ A + a₂ A² + … + a_n-1 A^n-1 + Aⁿ= 0

we can reduce elements of ℂ[A] modulo f(A) to get rid of powers of A higher than n - 1. That's just like working in the quotient ring

ℂ[A] / (f(A))

But we can also think of this quotient as

ℂ[A] / ((A - λ₁ I) (A - λ₂ I) ... (A - λ_n I))

From there, the correspondence between the eigenvalues λ_i and the prime ideals (A - λ_i I) seems fairly natural. Or at least it's where most people seem to say, "Ah, I see the connection now." So if you're going to generalize this idea to other rings, calling the set of prime ideals the spectrum of the ring actually seems to make sense.