Author: John

New RSA number factored

Posted on by John

Eric Lu announced on X today that he has factored RSA-260, a number N with 260 digits (862 bits) that is the product of two large primes [1].

RSA numbers are challenge problems posed to gauge the security of RSA encryption, which rests on the difficulty of factoring large numbers [2]. The naming scheme is confusing because RSA-n might have n digits or n bits. For example, RSA-768 is smaller than RSA-260 because the former has 768 bits and the latter has 260 digits.

RSA-260 is the largest RSA number factored so far. What does the news of its factorization say about the security of RSA?

Based on equations here, an RSA key with 862 bits would have a security level of 74 bits, i.e. the same security level as symmetric encryption with a 74-bit key. The minimum recommended RSA key size now is 2048 bits, which has a security level of 107 bits.

Security levels are on a logarithmic scale: each additional bit of security doubles the effort required to break the encryption by brute force. So breaking a 2048-bit RSA key would take 234, roughly 1010, times more effort than factoring RSA-260. All this depends on numerous assumptions, such as the state of factorization algorithms and the non-existence of CRQC [3].

Update: A week after the initial announcement, Eric Lu released an article explaining how he factored RSA-260. He says “In total, I estimate that this factorization cost about 4,900 GPU-days, or 13.5 GPU-years, which is about $400k at current market prices.”

Related posts

[1] N = pq = 22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199

p = 4397328654844826923795068102505872571721883526553349659561256924505973939597593482272505698004801207988043088656411102133523080581

q = 5028695206842569864686141618253083416610081090075366674776775706538324961364412200138116378509733307971876652984898985905923678379

[2] The ability to efficiently factor large primes would break RSA. It’s possible that there’s a way to break RSA without being able to factor large numbers. More on that here.

[3] Cryptographically-relevant quantum computer. Quantum computers exist, but so far they’re cryptographically irrelevant. So far quantum computers cannot factor 21 without cheating.

Patented application of linear algebra

Posted on by John

I just found out Brian Beckman and I got a patent on work we did for GSI Technology [1]. Nearly all the work I do is under an NDA, so I don’t often get a chance to talk about my projects. This work is public now that it’s in a patent; I suppose it has been public since the application was published.

Brian did most of the work on the project. My contribution was to mathematically formalize low-level operations on sheets of bits using linear algebra over a binary field. Lots of Hadamard products and outer products, if I remember correctly. When you can reduce computations to algebra, you can prove that a sequence of operations is correct, and you can find optimizations by simplifying expressions.

The patent mentions a programming language called Tartan. I suggested calling it plaid because it used matrices with mask patterns that reminded me of a plaid pattern, and Brian countered saying we should call it Tartan. I like that name better.

Figure 5B from patent

Figure 5B from the patent.

[1] Brian Beckman and John D. Cook. Compiler for a parallel processor. U.S. Patent 12,717,871 B2. Applicant/Assignee: GSI Technology Inc., Sunnyvale, CA.

Making the unnecessary easier

Posted on by John

I watched a few videos this morning, looking for ideas of what I could use AI to do.

In one video, someone had an agent monitor tech news sites every 30 minutes to notify him of a variety of developments. No doubt that’s less effort than visiting a bunch of sites every half hour, but not monitoring tech news in real time takes even less effort.

Another video mentioned having Grok Bot order a sandwich through DoorDash. If I want a sandwich, I make a sandwich.

One video showed how to manage dozens messaging services. Maybe you could just not use dozens of messaging services.

And of course there are videos on creating agents to monitor the agents that monitor your news, order your sandwiches, and manage your messages.

All the use cases I saw were ways to using technology mitigate problems caused by technology, making it easier to do things that don’t need to be done, or at least things that I don’t need to do.

Of course different people have different needs. Some people have a professional need to monitor news in real time, for example, and having an agent help with that could be big win. I suspect, however, that the use cases that you’ll see most often in YouTube videos have been made up to appeal to a wide audience rather than to scratch the author’s itch.

Productivity is deeply personal. As I said in an earlier post, the scripts I’ve found most useful are of zero interest to anyone else because they are so specific to my work. I’ve mostly automated tasks with Python and bash, not with AI.

I’m not trying to avoid using AI. As I said at the top of the post I’m looking for more ways to take advantage of it. But I don’t want to fall into the trap of doing more easily what doesn’t need to be done. Or, to put a finer point on it, I don’t want to find ways for my business to do things that we do not need to do, things that other businesses may need to do.

Related posts

Second solutions

Posted on by John

This post provides a couple examples to go along with two earlier posts.

