jump to navigation

The Border of Kingdom May 4, 2008

Posted by Alexandre Borovik in Uncategorized.

I bring my apologies for a Russian text quoted below — I promise to try to find an English translation, but so far I failed in my quest. This fable by Roerich came to my mind when I started to think about David Pierce’s induction/recursion opposition in terms of practicalities of “black box” computing in a very big residue ring \mathbb{Z}/m\mathbb{Z} with modulus m of unknown prime decomposition (and this is a VERY practical issue since it is a setup for the RSA cryptosystem). As David Pierce observed, a standard recursion scheme for exponentiation is inconsistent on finite rings like \mathbb{Z}/m\mathbb{Z}.

What is a black box calculation? I’ll give you a toy example concerned with the RSA setup. Assume that you are given a calculator which has only buttons for digits, two operations +, \times and return =. To make it worse, the calculator returns the answers modulo m for a very large — and unknown to you — number m which is a product of two very large primes m=pq which are also unknown to you. On the bright side, you can save any number of intermediate results in the memory and re-use them. To guide yourself through the labyrinth of modular arithmetic, you can do auxiliary calculations with a pencil on paper.

I make a (semi-mathematical) claim that, playing with such a calculator for the rest of your life, you will never notice inconsistency in the recursive definition of exponentiation. Also, if m has 100 digits, the calculator will be quite usable for many everyday needs.

My argument is based on a semi-philosophical premise that calculations (no matter how clever they are) with unknown modulus m are in effect random manipulations with buttons with known m.

But to find a random concrete instance of inconsistency of exponentiation in \mathbb{Z}/m\mathbb{Z}, that is, natural numbers n >1 and k >0 such that n^k = 1 \bmod m means getting at least a 1/4 chance to factorise m and thus break the RSA scheme based on modulus m: this is the probability with which k is even and

s = n^{k/2} \ne \pm 1 \bmod m.

Notice that  we can compute s by a square-and-multiply method. Now let us repeat a trick from Simmons’ attack on (a lousy implementation of) RSA:

s^2 = 1 \bmod m hence m =pq \mid (s-1)(s+1),

and, computing (with a pencil on paper, using Euclid’s algorithm) the greatest common divisors of (m, s-1) and (m,s+1), we easily find p and q — which exactly means to break the scheme.

I am pleased to say that David Corfield’s quest for instances of when the infinite is simpler is answered in this simple example in a stronger form: sometimes, infinite is not just simpler, it is safer.

What follows is Nicholas Roerich‘s fable The Border of Kingdom:

Н.К. Рерих


В Индии было.

Родился у царя сын. Все сильные волшебницы, как знаете, принесли царевичу свои лучшие дары. Самая добрая волшебница сказала заклятие:

Не увидит царевич границ своего царства.

Все думали, что предсказано царство, границами безмерное.

Но вырос царевич славным и мудрым, а царство его не увеличилось.

Стал царствовать царевич, но не водил войско отодвинуть соседей.

Когда же хотел он осмотреть границу владений, всякий раз туман покрывал граничные горы.

В волнах облачных устилались новые дали. Клубились облака высокими грядами.

Всякий раз тогда возвращался царь силою полный, в земных делах мудрый решением.

Вот три ненавистника старые зашептали:

Мы устрашаемся. Наш царь полон странною силою. У царя нечеловеческий разум. Может быть, течению земных сил этот разум противен. Не должен быть человек выше человеческого.

Мы премудростью отличенные, мы знаем пределы. Мы знаем очарования.

Прекратим волшебные чары. Пусть увидит царь границу свою. Пусть поникнет разум его. И ограничится мудрость его в хороших пределах. Пусть будет он с нами.

Три ненавистника, три старые повели царя на высокую гору. Только перед вечером достигли вершины, и там все трое сказали заклятие. Заклятие о том, как прекратить силу:

Бог пределов человеческих!

Ты измеряешь ум. Ты наполняешь реку разума земным течением.

На черепахе, драконе, змее поплыву. Свое узнаю. На единороге, барсе, слоне поплыву. Свое узнаю. На листе дерева, на листе травы, на цветке лотоса поплыву. Свое узнаю.

Ты откроешь мой берег! Ты укажешь ограничение! Каждый знает, и ты знаешь! Никто больше. Ты больше. Чары сними.

Как сказали заклятие ненавистники, так сразу алою цепью загорелись вершины граничных гор.

Отвратили лицо ненавистники. Поклонились.

Вот, царь, граница твоя.

Но летела уже от богини доброго земного странствия лучшая из волшебниц.

Не успел царь взглянуть, как над вершинами воздвигся нежданный пурпуровый град, за ним устлалась туманом еще невиданная земля.

Полетело над градом огневое воинство. Заиграли знаки самые премудрые.

Не вижу границы моей, — сказал царь. Возвратился царь духом возвеличенный. Он наполнил землю свою решениями самыми мудрыми.




1. abo - May 9, 2008

Sorry, I could be misunderstanding your point or the underlying theory, but the way I understand it: exponentiation is inconsistent in Z/mZ if and only if for some a, a^m != 1 mod m (i.e. it’s not equality here that shows inconsistency but inequality). That is, in Z/mZ m = 0 and so, to be consistent, a^m should equal a^0 which equals 1. But often it is not. For instance, in Z/5Z, 2^5 = 2 != 1 = 2^0.

2. confluence - June 3, 2008

Confluence says : I absolutely agree with this !

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: