February 2012 archive
Further adventures in
Walter
Mitty legislation:
Wyoming House Bill 85 would provide for "a task force to study governmental continuity in case of a disruption in federal government operations". On Friday, the Wyoming House passed an amendment to HB0085 directing the task force to study "Conditions under which the state of Wyoming should implement a draft, raise a standing army, marine corps, navy and air force and acquire strike aircraft and an aircraft carrier."
Only nine countries have aircraft carriers.
Russia, India, Brazil, France, and the UK have one aircraft carrier each.
Wyoming is the least populous of the 50 states and is 600+ miles from the nearest ocean.
State Representative Lorraine Quarberg (R-Thermopolis) said, "To put your head in the sand and think that nothing bad's going to happen, and that we have no obligation to the citizens of the state of Wyoming to at least have the discussion, is not healthy."
Bear with me today while, rather than writing anything original,
I post a pic of a scene at Stanford University after the 1906 earthquake.
"Agassiz was great in the abstract but not in the concrete."
For communication with RSA to be secure, you want to pick two prime numbers that no one else is using. As the primes used in RSA are so large, picking primes at random will suffice. That is, there are so many 512-bit primes that it's unlikely to pick the same prime twice at random, even among millions of users.
The crux is in the words at random. Generating random bits independently every time is crucial, and it doesn't come naturally to most computer equipment—which is, after all, designed to operate determinisically rather than randomly. Randomness is obtainable, but you have to know what you're doing.
Although factoring a large enough number is intractable, checking two such numbers for a common factor is not, and to find a common factor of two RSA public keys is to render both keys insecure. Research made public last week examined millions of published RSA keys and found enough instances of common factors to show that some encryption devices are not generating prime numbers randomly enough. These findings got a fair amount of media attention, but neither the paper itself nor most news articles on it discussed just how to find common factors in a pool of millions of large numbers.
A common factor of two numbers can be found with one of the oldest algorithms still in wide use: the Euclidean algorithm. You can turn it loose on a pair of 1024-bit RSA keys and get an answer in well under a second, but checking each of six million keys against all the others could take years of computer time. A faster method for the purpose is described here.
I'm struck by how it took until now for the prevalence of common factors to be publicized. The researchers put it like this: "The lack of sophistication of our methods and findings make it hard for us to believe that what we have presented is new, in particular to agencies and parties that are known for their curiosity in such matters."
Should Tommyjournal fail to appear, fear not, as it should return ere long. Thanks in advance for your patience.
Continuing the pattern from
last month's fourth,
the subject is math.
Our understanding of numbers is influenced by our familiarity with place value notation in general and decimal notation in particular. Place value offers all kinds of computational advantages; it's not an accident that we use it. But it is not the only game in town.
For all its benefits, place value can make numbers look more complicated than they are. Fractional notation sometimes makes the nature of numbers more obvious. Whereas 1/7 exactly represents a rational number, the decimal equivalent not only repeats infinitely but its repeating pattern 142857 is more cumbersome than the numerator and denominator in 1/7.
√7 ≈ 2.6457513. In decimal (or any place-value notation), an irrational square root of an integer looks like what might as well be random digits.
But successively more accurate rational approximations to √7 are not random in their form, even if the pattern is not immediately evident:
√7 ≈ 2 + 9/14
√7 ≈ 2 + 144/223
√7 ≈ 2 + 2295/3554
√7 ≈ 2 + 36576/56641
Each of those approximations is the best obtainable for the size of its denominator. E.g., 37/14 is the closest rational number to √7 whose denominator is no greater than 14.
Okay, but what's the pattern. The numerators and denominators in those fractions appear in the right columns of powers of a certain 2×2 matrix:
1/7 can't be written as a finite decimal, but to know 142857
is to know how to form decimals that approximate 1/7 to any
desired degree of accuracy.
√7 is irrational, but to know the numbers 2, 3, 9, 14 is to know how to form fractions that approximate √7 to any desired degree of accuracy. (Admittedly, multiplying matrices entails more work than replicating decimal patterns.)
Why a 2×2 matrix? It's a convenient way of bundling the repeating terms in the continued fraction representation of a square root.
Any rational number has a decimal representation ending with a repeating pattern.
The square root of any integer has a corresponding 2×2 integer matrix whose powers construct its best rational approximations.
So although √2, √3, √5, √6, √7, ... are not the quotients of integers, they are more approachable with integers than they might seem.
A few words about why I avoid Facebook.
With all due respect to those who find it useful, I am not keen to see one company gathering and controlling so much of the attention and time people spend online. I find it contrary to the spirit of the open, egalitarian project that was the WWW.
I admit my bias: commercialism irks me more than it does most people. That's partly just my nature, and partly having become accustomed to living in a rural area where day-to-day life does not entail seeing the barrage of signs and ads that are in one's field of view on city streets.
Facebook's S-1 registration statement includes a letter from Mark Zuckerberg, where he says, "we don't build services to make money; we make money to build better services." We'll see how long that lasts, what with how particular shareholders can be about making money.
And Facebook just rubs me the wrong way. I find their logo ugly. I don't like the look and feel of their pages. I don't like ready-made templates for interaction with people. There's more, but I'll stop here in the interest of not rattling on at length about things I don't like.
Facebook's S-1 filing includes 53 pics of employees holding notes saying thank you "to the millions of you who made this possible".
Wyoming House Bill 85 would provide for "a task force to study governmental continuity in case of a disruption in federal government operations". On Friday, the Wyoming House passed an amendment to HB0085 directing the task force to study "Conditions under which the state of Wyoming should implement a draft, raise a standing army, marine corps, navy and air force and acquire strike aircraft and an aircraft carrier."
Only nine countries have aircraft carriers.
Russia, India, Brazil, France, and the UK have one aircraft carrier each.
Wyoming is the least populous of the 50 states and is 600+ miles from the nearest ocean.
State Representative Lorraine Quarberg (R-Thermopolis) said, "To put your head in the sand and think that nothing bad's going to happen, and that we have no obligation to the citizens of the state of Wyoming to at least have the discussion, is not healthy."
At right: a recently declassified 1955 letter from the NSA to John Nash.
Do people who write such letters end up using the passive voice all the time? When ordering food, do they say "the steak would be liked"? Nash's thoughts on ciphers are discussed on Turing's Invisible Hand. |
"Agassiz was great in the abstract but not in the concrete."
 |
