Home
News:
  • CIM server migrating to SPM. Some services may not work properly until the full migration is performed. Migration will be performed in April 2014

  


LPDJLQH D VHFUHW - a film of art and mathematics on elliptic curves and cryptography







Pythagorean triples such as (3, 4, 5) or (4961, 6480, 8161) were well known by ancient Babylonians around 1600 B.C. They were also aware of their correspondence to right triangles with integer sides and to the problem of splitting a given square number into two squares. Although such triples have been studied in detail since the time of Euclid, around 300 B.C., it was only in the middle of the XVII century that Pierre de Fermat stated the famous observation: "No cube can be split into two cubes, nor any biquadrate into two biquadrates, nor generally any power beyond the second into two of the same kind".

This became the famous "Fermat’s Last Theorem", stating that the equation AN + BN = CN has no nonzero integer solutions when N is greater than 2. It was completely proven in 1994, about three and a half centuries later, using the XX century theory of elliptic curves!

Elliptic curves have deep and beautiful properties. They are plane curves of the type y2 = x3 + a x + b that have been studied since the XIX century. That equation in the affine plane corresponds to the homogeneous equation y2 z= x3 + a xz2 + b z3, which describes in space a family of algebraic surfaces with two parameters a and b. The computational variation of these equations generates beautiful animations that stimulate our imagination and evoke our mathematical creativity.

Cryptography refers to secure methods to transmit and safeguard secret and valuable information. Since 1977 the RSA public key system has been widely used. It is based on prime number theory and on the difficulty of factoring very large integers. With the impact of the elliptic curve method for integer factorization, Elliptic Curve Cryptography (ECC) was invented by mathematicians in 1985, and since then the mathematical sophistication of cryptography has been raised to a whole new level.

The security of the ECC algorithms is based on the discrete logarithm problem of elliptic curves, which seems to be a much harder problem in finite field arithmetic. Recent mathematical advances imply that a certain desired security level can be attained with significantly smaller keys, for instance, a 160-bit ECC key provides the same level of security as a 1024-bit RSA key.

The theory of elliptic curves illustrates the beauty of the links between number theory, algebra and geometry and provides a powerful mathematical tool to strengthen security of e-commerce and secure communications. The old and unreliable method of the Caesar cipher of using only the simple arithmetic operation to encipher a message in the usual Latin alphabet by means of the formula d = c - 3 (mod 26) is outdated. But, it gives us the key to decipher the title of this film:


_ _ _ _ _ _ _ _ _ _ _ _ _ _


Os triplos pitagóricos, por exemplo (3, 4, 5) ou (4961, 6480, 8161), eram já bem conhecidos na antiga Babilónia, cerca de 1600 A.C., tal como a sua correspondência com o comprimentos dos lados de um triângulo rectângulo e o problema de partir um número quadrado na soma de dois quadrados. Apesar desses triplos terem sido estudados em detalhe no tempo de Euclides (300 A.C.), foi apenas em meados do século XVII que Pierre de Fermat observou: "Nenhum cubo se pode partir em dois cubos, nem nenhum biquadrado em dois biquadrados, nem, em geral, nenhuma potência maior que a segunda em duas outras do mesmo tipo".

Esta afirmação tornou-se no famoso "Último Teorema de Fermat", estabelecendo que a equação AN + BN = CN não tem soluções inteiras não nulas quando N é maior que 2, e apenas foi completamente demonstrada em 1994, cerca de três séculos e meio mais tarde, usando a teoria das curvas elípticas do século XX !

As curvas elípticas são curvas planas do tipo y2 = x3 + a x + b que possuem propriedades belas e profundas, bem estudadas desde o século XIX. A essa equação corresponde a equação homogénea de grau três y2 z= x3 + a xz2 + b z3, a qual descreve no espaço uma família de superfícies algébricas com dois parâmetros a e b. A variação computacional desses parâmetros nessas equações gera belas animações que estimulam a nossa imaginação e evocam a nossa criatividade matemática.

A criptografia trata de métodos seguros para transmitir e salvaguardar informação secreta e valiosa. Desde 1977 o sistema de chave pública RSA tem sido largamente usado e baseia-se na teoria dos números primos e na dificuldade de fatorização de números inteiros muito grandes. Com o impacto do método das curvas elípticas na fatorização de inteiros, os matemáticos inventaram em 1985 um sistema de encriptação por curvas elípticas, o ECC (Elliptic Curve Cryptography) e, desde então, a sofisticação matemática da criptografia foi elevada a um novo nível.

