Just days after the 2004 election, two Midwest politicians who seem as publicly diverse in politics and persona as any two of the breed can be exchanged private messages that violated the shrill principles of partisan name-calling and political negativity that have made Washington what it is today.

Barack Obama, the dark-haired Democratic freshman from Illinois whose face was on the cover of Newsweek before his posterior was in his Senate chair, wanted to talk with Sen. Richard Lugar, the snow-haired Republican icon from Indiana who chairs the Senate Foreign Relations Committee. Obama wanted to explore the possibility of serving on Lugar’s panel.

Lugar, meanwhile, had just sent Obama a letter of congratulations in which he encouraged Obama to join his committee. The Indiana veteran was motivated by more than just good-neighbor policy. Obama had campaigned by strongly supporting the Nunn-Lugar program, co-authored in 1991 by then-Sen. Sam Nunn, D-Ga., and Lugar to secure and destroy vulnerable former Soviet nuclear, chemical and biological weapons _ before terrorists steal or buy them on the black market.

The message swap led to a Washington odd-coupling that may be as close to a beautiful friendship as things get here in Casablanca-on-the-Potomac. Obama, whose father was from Kenya and mother from Kansas, arrived in Washington (via Harvard Law School) with a media entourage befitting a Hollywood celebrity. When Lugar, quiet-spoken former Rhodes scholar, arrived in the Senate (Obama was age 15 at the time), he too had a reputation that preceded him. Back home in Indianapolis, Lugar was known as Richard Nixon’s favorite mayor. So as freshmen, they both had some things to live down.

Obama is clearly savvy enough to know that celebrity media treatment is no way to win Washington friends nor influence senators. So he strives to underplay his stardom. Especially when in the presence of his chairman.

And that turns out to be quite often. For Lugar has taken Obama under his wing, onto his jet plane and into his confidence in ways that are rare in Washington under any circumstances _ and which border on the unprecedented given their political divergence. In August, they traveled together to Russia, Ukraine and Azerbaijan.

“I very much feel like the novice and pupil,” Obama told Chicago Tribune correspondent Jeff Zeleny (who is chronicling with a keen eye his home-state senator’s first year) as their plane traversed the Russian interior. Zeleny also noted that in Ukraine, Obama referred on several occasions to “The Ukraine,” even though (as State Department guidelines, Lugar and, of course, their hosts know) the “The” had gone the way of the old Soviet empire.

In Russia, Lugar and Obama toured sites of nuclear, biological and conventional weapons _ and were detained for three hours by Russian authorities at the Perm airport who acted as though they were back in the bad old days of the Cold War. In Donetsk, Ukraine, they saw what looked like a junk yard, but was in fact a poorly secured arsenal of thousands of tons of live munitions, land mines and shoulder-fired antiaircraft missiles.

Back in Washington, Lugar and Obama introduced a bill creating a new program designed to bring the principles of the Nunn-Lugar program to efforts to at least secure conventional weapons such as those shoulder-fired antiaircraft missiles by which a terrorist could down a jetliner. This is a homeland-security sort of bill that America urgently needs to become law.

Lugar and Obama cleverly titled their bill: “Cooperative Proliferation Detection, and Interdiction Assistance and Conventional Threat Reduction Act.” If you think this is a title only a senator can love, you are right. But perhaps you haven’t figured out why. It is because these senators know how Washington works: After the bill passes, we will all simply call it the “Lugar-Obama program.”

“Lugar-Obama.” Not only is it a fitting tribute for the Senate’s new Odd Couple, but it is legislative shorthand that virtually rolls off the tongue. Except perhaps for one silver-tongued, white-haired senator for whom that name did pose a certain degree of difficulty. No, not Dick Lugar, but Ted Kennedy.

In a National Press Club speech earlier this year, the Massachusetts Democrat tried to say something nice about his young colleague from Illinois. But somehow he put his own tongue into light bondage as he paid tribute to: “Osama bin … uh, Osama …” _ mercifully, just before stage terror set in, he got there _ “Obama!”

(Martin Schram writes political analysis for Scripps Howard News Service. E-mail him at martin.schram(at)gmail.com.)