public domain image. another view here.
In setting up RSA encryption, one picks two large prime numbers and keeps them secret but makes their product public. The security of RSA—used extensively in web commerce—depends on the difficulty of factoring such a product.
For communication with RSA to be secure, you want to pick two prime numbers that no one else is using. As the primes used in RSA are so large, picking primes at random will suffice. That is, there are so many 512-bit primes that it's unlikely to pick the same prime twice at random, even among millions of users.
The crux is in the words at random. Generating random bits independently every time is crucial, and it doesn't come naturally to most computer equipment—which is, after all, designed to operate determinisically rather than randomly. Randomness is obtainable, but you have to know what you're doing.
Although factoring a large enough number is intractable, checking two such numbers for a common factor is not, and to find a common factor of two RSA public keys is to render both keys insecure. Research made public last week examined millions of published RSA keys and found enough instances of common factors to show that some encryption devices are not generating prime numbers randomly enough. These findings got a fair amount of media attention, but neither the paper itself nor most news articles on it discussed just how to find common factors in a pool of millions of large numbers.
A common factor of two numbers can be found with one of the oldest algorithms still in wide use: the Euclidean algorithm. You can turn it loose on a pair of 1024-bit RSA keys and get an answer in well under a second, but checking each of six million keys against all the others could take years of computer time. A faster method for the purpose is described here.
I'm struck by how it took until now for the prevalence of common factors to be publicized. The researchers put it like this: "The lack of sophistication of our methods and findings make it hard for us to believe that what we have presented is new, in particular to agencies and parties that are known for their curiosity in such matters."
 | I
was in Colorado for work this week. My travels took me through the
Vegas airport, which is getting a new tower (hereafter: twr).
People at the Vegas airport evidently march to a different drummer than the rest of the town. That is to say, new construction at LAS exhibits good taste that I normally wouldn't expect from Vegas; e.g., Terminal D has brass aeronautical chart symbols embedded in the terrazzo floor and has rad sculptures of desert animals. And although I reserve judgment on this new twr until it's done, so far it looks to be nicer than the bland twr at DEN (which is just like the bland twr at IAH). | |
I flew on Allegiant Air today, which Wikipedia told me has a replica of an MD-80 tail as the front desk at their Vegas headquarters, which I just had to see in person, and which their receptionist was kind enough to let me photograph: |
 |