The pattern we’re illustrating is families of polynomials pn(x) that each satisfy a differential equation and a three-term recurrence. The differential equations have a second solution qn(x) that is the larger solution with respect to x but the smaller solution with respect to n.

In both the examples below pn(x) is a polynomial, and so bounded on the interval [−1, 1], and qn(x) is not a polynomial, with singularities at ±1. This is analogous to the previous examples with Bessel functions Jn(x) and Qn(x) that satisfy the same differential equation but have contrasting behavior with respect to x versus n.

Legendre polynomials

The differential equation

(1-x^2)\,y^{\prime\prime} - 2x\,y^\prime + n(n+1)\,y = 0

has two solutions for each n, Pn(x) and Qn(x).

The solutions Pn(x) are the Legendre polynomials. The solutions Qn(x) are not polynomials but involve a term log((1 + x)/(1 − x)) that blows up at 1 and −1. But for fixed x and increasing n, Pn(x) grows exponentially and Qn(x) decays exponentially, provided |x| > 1.

Chebyshev polynomials

The differential equation

(1-x^2)\,y^{\prime\prime} - x\,y^\prime + n^2\,y = 0

has two solutions for each n, Tn(x) and Vn(x).

The solutions Tn(x) are the Chebyshev polynomials. The solutions Vn(x) are not polynomials but involve a term √(x² — 1) that become vertical up at 1 and −1. But for fixed x with |x| > 1 and increasing n, Tn(x) grows exponentially and Vn(x) decays exponentially.

Junk solutions

Posted on by John

When you’re interested in studying a family of functions, it can be useful to look at a differential equation that the functions solve. This is a theme I’ve written about several times, most recently here and here, but also three years ago here.

Orthogonal polynomials are mathematically elegant as well as very useful in applications [1]. Various families of orthogonal polynomials satisfy various differential equations. These equations have a polynomial and non-polynomial solutions. What use are the latter?

If the differential equation modeled something physical, then the second solution would be necessary to have a complete basis of solutions. But if the differential equation is only instrumental in studying the orthogonal polynomials, what use is a non-polynomial solution?

These non-polynomial solutions turn out to be useful. Just as “junk” DNA turned out not to be junk, these “junk” solutions are important. Junk DNA doesn’t directly code for proteins, but it regulates DNA that does code for proteins and serves other purposes. Similarly, these non-polynomial solutions carry information related to the polynomial solutions.

For example, orthogonal polynomials are used to construct numerical integration methods, such as Gaussian quadrature, and the associated non-polynomial solutions describe the error in these integration methods. Incidentally, Gaussian quadrature is based on Legendre polynomials, mentioned in the previous post. For every family of orthogonal polynomials there is a corresponding integration method. See these notes.

Another tie-in to recent posts is that these non-polynomial solutions are the minimal solution to the polynomial family’s three-term recurrence, the solution that takes extra care to compute numerically.

This post has been very high-level, alluding to ideas without going into details. I’d like to write future posts that go into more depth regarding the ideas introduced here.

 

[1] “Real analysts cannot do without Fourier, complex analysts cannot do without Laurent, and numerical analysts cannot do without Chebyshev [polynomials].” — Lloyd N. Trefethen”

Ultraspherical

Posted on by John

When I hear the term ultraspherical I think of something extremely spherical. For example, a baseball is spherical, but a billiard ball is more spherical. Maybe a highly polished billiard ball is ultraspherical.

Using this line of thought, the term ultraspherical polynomial is inexplicable. This is an example of the arcane terminology I wrote about recently. In this post I’ll explain what it conveys.

A spherical polynomial is a polynomial that naturally falls out of solving Laplace’s equation in spherical coordinates, using separation of variables. Legendre polynomials are spherical polynomials.

Gegenbauer polynomials are so called because a man named Gegenbauer studied them, just as Legendre polynomials take their name from Legendre. Gegenbauer polynomials are also called ultraspherical polynomials. Why is that?

There are two possible reasons. I’m not sure which is the historical reason, but both are plausible and are useful mnemonics.

Ultraspherical polynomials are not extremely spherical, they’re beyond spherical in some sense. More modern terminology uses the hyper- prefix rather than ultra-, which helps a bit.

Ultraspherical polynomials are beyond spherical in two ways. Gegenbauer polynomials are a generalization of Legendre polynomials, so they’re beyond Legendre polynomials in this sense.

More importantly, Gegenbauer polynomials fall out of solving Laplace’s equation on a hypersphere, i.e. a sphere in ℝn for n > 3, just as Legendre polynomials fall out of the case n = 3. It makes sense to call these polynomials hyperspherical because they fall out of solving an equation on a hypersphere. Unfortunately the classical term is ultraspherical rather than hyperspherical.

