puzzle – Page 5 – neverendingbooks

Chinese remainders and adele classes

Published January 31, 2008 by lieven

Oystein Ore mentions the following puzzle from Brahma-Sphuta-Siddhanta (Brahma’s Correct System) by Brahmagupta :

An old woman goes to market and a horse steps on her basket and crashes the eggs. The rider offers to pay for the damages and asks her how many eggs she had brought. She does not remember the exact number, but when she had taken them out two at a time, there was one egg left. The same happened when she picked them out three, four, five, and six at a time, but when she took them seven at a time they came out even. What is the smallest number of eggs she could have had?

Here’s a similar problem from “Advanced Number Theory” by Harvey Cohn (( always, i wonder how one might ‘discreetly request’ these remainders… )) :

Exercise 5 : In a game for guessing a person’s age x, one discreetly requests three remainders : r1 when x is divided by 3, r2 when x is divided by 4, and r3 when x is divided by 5. Then x=40 r1 + 45 r2 + 36 r3 modulo 60.

Clearly, these problems are all examples of the Chinese Remainder Theorem.

Chinese because one of the first such problems was posed by Sunzi [Sun Tsu] (4th century AD)
in the book Sunzi Suanjing. (( according to ChinaPage the answer is contained in the song on the left hand side. ))

There are certain things whose number is unknown.
Repeatedly divided by 3, the remainder is 2;
by 5 the remainder is 3;
and by 7 the remainder is 2.
What will be the number?

The Chinese Remainder Theorem asserts that when $N = n_{1} n_{2} \dots n_{k}$ with the $n_{i}$ pairwise coprime, then there is an isomorphism of abelian groups $Z / N Z ≃ Z / n_{1} Z \times Z / n_{2} Z \times \dots \times Z / n_{k} Z$ . Equivalently, given coprime numbers $n_{i}$ one cal always solve the system of congruence identities