| On the way home, I stopped at the made-famous-by-the-U2-album-cover Joshua tree (now dead and toppled) around sundown, when the light is at the angle I wanted for photographing the plaque fans put in the ground nearby: |
 |
| To find the tree: park at mile marker 33 (the distance is referred to the junction with US 395) on California route 190 and walk 400 meters south. |
 |
 |
| virga in the sun against mountains in the shade |
Other nations routinely trade in their constitutions wholesale, replacing them on average every 19 years. By odd coincidence, Thomas Jefferson, in a 1789 letter to James Madison, once said that every constitution "naturally expires at the end of 19 years" because "the earth belongs always to the living generation." - NY Times"by odd coincidence". Tommyjournal (and my pages at minortriad.com) will probably be moving to different web server machine soon. I'm hoping for little or no interruption of service, but that depends on how my hosting provider does their job and how DNS changes propagate: both not under my control.
Should Tommyjournal fail to appear, fear not, as it should return ere long. Thanks in advance for your patience.
Nice day today.
I climbed four new routes and I heard someone use the word caltrop in a sentence for the first time, or — as my memory may be faulty — for what at least felt like the first time, which is really just as good. |
Our understanding of numbers is influenced by our familiarity with place value notation in general and decimal notation in particular. Place value offers all kinds of computational advantages; it's not an accident that we use it. But it is not the only game in town.
For all its benefits, place value can make numbers look more complicated than they are. Fractional notation sometimes makes the nature of numbers more obvious. Whereas 1/7 exactly represents a rational number, the decimal equivalent not only repeats infinitely but its repeating pattern 142857 is more cumbersome than the numerator and denominator in 1/7.
√7 ≈ 2.6457513. In decimal (or any place-value notation), an irrational square root of an integer looks like what might as well be random digits.
But successively more accurate rational approximations to √7 are not random in their form, even if the pattern is not immediately evident:
√7 ≈ 2 + 9/14
√7 ≈ 2 + 144/223
√7 ≈ 2 + 2295/3554
√7 ≈ 2 + 36576/56641
Each of those approximations is the best obtainable for the size of its denominator. E.g., 37/14 is the closest rational number to √7 whose denominator is no greater than 14.
Okay, but what's the pattern. The numerators and denominators in those fractions appear in the right columns of powers of a certain 2×2 matrix:
 |
√7 is irrational, but to know the numbers 2, 3, 9, 14 is to know how to form fractions that approximate √7 to any desired degree of accuracy. (Admittedly, multiplying matrices entails more work than replicating decimal patterns.)
Why a 2×2 matrix? It's a convenient way of bundling the repeating terms in the continued fraction representation of a square root.
Any rational number has a decimal representation ending with a repeating pattern.
The square root of any integer has a corresponding 2×2 integer matrix whose powers construct its best rational approximations.
So although √2, √3, √5, √6, √7, ... are not the quotients of integers, they are more approachable with integers than they might seem.
A couple days ago, a
posting on Giles' blog
touched on the delights of cover art for early-20th-century sheet music.
That makes me wanna post one of my favorites, from the first edition of Bartók's Three Burlesques for piano, published in 1912. The art was drawn by Ervin Voit, a cousin of Bartók's. |
With all due respect to those who find it useful, I am not keen to see one company gathering and controlling so much of the attention and time people spend online. I find it contrary to the spirit of the open, egalitarian project that was the WWW.
I admit my bias: commercialism irks me more than it does most people. That's partly just my nature, and partly having become accustomed to living in a rural area where day-to-day life does not entail seeing the barrage of signs and ads that are in one's field of view on city streets.
Facebook's S-1 registration statement includes a letter from Mark Zuckerberg, where he says, "we don't build services to make money; we make money to build better services." We'll see how long that lasts, what with how particular shareholders can be about making money.
And Facebook just rubs me the wrong way. I find their logo ugly. I don't like the look and feel of their pages. I don't like ready-made templates for interaction with people. There's more, but I'll stop here in the interest of not rattling on at length about things I don't like.
Facebook's S-1 filing includes 53 pics of employees holding notes saying thank you "to the millions of you who made this possible".