A segurança dos algoritmos ECC é baseada no problema do logaritmo discreto na teoria das curvas elípticas, o qual é atualmente um problema muito mais difícil da aritmética em corpos finitos. Avanços matemáticos recentes implicam que um certo nível de segurança desejada pode ser atingida com chaves significativamente menores, por exemplo, uma chave ECC de 160 bits fornece o mesmo nível de segurança que uma chave RSA de 1024 bits.

A teoria das curvas elípticas ilustra a beleza das interligações entre a teoria dos números, a álgebra e a geometria, além de que fornece um poderoso instrumento matemático para reforçar a segurança do comércio eletrónico e das comunicações digitais. O velho e inseguro método de César para cifrar mensagens no alfabeto latino, que corresponde à simples operação aritmética d = c - 3 (mod 26), está ultrapassado. Mas ainda nos dá a chave para decifrar o título deste filme:


_ _ _ _ _ _ _ _ _ _ _ _ _ _


Las tríadas pitagóricas, como (3,4,5) o (4961,6480,8161), ya eran conocidas en la Antigua Babilonia, cerca de 1600 a.c., así como su relación con las longitudes de los lados de un triángulo rectángulo y el problema de la descomposición del cuadrado de un número como suma de otros dos cuadrados. Estas tríadas fueron estudiadas detalladamente en el tiempo de Euclides (300 a.c.) mas hubo que esperar a mediados del siglo XVII para que Fermat observase: “Ningún cubo se puede dividir en dos cubos, ningún bi-cuadrado en dos bi-cuadrados y, en general, ninguna potencia mayor que la segunda en dos del mismo tipo”.

Esta afirmación se convirtió en el famoso “Último Teorema de Fermat” que establece que la ecuación AN + BN = CN no tiene soluciones enteras no nulas cuando N es mayor que 2. La demostración completa de este resultado fue obtenida solo en 1994 ¡cerca de tres siglos y medio después de ser enunciado y usando la teoría de las curvas elípticas del siglo XX!

Las curvas elípticas son curvas planas de ecuación y2 = x3 + a x + b y poseen propiedades bellas y profundas, bien estudiadas desde el siglo XIX. A ese tipo de ecuación corresponde la ecuación homogénea de grado tres y2 z= x3 + a xz2 + b z3 que describe en el espacio una familia de superficies algebraicas con dos parámetros a y b. La variación computacional de estos parámetros en esas ecuaciones genera hermosas animaciones que estimulan nuestra imaginación y evocan nuestra creatividad matemática.

La criptografía estudia métodos seguros para transmitir y salvaguardar información secreta y valiosa. Desde 1977 el sistema de clave pública RSA ha sido ampliamente usado y se basa en la teoría de números primos, más concretamente, en la dificultad de factorización de números enteros muy grandes. Con el impacto del método de curvas elípticas en la factorización de enteros, los matemáticos inventaron en 1985 un sistema de encriptación por curvas elípticas, el ECC (Ellliptic Curve Cryptography) y, desde entonces, la sofisticación matemática de la criptografía se elevó a un nuevo nivel.

La seguridad de los algoritmos ECC se basa en el problema del logaritmo discreto en la teoría de curvas elípticas que es actualmente un problema mucho más difícil de la aritmética en cuerpos finitos. Recientes avances matemáticos implican que un nivel de seguridad deseada puede ser alcanzado con claves significativamente menores, por ejemplo, una llave ECC de 160 bits proporciona el mismo nivel de seguridad que una llave RSA de 1024 bits.

La teoría de las curvas elípticas ilustra la belleza de las interrelaciones entre la teoría de los números, el álgebra y la geometría, además de proporcionar un poderoso instrumento matemático para reforzar la seguridad del comercio electrónico y de las comunicaciones digitales. El viejo e inseguro método de César para cifrar mensajes del alfabeto latino, que corresponde a la simple operación aritmética d=c-3(mod 26) está superado. Sin embargo, todavía nos da la clave para descifrar el título de esta película:


_ _ _ _ _ _ _ _ _ _ _ _ _ _