${\begin{cases} x \equiv a_{1} (mod n_{1}) \\ x \equiv a_{2} (mod n_{2}) \\ ⋮ \\ x \equiv a_{k} (mod n_{k}) \end{cases}$

and all integer solutions are congruent to each other modulo $N = n_{1} n_{2} \dots n_{k}$ .

We will need this classical result to prove that
$Q / Z ≃ A / R$
where (as last time) $A$ is the additive group of all adeles and where $R$ is the subgroup $\prod_{p} Z_{p}$ (i’ll drop all ‘hats’ from now on, so the p-adic numbers are $Q_{p} = {\hat{Q}}_{p}$ and the p-adic integers are denoted $Z_{p} = {\hat{Z}}_{p}$ ).

As we will have to do calculations with p-adic numbers, it is best to have them in a canonical form using digits. A system of digits $D$ of $Q_{p}$ consists of zero and a system of representatives of units of $Z_{p}^{*}$ modulo $p Z_{p}$ . The most obvious choice of digits is $D = 0, 1, 2, \dots, p - 1$ which we will use today. (( later we will use another system of digits, the Teichmuller digits using $p - 1$ -th root of unities in $Q_{p}$ . )) Fixing a set of digits $D$ , any p-adic number $a_{p} \in Q_{p}$ can be expressed uniquely in the form

$a_{p} = \sum_{n = d e g (a_{p})}^{\infty} a_{p} (n) p^{n}$ with all ‘coefficients’ $a_{p} (n) \in D$ and $d e g (a_{p})$ being the lowest p-power occurring in the description of $a_{p}$ .

Recall that an adele is an element $a = (a_{2}, a_{3}, a_{5}, \dots) \in \prod_{p} Q_{p}$ such that for almost all prime numbers p $a_{p} \in Z_{p}$ (that is $d e g (a_{p}) \geq 0$ ). Denote the finite set of primes p such that $d e g (a_{p}) < 0$ with $P = p_{1}, \dots, p_{k}$ and let $d_{i} = - d e g (a_{p_{i}})$ . Then, with $N = p_{1}^{d_{1}} p_{2}^{d_{2}} \dots p_{k}^{d_{k}}$ we have that $N a_{p_{i}} \in Z_{p_{i}}$ . Observe that for all other prime numbers $q \notin P$ we have $(N, q) = 1$ and therefore $N$ is invertible in $Z_{q}$ .

Also $N = p_{i}^{d_{i}} K_{i}$ with $K_{i} \in Z_{p_{i}}^{*}$ . With respect to the system of digits $D = 0, 1, \dots, p - 1$ we have

$N a_{p_{i}} = \underset{= α_{i}}{\underset{⏟}{K_{i} \sum_{j = 0}^{d_{i} - 1} a_{p_{i}} (- d_{i} + j) p_{i}^{j}}} + K_{i} \sum_{j \geq d_{i}} a_{p_{i}} (- d_{i} + j) p_{i}^{j} \in Z_{p_{i}}$

Note that $α_{i} \in Z$ and the Chinese Remainder Theorem asserts the existence of an integral solution $M \in Z$ to the system of congruences

${\begin{cases} M \equiv α_{1} modulo p_{1}^{d_{1}} \\ M \equiv α_{2} modulo p_{2}^{d_{2}} \\ ⋮ \\ M \equiv α_{k} modulo p_{k}^{d_{k}} \end{cases}$

But then, for all $1 \leq i \leq k$ we have $N a_{p_{i}} - M = p_{i}^{d_{i}} \sum_{j = 0}^{\infty} b_{i} (j) p^{j}$ (with the $b_{i} (j) \in D$ ) and therefore

$a_{p_{i}} - \frac{M}{N} = \frac{1}{K_{i}} \sum_{j = 0}^{\infty} b_{i} (j) p^{j} \in Z_{p_{i}}$

But for all other primes $q \notin P$ we have that $α_{q} \in Z_{q}$ and that $N \in Z_{q}^{*}$ whence for those primes we also have that $α_{q} - \frac{M}{N} \in Z_{q}$ .

Finally, observe that the diagonal embedding of $Q$ in $\prod_{p} Q_{p}$ lies entirely in the adele ring $A$ as a rational number has only finitely many primes appearing in its denominator. Hence, identifying $Q \subset A$ via the diagonal embedding we can rephrase the above as

$a - \frac{M}{N} \in R = \prod_{p} Z_{p}$

That is, any adele class $A / R$ has as a representant a rational number. But then, $A / R ≃ Q / Z$ which will allow us to give an adelic version of the Bost-Connes algebra!

Btw. there were 301 eggs.

sobering-up

Published January 5, 2008 by lieven

Kea’s post reminded me to have a look at my search terms (the things people type into search engines to get redirected here). Quite a sobering experience…

Via Google Analytics I learn that 49,51% of traffic comes from Search Engines (compared to 26,17% from Referring Sites and 24,32% from direct hits) so I should take Search Terms more seriously! Above you can find the top-25.

On 1. there is neverendingbooks. Well, some people seem to remember the blog-name, but require google to remember the URL (neverendingbooks.org)…, okay, fair enough. But from then on… all search terms are iTouch related! The first ‘other’ term is puzzle m at 24. and believe me things do not improve afterwards. Here the only non-Touch related search terms in the top 100 :

neverendingbooks.org (40)
“puzzle m” (42)
moonshine mathematics (79)
necklace algebra (80)
“calabi-yau algebra (90)
“dessin d enfant” (91)
“lieven le bruyn” (95)
Mathieu group + M(13) (97)
13 points 5 lines puzzle (98)
15 itouch sliding puzzle (99)

the last one is really touching (sic). Is there anybody out there still interested in the mathematics, or should I turn this blog into a yaib (yet another iTouch blog) ???

tori & crypto : Diffie-Hellman or GCHQ?

Published January 3, 2008 by lieven

Boris Kunyavskii arXived the paper Algebraic tori – thirty years after dedicated to the 80th anniversary of V. E. Voskresenskii. The goal is to give an overview of results of V. E. Voskresenskii on arithmetic and birational properties of algebraic tori which culminated in his monograph “Algebraic Tori” published in Russian 30 years ago. As Ive worked on this stuff a long time ago I glanced through the paper and it contains a nice summary of the work of V.E. Voskresenskii, and later of Jean-Louis Colliot-Thelene, Jean-Jacques Sansuc and David Saltman. To my surprise I also made a guest-appearance and even seem to have a conjecture (??!!). Fortunately the ‘conjecture’ turned out to be correct as was proved by Nicole Lemire and Martin Lorenz. But a much bigger surprise (at least to me) is contained in the final section of the paper where applications of (stable) rationality of certain tori are given to primality testing and public key cryptography!

In [GPS]
the authors propose to use a similar idea of compression for using tori
in an even more recent cryptographic protocol (so-called pairing-based
cryptography). It is interesting to note that the efficiency (compression factor) of the above mentioned cryptosystems heavily depends on
rationality of tori under consideration (more precisely, on an explicit
rational parameterization of the underlying variety). As the tori used
by Rubin and Silverberg are known to be stably rational, the seemingly abstract question on rationality of a given stably rational torus
is moving to the area of applied mathematics. The first challenging
problem here is to obtain an explicit rational parameterization of the
8-dimensional torus $T_{30}$ , deïfined over a finite field k and splitting over
its cyclic extension L of degree 30.

This is a particular case of a problem posed by Voskresenskii [Vo77,
Problem 5.12] 30 years ago. Let us hope that we will not have to wait
another 30 years for answering this question on a degree 30 extension.

That’s all it takes to get me seriously side-tracked… so the last couple of hours I’ve been reading up on this connection between tori and cryptography. I will spend a couple of posts on these beautiful results. The latest seems to be that, while rationality of $T_{30}$ is still unknown, one can use an explicit stable-rationality description of it to get a better bound than the XTR-system (the system corresponding to the torus $T_{6}$ ) which in turn is better than the LUC-system (corresponding to $T_{2}$ ), which is turn is twice as efficient as the Diffie-Hellman key exchange system… So let us start gently with the latter one…

Whitfield Diffie (r.) and Martin Hellman (m.) published in 1976 their public key-exchange system. Take a large prime power $q = p^{N}$ , make it public and consider the finite field $F_{q}$ which is known to have a cyclic group of units $F_{q}^{*}$ of order $q - 1$ . Now, take $g$ to be an element in it of large order (preferable a generator but that isnt necessary) and also make this element public.

Now choose a random integer $a$ (your hidden secret) and compute the element $g^{a} \in F_{q}$ and publicize this element. Suppose someone else published his/her element $g^{b}$ constructed from his/her secret integer $b$ then both you and this other person can compute from the published data and their secret numbers the element (the shared key)

$g^{a b} = (g^{b})^{a} = (g^{a})^{b}$

(because you know $a$ and the published $g^{b}$ and your correspondent knows $b$ and the published $g^{a}$ ) but nobody else can compute it from the public-available data only because discrete logarithms cannot be feasibly computed in the group $F_{q}^{*}$ . Hellman suggests to call this system the Diffie-Hellman-Merkl key-exchange (via this link)

The first researchers to discover and publish the concepts of PKC were Whitfield Diffie and Martin Hellman from Stanford University, and Ralph Merkle from the University of California at Berkeley. As so often happens in the scientific world, the two groups were working independently on the same problem — Diffie and Hellman on public key cryptography and Merkle on public key distribution — when they became aware of each other’s work and realized there was synergy in their approaches. In Hellman’s words: “We each had a key part of the puzzle and while it’s true one of us first said X, and another of us first said Y, and so on, it was the combination and the back and forth between us that allowed the discovery.”

And that was the full story until 1997. In December, 1997, it was revealed that researchers at the GCHQ organization did some work in the early 1970’s in the field of “non-secret encryption”. The people involved are James Ellis, Clifford Cocks and Malcolm Williamson (r.).

Here is a note by Ellis on his recollection of the history of ‘Non-secret encryption” :

Cryptography is a most unusual science. Most professional scientists aim to be the first to publish their work,
because it is through dissemination that the work realises its value. In contrast, the fullest value of cryptography
is realised by minimising the information available to potential adversaries. Thus professional cryptographers
normally work in closed communities to provide sufficient professional interaction to ensure quality while
maintaining secrecy from outsiders. Revelation of these secrets is normally only sanctioned in the interests
of historical accuracy after it has been demonstrated clearly that no further benefit can be obtained from
continued secrecy.
In keeping with this tradition it is now appropriate to tell the story of the invention and development within
CESG of non-secret encryption (NSE) which was our original name for what is now called PKC. The task of writing
this paper has devolved on me because NSE was my idea and I can therefore describe these early developments from
personal experience. No techniques not already public knowledge, or specific applications of NSE will be mentioned…

The once secret notes of Williamson are also available. NON-SECRET ENCRYPTION USING A FINITE FIELD
by M J Williamson, 21 January 1974 and THOUGHTS ON CHEAPER NON-SECRET ENCRYPTION
M J Williamson, 10 August 1976.

Tag: puzzle

Chinese remainders and adele classes

sobering-up

tori & crypto : Diffie-Hellman or GCHQ?