I think, but I’m not sure, that at one time higher dimensional spheres were called hyperspheres, but the the higher dimensional analog of spherical coordinates was called ultraspherical coordinates. If so, it would be understandable that the adjective modifying coordinates would be applied to the polynomials that result from solving equations in these coordinates.

Numerical (in)stability of recurrence relations

Posted on by John

The previous post gave several examples of three-term recurrence relations for special functions. These relations can be computationally useful, but they have to be applied carefully.

Several years ago I wrote a post on stable and unstable recurrences. In that post I show that the stability of the recurrence relation for Bessel functions produces depends on which kind of Bessel function and which direction the recurrence is applied.

In the forward direction, computing higher order values from lower order values, works well for Bessel functions of the second kind Yn but not for Bessel functions of the first kind Jn. In the reverse direction, the recurrence is stable for Jn but not for Yn.

I didn’t explain in that post why this is. In this post I will.

Second order linear difference equations have two independent solutions, just like second order linear differential equations. For both kinds of equations, all solutions are linear combinations of the two solutions. Suppose one solution grows with n and the other decays. You may want to compute the decaying solution, but in doing so you might pick up a small component of the growing solution due to rounding error. This post illustrates this phenomena for differential equations, and this post illustrates it for difference equations.

When you look at a plot of Bessel functions in a text book, you’ll probably see a few plots of Jn(x) andYn(x) for a few small values of n. The functions seem to behave roughly the same way, like sine and cosine. And that’s true, as functions of x.

But it’s not true for Jn(x) andYn(x) as functions of n for fixed x. As n increases, Jn(x) decays to zero and Yn(x) goes off to −∞.

That’s the source of numerical instability. And there will be similar instability problems for other recurrences where the ratios of the two independent solutions goes to zero or infinity as a function of n.

There are techniques for computing the solution that does not diverge, the so-called minimal solution, such as Miller’s algorithm mentioned here.

 

Three-term recurrences

Posted on by John

There many examples of families of functions where each function can be computed as a linear combination of the two previous terms

f_{n+1}(x) = a(x) f_n(x) + b(x) f_{n-1}(x)

where a and b are functions of x and possibly n. This is called a three-term recurrence formula.

It’s amazing how often you can run into three-term recurrence formulas. There are theorems that give conditions for such recurrences to hold, but I haven’t reached the bottom of that rabbit hole [1].

For this post I just want to give examples.

NB: before using any of the recurrences below, see the next post for a numerical pitfall to avoid.

Bessel functions of the first and second kind:

\begin{align*} J_{\nu+1}(x) &= \frac{2\nu}{x}\,J_\nu(x) - J_{\nu-1}(x) \\ Y_{\nu+1}(x) &= \frac{2\nu}{x}\,Y_\nu(x) - Y_{\nu-1}(x) \end{align*}

Modified Bessel functions of the first and second kind:

\begin{align*} I_{\nu+1}(x) &= I_{\nu-1}(x) - \frac{2\nu}{x}\,I_\nu(x) \\ K_{\nu+1}(x) &= K_{\nu-1}(x) + \frac{2\nu}{x}\,K_\nu(x) \end{align*}

Chebyshev polynomials of the first and second kind:

\begin{align*} T_{n+1}(x) &= 2x\,T_n(x) - T_{n-1}(x) \\ U_{n+1}(x) &= 2x\,U_n(x) - U_{n-1}(x) \end{align*}

Hermite polynomials (physicists’ convention):

H_{n+1}(x) = 2x\,H_n(x) - 2n\,H_{n-1}(x)

Legendre polynomials:

P_{n+1}(x) = \frac{2n+1}{n+1}\,x\,P_n(x) - \frac{n}{n+1}\,P_{n-1}(x)

[1] See Bochner’s theorem for orthogonal polynomials, the Nikiforov–Uvarov method, and Infeld-Hull factorization.

The von Mises-Fisher distribution

Posted on by John

Probability density function must integrate to 1, and so if you know a density function up to a constant, the constant is determined.

When you’re looking at a probability density f(x) for the first time, it helps to ignore the normalizing constant. Concentrate on the part of the function involving x and know that the normalizing constant is whatever it has to be. For example, about half of the ink that it takes to write down a beta or chi-squared density is devoted to the normalization constant; the rest of the expression is easier to understand.

This post will do the opposite of the advice above and focus on normalization constants because this ties into the previous post on modified Bessel functions.

The von Mises probability distribution on a circle has two parameters, μ and κ, and its density function is

f(x \mid \mu, \kappa) = \frac{\exp(\kappa \cos(x - \mu))}{2\pi I_0(\kappa)}