Pythagoräische Tripel, wie (3,4,5) oder (4961, 6480, 8161) waren bereits den Babyloniern 1600 vor Christus bekannt. Sie beschrieben auch den Zusammenhang dieser Tripel mit rechtwinkligen Dreiecken, die ganzzahligen Seitenlängen haben, sowie mit dem Problem eine Quadratzahl als Summe zweier Quadratzahlen zu auszudrücken. Obwohl sich sogar Euklid 300 vor Christus intensiv mit dem Studium der pythagoräischen Tripel beschäftigte, dauerte es noch bis Mitte des 18. Jahrhunderts, als der französische Mathematiker Pierre de Fermat seine berühmte Vermutung formulierte: “Kein Würfel kann in zwei Würfel zerteilt werden und kein Biquadrat in zwei Biquadrate, noch irgendeine Potenz nach der zweiten in zwei derselben Art”.

Das ist die Formulierung des bekannten “letzten Satzes von Fermat”, der besagt, dass die Gleichung AN + BN = CN für N größer 2 keine nicht-trivialen ganzzahligen Lösungen hat. Es dauerte bis 1994, um den Satz vollständig zu beweisen. Der Beweis verwendet die Theorie der elliptischen Kurven, die erst im 20ten Jahrhundert entstanden ist.

Elliptische Kurven haben schöne und tiefgründige Eigenschaften. Die Mathematik beschäftigt sich seit dem 19ten Jahrhundert mit ihnen. Es handelt sich um ebene Kurven vom Typ y2 = x3 + a x + b. Diese Gleichung in der affinen Ebene entspricht der homogenen Gleichung y2 z= x3 + a xz2 + b z3, die im Raum eine Familie von algebraischen Flächen mit den Parametern a und b beschreibt. Am Computer berechnete Variationen dieser Gleichung erzeugen schöne Animationen, regen unsere Phantasie an und wecken unsere mathematische Kreativität.

Das mathematische Teilgebiet der Kryptographie beschäftigt sich mit der Verschlüsselung und Übermittlung von sensiblen Informationen. Seit 1977 wird hauptsächlich das RSA-Sicherheitssystem benutzt. Es basiert auf der Verwendung von Primzahlen und der Schwierigkeit, eine große natürliche Zahl in ihre Primfaktoren zu zerlegen. Mithilfe der Methode der elliptischen Kurven zur Faktorisierung einer ganzen Zahl wurde 1985 die Elliptic Curve Cryptography (ECC) entwickelt. Diese Methode hat das mathematische Niveau der Verschlüsselung auf eine neue Stufe gehoben.

Die Sicherheit des ECC-Algorithmus basiert auf dem Problem des diskreten Logarithmus elliptischer Kurven, das in der Arithmetik der endlichen Körper sehr schwer zu lösen ist. Neue mathematische Entwicklungen zeigen, dass so ein bestimmtes gewünschtes Sicherheitsniveau mit signifikant kleineren Schlüsseln erreicht werden kann, z.B. erzeugt ein 160-bit ECC-Schlüssel dieselbe Sicherheitsstufe wie ein 1024-bit RSA-Schlüssel.

Die Theorie der elliptischen Kurven illustriert anschaulich die Schönheit von Zahlentheorie, Algebra und Geometrie in ihrer Verbindung und stellt ein mächtiges mathematisches Werkzeug zur Verbesserung der Sicherheit von e-commerce und Kommunikation dar. Die alte und unsichere Methode des Cäsar-Codes, die nur eine einfache arithmetische Operation verwendet, um das gewöhnliche lateinische Alphabet mit der Formel d=c-3 (mod 26) zu verschlüsseln, hat ausgedient. Aber mit ihr kann man den Titel dieses Films dekodieren:


_ _ _ _ _ _ _ _ _ _ _ _ _ _


INITIATIVE
Centro Internacional de Matemática
Casa da Animação
Mathematisches Forschungsinstitut Oberwolfach

ORIGINAL IDEA
José Francisco Rodrigues

CONCEPTION
Victor Fernandes
Stephan Klaus
Armindo Moreira
José Francisco Rodrigues

REALIZATION AND PRODUCTION
Victor Fernandes
Armindo Moreira

SURFER MOVIES
Andreas Matt
Bianca Violet

ORIGINAL MUSIC
Victor Fernandes
Armindo Moreira

ACKNOWLEDGMENTS
CMAF/Universidade de Lisboa
Fundação Calouste Gulbenkian
IMAGINARY exhibition
Vila de Óbidos

SPONSOR
CIÊNCIA VIVA


The first public presentation of the movie LPDJLQH D VHFUHW was done the 26 September 2010 in Óbidos during the opening of the Workshop "Raising the Public Awareness in Mathematics". Versions of the film in high quality (approx 4.5Gb) are available in English, Portuguese, Spanish, and Deutsch. YouTube versions of the film are available in English, Portuguese, Spanish, and Deutsch.