# Making ())( not a palindrome anymore – defining “conjugate palindromicity”

One of the top posts on r/Showerthoughts is It’s off-putting that ()() isn’t a palindrome, yet ())( is.

I agree.

The absolute value operator |x| is first taught as “if x is negative, make it positive.” This falls apart with complex numbers. Then |z| is retaught as “multiply z by its conjugate, then take the square root of the result.”

What is “the conjugate of z?” Complex numbers come in conjugate pairs; think of them as opposite sides of the same coin. -1 has two square roots: i and –i. The conjugate of z is the number you get by choosing the other square root. For example, the conjugate of -3 – 4i is -3 + 4i.

In much the same way, English (and other languages) have conjugate symbols. Just as -3 – 4i and -3 + 4i are a conjugate pair, so too are ( and ) a conjugate pair.

The usual definition of a “palindrome” is “a sequence of symbols that reads the same forwards and backwards” which is to say “a sequence that is identical to its own reverse.” The sequence is symmetric under the operation of reversal. With this definition, ()() is not a palindrome, and ())( is. That can’t be right, so the definition is wrong.

The way conjugate symbols work is fundamentally tied to their position in the sequence. A ( at the beginning of the string means the same, in reverse, as a ) at the end of the string. So I make a new definition – conjugate palindromicity. A sequence of symbols is a conjugate palindrome if it is symmetric under the operation of reversal and the replacement of all symbols with their conjugate.

I wrote a PowerShell script which tests strings for both palindromicity and conjugate palindromicity.

Test-Palindrome.ps1

```> .\Test-Palindrome.ps1 "()()"; .\Test-Palindrome.ps1 "())("; .\Test-Palindrome.ps1 "()()" -conjugate; .\Test-Palindrome.ps1 "())(" -conjugate
False
True
True
False```

Under this new definition, happily, ()() is a conjugate palindrome, and ())( is not (as it should not be.)

# Bipartisan-ness of United States presidential impeachment verdicts

• This is the “most bipartisan” impeachment in US history
• This impeachment “brought the most guilty votes” in US history

There have been four impeachment verdicts against United States Presidents by the United States Senate. Here’s the data:

• Andrew Johnson, 1868
• Verdict: not guilty on all counts
• 54 Senators
• 45 Republican
• 9 Democratic
• Vote: 35 guilty, 19 not guilty
• Guilty: 35 Republican
• Not guilty: 10 Republican, 9 Democratic
• Bill Clinton, 1999
• Verdict: not guilty on all counts
• 100 Senators
• 55 Republican
• 45 Democratic
• On the “perjury” count
• 45 guilty, 55 not guilty
• Guilty: 45 Republican
• Not guilty: 45 Democratic, 10 Republican
• On the “obstruction of justice” count
• 50 guilty, 50 not guilty
• Guilty: 50 Republican
• Not guilty: 45 Democratic, 5 Republican
• Donald Trump, 2020
• Verdict: not guilty on all counts
• 100 Senators
• 53 Republican
• 45 Democratic
• 2 Independent
• On the “abuse of power” count
• 48 guilty, 52 not guilty
• Guilty: 45 Democratic, 1 Republican, 2 Independent
• Not guilty: 52 Republican
• On the “obstruction of justice” count
• 47 guilty, 53 not guilty
• Guilty: 45 Democratic, 2 Independent
• Not guilty: 53 Republican
• Donald Trump, 2021
• Verdict: not guilty (on the sole count)
• 100 Senators
• 50 Democratic
• 50 Republican
• 57 guilty, 43 not guilty
• Guilty: 50 Democratic, 7 Republican
• Not guilty: 43 Republican

The “most bipartisan” claim is mostly true though it ignores the role of the two Independent Senators in Donald Trump’s 2020 impeachment verdict.

The “most guilty votes” claim is misleading. Yes, it is technically true that Donald Trump 2021’s 57 guilty votes is more by count than Andrew Johson 1868’s 35 guilty votes – but as a percentage Andrew Johnson’s 65% guilty is higher than Donald Trump 2021’s 57% guilty.

So Andrew Johnson still has the honor of being the President who came closest to being convicted by the Senate.

# How all the United States presidencies have ended

There are lots of ways a United States presidency can come to an end. Let’s look at some of them.

## Did not run for re-election

20 presidents have chosen not to run for re-election when their term expired. (I also include cases where a president sought re-election but was not nominated.)

1. George Washington, 1796
2. Thomas Jefferson, 1808
4. James Monroe, 1824
5. Andrew Jackson, 1836
6. John Tyler, 1844
7. James K. Polk, 1848
8. Millard Fillmore, 1852
9. Franklin Pierce, 1856
10. James Buchanan, 1860
11. Andrew Johnson, 1868
12. Ulysses S. Grant, 1876
13. Rutherford B. Hayes, 1880
14. Chester A. Arthur, 1884
15. Grover Cleveland (second term,) 1896
16. Theodore Roosevelt, 1908
17. Woodrow Wilson, 1920
18. Calvin Coolidge, 1928
19. Harry S. Truman, 1952
20. Lyndon B. Johnson, 1968

## Lost re-election

Eleven presidents have run for re-election but lost. Grover Cleveland later ran again and won.

3. Martin van Buren, 1840
4. Grover Cleveland (first term,) 1888
5. Benjamin Harrison, 1892
6. William Howard Taft, 1912
7. Herbert Hoover, 1932
8. Gerald Ford, 1976
9. Jimmy Carter, 1980
10. George H. W. Bush, 1992
11. Donald Trump, 2020

## Died in office

Eight presidents have died while in office.

1. William Henry Harrison, 1841
2. Zachary Taylor, 1850
3. Abraham Lincoln, 1865
4. James A. Garfield, 1881
5. William McKinley, 1901
6. Warren G. Harding, 1923
7. Franklin D. Roosevelt, 1945
8. John F. Kennedy, 1963

## Exhausted term limits

In 1951 the 22nd amendment to the United States Constitution instituted term limits for the presidency. Five presidents have exhausted those term limits.

1. Dwight D. Eisenhower, 1960
2. Ronald Reagan, 1988
3. Bill Clinton, 2000
4. George W. Bush, 2008
5. Barack Obama, 2016

## Resigned

One president has resigned.

1. Richard Nixon, 1974

## Impeached and removed

Article I of the Constitution lays out a process for impeachment (by the House) and removal (by the Senate) of a president. Impeachment has happened four times, but removal has not happened:

1. Andrew Johnson, 1868 (acquitted)
2. Bill Clinton, 1998 (acquitted)
3. Donald Trump, 2019 (acquitted); 2021 (term ended prior to trial)

## Unable to discharge powers and duties

Article II of the Constitution, as amended in 1967 by the 25th amendment, lays out a process by which the Vice President can become Acting President if the President is “unable to discharge the powers and duties of his office.” This has not happened.

EDIT 2021-01-13: Impeachment has happened four times now.

EDIT 2021-01-20: Donald Trump’s term has officially ended via “lost re-election.”

# Gender identity and sexual attraction, part 3 – vocabulary for attraction in the triangle gender model

Posts in this series:

We can extend much of the continuum vocabulary forward, with careful consideration to agender/genderless and partially gendered people. There will be some ambiguity, and some outright gaps, some of which we will attempt to fill with new vocabulary.

For example:

• Consider neptunic.
• Continuum definition: a person (of any gender) who desires people who are female or nonbinary is neptunic.
• Triangle definition: A person (of any or no gender) who desires people who are female, nonbinary, or agender/genderless, is neptunic.
• Consider mercuric.
• Continuum definition: a person (of any gender) who desires people who are female or male is mercuric.
• Triangle definition: this could extend in two different ways. It could include agender/genderless people, or not. For the purposes of this blog post we will extend it to not include agender/genderless people; this means we need a new term for the other possible extension.
• Consider a person who is attracted only to agender/genderless people. There is no term in the continuum model which would naturally extend to this; we need a new word.
• The continuum model had several words which applied only if the desirer was male, or female, or nonbinary. We need new terms for agender/genderless desirers.

## Terms for attraction by gender of the desired

In addition to all the terms carried forward, we add the following:

Here’s a diagram:

## Terms for attraction if the desirer is agender/genderless

If the desirer is agender/genderless, we add the following terms:

• An agender/genderless person who desires people regardless of gender or lack thereof is dahlian.
• An agender/genderless person who desires agender/genderless people is delphinian.
• An agender/genderless person who desires women is azalian.
• An agender/genderless person who desires men is thistlian.
• An agender/genderless person who desires gendered nonmen is plumerian.
• An agender/genderless person who desires nonbinary people is wisterian.
• An agender/genderless person who desires gendered nonwomen is lilacian.
• An agender/genderless person who desires nonmen is geranian.
• An agender/genderless person who desires nonwomen is irisian.
• An agender/genderless person who desires men or women is orchidian.
• An agender/genderless person who desires agender/genderless and nonbinary people is magnolian.

Here’s a diagram:

The terms magnolian, plumerian, wisterian, and lilacian appear to be lacking non-desirer-gender-specific equivalents. If you know of any, please tell me. I suppose, in the absence of specific terms, a male person who desired female people and nonbinary people could call himself a male plumerian, in the same way that some trixic people call themselves nonbinary lesbians.

Deep breath

(hands over ears)

OMG

SO MANY WORDS

SEX IS SUPPOSED TO BE FUN

I feel a bit like J. Evans Pritchard, Ph. D. I have drowned human love in a sea of vocabulary and stretched it out to dry on mathematical axes. Please rip out these blog posts and go read a good love story.

but anyway

… those are some of the labels for people (perhaps of a particular gender, or perhaps not) who desire other people in particular combinations of genders.

It is likely that this post contains mistakes. If you find any please let me know.

# Gender identity and sexual attraction, part 2 – vocabulary for attraction in the continuum gender model

Posts in this series:

Some words are used to describe desire for particular genders, regardless of the gender of the desirer:

## Terms for attraction by gender of the desired

People whose desire is not defined by the gender of the desired:

• A person (of any gender) who desires people of all genders is pansexual or omnisexual.
• The binary model used bisexual for people who fit this definition. But since there are more than two genders, the bi- prefix doesn’t really fit here anymore.
• A person (of any gender) who does not desire people is asexual.

People who desire one gender in particular:

• A person (of any gender) who desires people who are female is venusic or womasexual.
• A person (of any gender) who desires people who are male is marsic or masexual.
• A person (of any gender) who desires people who are nonbinary is ceterosexual or enboric or stellaric. The term skoliosexual is now frowned upon because skolios can mean “crooked.” Allotroposexual is another potential alternative.

People who desire some specific combination of genders:

• A person (of any gender) who desires people who are female or nonbinary is neptunic.
• A person (of any gender) who desires people who are male or nonbinary is uranic.
• A person (of any gender who desires people who are female or male is mercuric.
• The binary model used bisexual for people who fit this definition too. So in the new model, bisexual is ambiguous. Best not to use it.

Here’s a diagram:

There are also terms which are specific to the gender of the desirer.

## Terms for attraction if the desirer is male

If the desirer is male additional terms can be used:

• A male who desires people regardless of gender is astronic or marblic.
• A male who desires people who are female is mlw or straight.
• A male who desires people who are female or nonbinary is litian.
• A male who desires people who are male is achillean, gay, hyacique, mlm, vincian, or wildean although achillean is frowned upon by some because of Achilles’ non-consensual relationship with his slave-woman Briseis.
• A male who desires people who are nonbinary is asteroidian, astroidian, or mlnb.
• A nonbinary male who desires people who are female is umbalian.
• A nonbinary male who desires people who are male is azurian.

Here’s a diagram:

## Terms for attraction if the desirer is female

If the desirer is female additional terms can be used:

• A female who desires people who are female is lesbian or sapphic or wlw.
• A female who desires people who are female or nonbinary is agatic.
• A female who desires people who are male is straight or wlm.
• A female who desires people who are male or nonbinary is citrinian.
• A female who desires people who are nonbinary is asterian or wlnb.

Here is a diagram:

## Terms for attraction if the desirer is nonbinary

Here is a diagram:

Okay that’s a lot of words.

Next time… even more words. Sorry.

It is likely that this post contains mistakes. If you find any please let me know.

# Gender identity and sexual attraction, part 1 – models for gender identity

Posts in this series:

Last time I presented a couple of flowcharts for sexual attraction. But they weren’t really adequate. So let’s dig into gender identity a little.

To set the tone, here is Irving Kaufman singing Edgar Leslie and James Monaco’s 1925 song “Masculine Women! Feminine Men!”

I present three models for gender identity.

It’s important to realize that these are just models. We’re going to try to use them to describe people, but the people are the important thing – not the model. If a real person and an artificial model don’t fit together, it is the model that is at fault, not the person.

## Binary model

The binary model I grew up with admits of only two genders. It is useful only as a starting point for further development.

We can express this mathematically as G2 = {♀, ♂}. We can define some labels:

• A female person has gender ♀.
• A male person has gender ♂.

Ugh. Surely we can do better than this.

## Continuum model

The continuum model extends the binary model by creating a continuous spectrum of genders between the two genders in the binary model. This allows for more meaningful discourse but is still flawed.

We can express this mathematically as Gc = { (1 − λ)♀ + λ♂ | λ ∈ [0, 1] }. λ tells us the relative position of the gender compared to the binary genders ♀ and ♂. The model reduces to G2 in the case where λ ∈ {0, 1}.

We can define some labels:

• A female person has λ near 0.
• A male person has λ near 1.
• A nonbinary person has λ away from 0 and 1.

The Galactian Alignments system allows for gender alignment of nonbinary people:

• A female-aligned nonbinary person is lunarian.
• A male-aligned nonbinary person is solarian.
• A non-aligned nonbinary person is stellarian.

Here’s the same diagram showing the labels.

That’s a little better.

## Triangle model

The triangle model extends the continuum model by adding a notion of gender saturation:

To express this mathematically we introduce ⚪ – meaning agender/genderlessness – and identify it with 0. We define the triangle GΔ = { κ((1 − λ)♀ + λ♂) | κ, λ ∈ [0, 1] }. κ is the degree of gender saturation. This reduces to the continuum model Gc in the case where κ = 1.

New definitions:

• A gendered person has κ near 1.
• An agender/genderless person has κ near 0.
• A partially gendered person has κ away from 0 and 1.
• A female person has (λ, κ) near (0, 1).
• A male person has (λ, κ) near (1, 1).

Here’s the same diagram showing the labels:

Better still.

Now, even this model is flawed – for example, it doesn’t fit with genderfluid or bimodal people – but I’ll stop here for the sake of space.

It is likely that, even as far as it goes, this post contains mistakes. If you find any please let me know.

Exercise: are agender/genderless people nonbinary?

# Some sexual identification flowcharts

Here’s a sexual identification flowchart I made based on the binary gender model I grew up with:

This is inadequate because it does not acknowledge the existence of:

• People who are neither simply “male” nor simply “female”
• People who don’t want to have sex

So I made an updated version:

That’s a little better. But I like this one best of all:

Next time, more on the “this gets interesting” bit.

# Hacking private keys from unsafe primes using the Pohlig-Hellman discrete logarithm

I’ve talked a few times about ElGamal encryption, where a participant A has a private key a and a public key ga mod p for some public prime p and generator g.

Now let’s suppose we’re an attacker and we’re after A‘s private key. We know her public key ga, we know g, and we know p. Can we figure out a = logg ga mod p? This is called the “discrete logarithm problem.”

## Brute force

If p is extremely small or we are extremely patient we can do it very easily. Start with 1 = g0. Multiply by g to get g. Multiply again to get g2 mod p. Multiply a third time to get g3 mod p. Keep going until you get ga. Then a is just the number of times you had to multiply.

For example, consider implementing ElGamal encrypt, decrypt, sign, and verify signature. In this toy example p = 101, g = 2, A‘s private key was 57, and her public key was 257 mod 101 = 74. Since we (as the attacker) know g and p we can just calculate, doubling as we go, and subtracting 101 when we can:

• 20 mod 101 = 1
• 21 mod 101 = 2
• 22 mod 101 = 4
• 26 mod 101 = 64
• 27 mod 101 = 27
• 28 mod 101 = 54
• 256 mod 101 = 37
• 257 mod 101 = 74

So log2 74 = 57 mod 101 and now we know A‘s private key.

This approach takes O(p) time so it quickly becomes impractical as p gets big.

## Baby-step giant-step

I blogged earlier about a speed improvement: David Shanks’ baby-step/giant-step algorithm. The basic idea is to precompute gi mod p only up to s = ⌈√p⌉ and then store them in a lookup table. Then use a little algebra to query the lookup table up to s times. This takes O(√p) time and space so it can let us squeeze out a little more juice but as √p gets big too this also becomes impractical.

## Pohlig-Hellman

Stephen Pohlig and Martin Hellman (yes, that Hellman) published their algorithm for taking discrete logarithms which works by analyzing the group Zpx.

The group has p – 1 elements {1, 2, …, p – 1}. (Note that 0 is not included.) This means that the order of the subgroup generated by any given element divides p – 1.

Factor p – 1 as a product of powers of primes: p – 1 = p1k1 p2k2pnkn.

To calculate y = logg x mod p:

1. Calculate y mod p1k1 (more on this later)
2. Calculate y mod p2k2
3. Calculate y mod pnkn
4. Use the Chinese Remainder Theorem to reassemble y from its various modular residues.

That’s all well and good, but how do we calculate y mod piki?

Let q = pi and let k = ki. The trick to the algorithm is to realize that y mod qk can be written in base q as y0 + y1 q + y2 q2 + … + yk – 1 qk – 1. Each of the yi is a number in {0, 1, …, q – 1} and can be evaluated in O(√q) time and space using a little algebra, e.g. the fact that g(p – 1)/q is an element of order q.

So even if p is big, if p – 1 has all small prime factors, private keys can be extracted from public keys very quickly!

I wrote up an implementation of Pohlig-Hellman in PowerShell and tested it out.

First I found a (p – 1, p) pair where p was reasonably big and p – 1 had all small prime factors:

```> cd pohlig-hellman
> .\find-unsafe-prime.ps1 -n 10000000
Sieving primes up to 10000000 + 1...
Finding largest small prime and the product of small primes from 100000000000000 to 100000020000000
Finding the prime between 100000000000000 and 100000020000000 with the smoothest p - 1
Prime 100000008359681 is one more than a number whose biggest prime factor is 53
> \$p = [bigint]::Parse("100000008359681")
> \$p
100000008359681 ```

100000008359681 is prime, and 100000008359680 = 28 5 112 13 19 31 37 43 53 has only small prime factors.

Then I found a generator:

```> .\find-generator.ps1 -p 100000008359681
2^((100000008359681 - 1)/2) mod 100000008359681 = 1, rejecting 2
3^((100000008359681 - 1)/5) mod 100000008359681 = 1, rejecting 3
4^((100000008359681 - 1)/2) mod 100000008359681 = 1, rejecting 4
5^((100000008359681 - 1)/2) mod 100000008359681 = 1, rejecting 5
6 passes all checks
> \$g = [bigint]::Parse("6")
> \$g
6```

Then I (arbitrarily) picked public key 6a = 2 mod 100000008359681. Now I have enough to calculate the discrete logarithm to find the private key a.

Actually, √p is still small enough that baby-step giant-step can crack this logarithm directly, but it is slow. On my machine it finds log6 2 = 67708279093016 mod 100000008359681 in a little over eleven minutes:

```> cd baby-step-giant-step
> Measure-Command { .\baby-step-giant-step.ps1 -p \$p -g \$g -x 2 }
Find y so that 6^y = 2 mod 100000008359681
log_6 2 mod 100000008359681 = 67708279093016
6^67708279093016 mod 100000008359681 = 2
...
TotalMinutes      : 11.3536922983333
...```

By comparison, Pohlig-Hellman finds the same logarithm on the same machine in less than one-tenth of a second:

```> cd pohlig-hellman
> Measure-Command { .\pohlig-hellman.ps1 -p \$p -g \$g -x 2 }
log_6 2 = 67708279093016 mod 100000008359681
6^67708279093016 = 2 mod 100000008359681
...
TotalMilliseconds : 74.797
...```

# Solving x = r₁ mod m₁, x = r₂ mod m₂, … x = rₙ mod mₙ using the Chinese Remainder Theorem

Suppose we have an unknown number of objects. When counted in threes, 2 are left over, when counted in fives, 3 are left over, and when counted in sevens, 2 are left over. How many objects are there?

Sunzi Suanjing, 3rd to 5th century CE

I coded up a PowerShell implementation of the Chinese Remainder Theorem which solves sets of simultaneous modular equations like this. The above story problem can be translated as:

Find x that satisfies the following modular equations:

• x = 2 mod 3
• x = 3 mod 5
• x = 2 mod 7

The answer it comes up with is 23:

```> .\chinese-remainder-theorem.ps1 -moduli (3, 5, 7) -remainders (2, 3, 2)
23```

Checking, this does indeed meet the criteria:

• 23 = 3(7) + 2 = 2 mod 3
• 23 = 5(4) + 3 = 3 mod 5
• 23 = 7(3) + 2 = 2 mod 7

Actually, combining the equations only tells us that x = 23 mod 105. There are infinitely many such x, in particular 23, 128, 233, 338, …. The general term is 23 + 105n.

# How safe is the prime 2²⁵⁵ – 19?

A while back we talked about safe primes and unsafe primes and we gave some small examples of safe primes and unsafe primes.

Recap: A has a secret key a and a public key (ga mod p) with a known prime p and generator g. It is crucial that an attacker not be able to take the discrete logarithm a = logg ga mod p. If they could do that, the attacker would have A‘s private key, without even having to eavesdrop on any communications!

The Pohlig–Hellman algorithm allows an attacker to perform this discrete logarithm. It takes time proportional to the largest prime factor of p – 1. So if p – 1’s prime factors are all small, the attacker can extract private keys easily from public keys. But if there is at least one large prime factor of p – 1, then we’re OK; the larger, the better.

So the unsafest primes are the Fermat primes where p = 2n + 1 for some n. The largest prime factor of p – 1 is only 2!

The safest primes are those of the form p = 2q + 1 where q is a Sophie Germain prime. The largest prime factor of p – 1 is (p – 1) / 2 = q.

How safe is the prime p = 2255 – 19 = 57896044618658097711785492504343953926634992332820282019728792003956564819949? Let’s factor p – 1 and see.

p – 1 = 2255 – 19 – 1 = 2255 – 20 is divisible by 2 – and even by 4 – but not by 8. So we have p – 1 = 22(2253 – 5). So far so good.

What about 2253 – 5? It’s NOT divisible by 5. What about by 3?

With a little bit of thought we can see that it is divisible by 3. 2 = -1 mod 3 and 5 = -1 mod 3, so substituting we have 2253 – 5 = (-1)253 – (-1) = -1 – (-1) = 0 mod 3. (2253 – 5)/3 doesn’t seem to have a nice concise form but we can just write it out in full.

So far we have p – 1 = 22 3 4824670384888174809315457708695329493886249361068356834977399333663047068329. What about 4824670384888174809315457708695329493886249361068356834977399333663047068329?

A quick poke at it with Miller-Rabin shows that it is NOT prime but does not offer a hint as to any factors. So we turn to brute-force trial division and after some time we find that it is divisible by 65147.

So far we have p – 1 = 22 3 65147 74058212732561358302231226437062788676166966415465897661863160754340907. What about 74058212732561358302231226437062788676166966415465897661863160754340907?

Miller-Rabin suggests that this COULD BE prime. In fact, it is prime. Here’s a proof.

The largest prime factor of p – 1 is pretty big. So p is pretty safe. Good.

We also have to take care when choosing a generator not to fall into any of the small cycles of length 2a 3b 65147c with a ∈ {0, 1, 2}, b ∈ {0, 1}, c ∈ {0, 1}.