Maths

[Harry]

Got any questions about maths? You have a huge community of experts on this forum, so why not ask them here. No coursework help though!

[madness]

Here’s some cryptographic maths for you:

Suppose we take the rows of a tableau from a polyalphabetic substitution cipher as a set,
and define a binary operation among them by finding the encryption of one using the other as
a key in a monoalphabetic substitution. Turns out it’s commutative and associative. Of course,
I only checked one or two examples, but that’s proof enough, right?

It should be no surprise that the rows of the Vigenere cipher with this binary operation is
isomorphic to Z mod 26 with addition. After all, each row is the key of a Caesar shift cipher.
The identity is the key in row A.

[An isomorphism is a map from one set to another such that map(x+y) = map(x)+map(y), where “+”
denotes the binary operator, which might not be addition. In other words, the structure of the
thing is the same after the mapping. Here, I’m saying that these substitution keys with the
binary operation defined as letting one act on the other in a substitution cipher has the same
structure as the set of integers {0,…,25} with addition modulo 26.]

What might be surprising is that it appears that the rows of a quagmire 3 tableau also form
a group isomorphic to Z26. However, they are not in the same order as with the Vigenere.
The identity is still ABCDEFGHIJKLMNOPQRSTUVWXYZ, but it appears in the row labeled by the
first letter of the keyword. Let’s try this example, generated from the keyword KEYWORD:

a JLMIBNPQSTAUVXGZKHEYWOFRCD
b LMNJCPQSTUBVXZHKEIYWORGDFA
c MNPLFQSTUVCXZKIEYJWORDHAGB
d IJLHAMNPQSDTUVFXZGKEYWCOBR
e BCFAYGHIJLEMNPRQSDTUVXOZWK
f NPQMGSTUVXFZKEJYWLORDAIBHC
g PQSNHTUVXZGKEYLWOMRDABJCIF
h QSTPIUVXZKHEYWMORNDABCLFJG
i STUQJVXZKEIYWONRDPABCFMGLH
j TUVSLXZKEYJWORPDAQBCFGNHMI
k ABCDEFGHIJKLMNOPQRSTUVWXYZ
l UVXTMZKEYWLORDQABSCFGHPINJ
m VXZUNKEYWOMRDASBCTFGHIQJPL
n XZKVPEYWORNDABTCFUGHIJSLQM
o GHIFRJLMNPOQSTBUVCXZKEAYDW
p ZKEXQYWORDPABCUFGVHIJLTMSN
q KEYZSWORDAQBCFVGHXIJLMUNTP
r HIJGDLMNPQRSTUCVXFZKEYBWAO
s EYWKTORDABSCFGXHIZJLMNVPUQ
t YWOEURDABCTFGHZIJKLMNPXQVS
u WORYVDABCFUGHIKJLEMNPQZSXT
v ORDWXABCFGVHIJELMYNPQSKTZU
w FGHCOIJLMNWPQSATUBVXZKDERY
x RDAOZBCFGHXIJLYMNWPQSTEUKV
y CFGBWHIJLMYNPQDSTAUVXZRKOE
z DABRKCFGHIZJLMWNPOQSTUYVEX

The identity is k. The element that is its own inverse (maps to 13 in Z26 under the isomorphism) is i:
Sub(STUQJVXZKEIYWONRDPABCFMGLH,STUQJVXZKEIYWONRDPABCFMGLH) = ABCDEFGHIJKLMNOPQRSTUVWXYZ
The other elements have order 13 or 26, meaning that if you find x^13 or x^26 using the binary operation
defined above, then for some x^13 = identity, and for others x^26 = identity. And the inverse of each
key is also in the tableau.

This doesn’t work for quagmires 1, 2, and 4.

Can this help to identify a cipher from its key? Here is the key tableau from 2018 challenge 10B:

1 DCEOFGIAJKLMNPWQRTHUVXBYZS
2 TYZUSHARDOWBCEVFGIQJKLXMNP
3 WFGBIJKOLMNPQRCTUVDXYZESHA
4 GLMINPQFRTUVXYJZSHEADOKWBC
5 IMNJPQRGTUVXYZKSHAFDOWLBCE
6 YADZOWBXCEFGIJSKLMVNPQHRTU
7 CIJEKLMBNPQRTUFVXYWZSHGADO

If we let 1 operate on 4 we get 5: Sub(GLMINPQFRTUVXYJZSHEADOKWBC,GLMINPQFRTUVXYJZSHEADOKWBC) = IMNJPQRGTUVXYZKSHAFDOWLBCE.
Key 2 times key 4 gives the identity, so they are inverses of each other.
Key 2 times 5 is 1.
Key 3 times 7 is 4.
Key 5 times 6 is 7.
Key 6 times 7 is 1.
(key 1)^26 = ABCDEFGHIJKLMNOPQRSTUVWXYZ = identity
(key 2)^13 = identity
(key 3)^26 = identity
(key 4)^13 = identity
(key 5)^26 = identity
(key 6)^13 = identity
(key 7)^26 = identity

Looks like we have part of a quagmire 3 tableau. If we hadn’t already figured that out in 2018,
this analysis could have told us.

I think that the mapping from the tableau to Z26 might give some information about the keywords,
but so far all I can see is that we can get the first letter of one of them.

Ah, the nurse is coming with my meds. Time for me to log off.

[BreakTheCipher]

I came across this forum post for computing the sum of primes, but I’m not really sure how it works? Could anyone explain this to me because I don’t really understand this.

This was the post:

“The main idea is as follows: Let S(v,m) be the sum of integers in the range 2..v that remain after sieving with all primes smaller or equal than m. That is S(v,m) is the sum of integers up to v that are either prime or the product of primes larger than m.

S(v, p) is equal to S(v, p-1) if p is not prime or v is smaller than p*p. Otherwise (p prime, p*p<=v) S(v,p) can be computed from S(v,p-1) by finding the sum of integers that are removed while sieving with p. An integer is removed in this step if it is the product of p with another integer that has no divisor smaller than p. This can be expressed as

S(v,p)=S(v,p−1)−p(S(v/p,p−1)−S(p−1,p−1)).”

[Rhydwen]

I’ve worked through an example and think I can understand the statement, but I haven’t gained any great insight. I’d welcome any additional comments from a mathematician. Here are my numbers – I hope they are correct.

To generate a list of primes up to v by sieving, a list of all integers up to v would need to be sieved by all integers up to and including the square root of v. Sieving the set of all prime numbers up to 100 by all integers up to 10 gives the set: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. The sum of these numbers is: 1060.

The set of the integers less than 100, incompletely sieved by all numbers up to and including 5 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97. This list includes all the prime numbers (as above) plus the following numbers which are not prime: 49, which is 7 x 7, 77, which is 7 x 11 and 91, which is 7 x 13. S(100, 5) The sum of these numbers is: 1277.

Regarding “S(v, p) is equal to S(v, p-1) if p is not prime or…” The set of the sieved numbers less than 100, sieved up to and including 6 are:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97. As six is not prime, all multiples of six have already been excluded and this list is the same as the one above. In other words S(100, 6) The sum of the sieved numbers less than 100, sieved up to and including 6 is the same as S(100,5) because 6 has already been accounted for as 2 x 3.

Regarding “S(v, p) is equal to S(v, p-1) if “p is not prime or v is smaller than p*p…” If v is smaller than p*p and p is not prime, sieving was completed at the previous p – 1 step and the output set only contained prime numbers at that point.

In our example the set of the sieved numbers less than 100, sieved up to and including 7 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. As 7 is prime, this list is not the same as the one above sieved up to and including 6. Consequently S(100, 7) the sum of the sieved numbers less than 100, sieved up to and including 7 is: 1060. The not the same as S(100,6) as 49 and 77 have been removed from the sum as they are “the product of p (7) with another integer that has no divisor smaller than p ( 7 and 11)”

Regarding “This can be expressed as S(v,p)=S(v,p−1)−p(S(v/p,p−1)−S(p−1,p−1))”…

As noted if we let v = 100 and p = 7:

S(v, p) = S(100, 7) = 1060

S(100, 6) = 1277.
S(100 / 7, 7) = 2 + 3 + 5 + 7 + 11 + 13 = 41.
S(6, 6) = 2 + 3 + 5 = 10.

S(v,p−1)−p(S(v/p,p−1)−S(p−1,p−1)) = S(100, 6) – 7(S(16, 5) – S(6, 6))
= 1277 – 7(41 – 10)
= 1277 – 217
= 1060

So, the expression provided appears true, but I can’t explain why.

[Rhydwen]

I guess the point is that it is quicker to calculate S(v,p), and thereby determine if p is prime, by starting with S(v,p−1) and applying the difference −p(S(v/p,p−1)−S(p−1,p−1)). If you proceed incrementally you use the value of S(v, p) you have already obtained in the next step and only need to calculate the difference each time. That would be my take on the post.

[BreakTheCipher]

Thanks a lot for this, it makes a lot more sense now. I suppose you deserve a bit more context for this post – it comes from a discussion thread for a problem on project Euler about the sum of primes (and I do recommend checking out the website if you’re into maths and programming). You can find the full post and the code here https://projecteuler.net/thread=10;page=5 (project Euler problem 10 page 5) but you need to have registered an account and solved the problem to see it. This is the fastest solution I could find to the problem.

[Rhydwen]

@BreakTheCipher Thanks, that’s an interesting list of challenges. My non-optimal implementation of the Sieve of Eratosthenes still hadn’t found a solution to problem 10 page 5 after several hours, but an implementation of the Sieve of Sundaram found the correct solution after 53 ms. If I get chance I’ll have a look at the method described in your original post. Although I have to admit to feeling a bit of a fraud when using an algorithm that I don’t fully understand. I’ll read the comments on the PE forum to see if that sheds any further light.

[madness]

Hey, Harry,

Is it always true that the group of automorphisms of Zn (additive group) is Zn* (the multiplicative group of invertible elements)? My n is not necessarily prime.

Thanks.

[Harry]

Any element of Z_n has the form m.1, and if f is an automorphism then f(m)=f(m.1)=m.f(1), so it is defined by its value on 1. Since every element has to be a power of f(1), if f is bijective f(1) must generate Z_n, so in particular there is some a such that a.f(1)=1 in Zn, or, equivalently a.f(1)+b.n=1 for some a,b in Z. It follows that f(1) has to be coprime to n. Conversely if f(1) is coprime to n then f(1) generates all of Z_n and the map f(m) = m.f(1) defines an automorphism. Finally if f and g are automorphisms then so is f composed with g, and (fg)(1) = f(g(1))=g(1).f(1) mod n, so composition of automorphisms agrees with multiplication mod n. Hence, as you suspected, the automorphism group of Z_n is just the group of units, whether or not n is prime.

[madness]

I knew it would be obvious.

Here’s something new: The automorphisms of the Vigenere are the affine ciphers.

[Rhydwen]

Given a string of text (clear, or cipher), you could work through it character-by-character and produce two-character co-ordinates from each adjacent pair. So, for “the quick brown fox…”, your first co-ordinate is (t, h), the second is (h, e) and so on. If you plot these co-ordinates, and the lines between, on an X Y grid, with the full character set on each axis, you’ll get a two-dimensional pattern of points and lines representing adjacent characters. With sufficient text, and a bit of work, you could emphasize strong relationships. I’m guessing natural language and some ciphertext will have distinctive and different characteristics. Is this pattern “a thing” in maths and if it is, what is the pattern of relationships called? I’d guess a map(?) of nodes(?) and links(?).

[Harry]

Nice idea. Thoughts anyone?

[madness]

I would call it a weighted graph.

But the same information could be stored as 26^2 numbers, which I would call digram frequencies.

[Rhydwen]

Weighted graph it is.

I’m struggling to automate the drawing of such a graph – not because it’s complicated, but just my skills, in that respect, aren’t up to much.

I think the image could convey the bigram, trigram and n-gram relationships, as they’d all form a continuous path between numerous points, better than a grid of numbers. But I need to produce one to be sure. Unfortunately I’m not going to be around for a few weeks.

[madness]

What do you call a set/group whose automorphisms are its own members?

[A paradox in waiting? For a group, each element gives an automorphism by conjugation. The automorphism is trivial if and only if the element commutes with everything in the group, so this identification of elements with automorphisms gives an injective map from G to Aut G precisely when G has trivial centre. The question is then whether there are any other automorphisms. If G has trivial centre and no outer automorphisms it is isomorphic to its own automorphism group, and is said to be complete. Harry]

[Author]

Posts