The normalizing constant is 2π I0(κ). The factor of 2π is unsurprising for anything defined on a circle. The more interesting part is I0, the modified Bessel function of order 0.

The von Mises-Fisher distribution is the generalization of the von Mises distribution to a sphere in p dimensions. The density function is

f(\mathbf{x} \mid \boldsymbol{\mu}, \kappa) = C_{p}(\kappa) \exp \left( {\kappa \boldsymbol{\mu}^\mathsf{T} \mathbf{x} } \right)

where the normalization constant Cp(κ) is

C_{p}(\kappa)=\frac {\kappa^{p/2-1}} {(2\pi)^{p/2}I_{p/2-1}(\kappa)}

where Ip/2 − 1 is the modified Bessel function of order p/2 − 1. The values of x and μ are in bold face because they are now vectors, points on the unit sphere.

When p = 2, we have the “sphere” in two dimensions, i.e. the circle, and the von Mises-Fisher distribution reduces to the von Mises distribution. But where did the cosine go? The inner product of x and μ is the cosine of the angle between the two vectors.

When p = 3, obviously an important special case, the von Mises-Fisher distribution is known as the Fisher distribution. In that case the normalizing constant C3(κ) can be written without using modified Bessel functions because when ν = ½ + n for an integer n, Iν(x) is an elementary function.

What exactly is modified about a modified Bessel function?

Posted on by John

Special functions often have arcane names that not very helpful without some context. The previous post goes into some reasons for this. This post will expand on a point at the end of the post about “modified” functions.

Things are given their names for reasons. Discovering those reasons may help you understand their motivation and use.

Pure math perspective

For each integer n, the modified Bessel function In is essentially the Bessel function Jn evaluated along the imaginary axis. Specifically,

I_n(x) = i^{-n} J_n(ix)

From a certain shallow perspective, that’s the end of the story: modified Bessel functions are modified in the sense that the argument is multiplied by i. And there’s a fiddly constant term up front for no apparent reason.

But of course that’s not the end of the story or else this wouldn’t be worth an entire post.

The equation above is analogous to the relationships between circular and hyperbolic functions

\begin{align*} \sin(ix) &= i \sinh(x) \\ \cos(ix) &= \phantom{i} \cosh(x) \\ \tan(ix) &= \phantom{i} \tanh(x) \end{align*}

These relationships are interesting because the circular and hyperbolic functions are independently meaningful. If you view these equations merely as definitions you lose their significance. Circular and hyperbolic functions were widely used before Euler discovered the connection between them.

Similarly, there’s a reason the modified Bessel functions were given a name their own. If you were led to Bessel functions and modified Bessel functions separately by different applications, you would regard the equation

I_n(x) = i^{-n} J_n(ix)

as a discovery rather than just a definition. The following section explains why someone would be interested in modified Bessel functions.

Before we move on, I’d like to explain the reason for the term i−n term. In general

I_\nu(x) = \exp(\nu\pi i/2) J_n(ix)

for all real ν. The reason for the exp(νπi/2) term is that it makes Iν(x) real for all real x.

Applied math perspective

Bessel functions often arise from solving problems with radial symmetry. Solving the wave equation in cylindrical coordinates using separation of variables leads to Bessel’s differential equation

x^2 y'' + x y' + (x^2 - \nu^2) y = 0

and its solutions Jn and Yn, Bessel functions of the first and second kind.

Solving the heat equation in cylindrical coordinates with separation of variables leads to the modified Bessel equation

x^2 y^{\prime \prime} + x y^{\prime} - (x^2 + \nu^2) y = 0

and its solutions In and Kn, the modified Bessel functions of the first and second kind.

This is the reason behind the complex analysis perspective above: the change of variables sending x to ix changes the sign of the x² term in Bessel’s equation.

Bessel functions describe radially symmetric oscillations, such as the vibrations of a drum head. Modified Bessel functions describe radially symmetric exponential growth or decay [1], such as in the heat in a cylinder.

Other modified functions

Struve functions are closely related to Bessel functions. The (modified) Struve functions also satisfy Bessel’s (modified) differential equation, but with a non-zero right hand side. The modified Struve functions are proportional to the unmodified Struve functions evaluated along the imaginary axis, with a proportionality constant that makes the modified Struve functions real for real arguments.

There’s a similar relationship between the Mathieu functions and modified Mathieu functions. The general pattern is that “modified” in the context of special functions means “evaluated at ix and multiplied by a constant to make the function real for real arguments.”

 

[1] The functions In grow exponentially and the functions Kn decay exponentially. For this reason, A&S didn’t tabulate In and Kn per se. Instead it tabulated e−xIn and exKn because these functions varied less over their range.