El algoritmo conocido como “de Karatsuba y Ofman” para multiplicar enteros de n cifras con un coste asintótico en O(n^{log 3})  ( ≈ O(n^1,59) )  aparece publicado en el artículo ”Multiplication of multidigit numbers on automata”, A. Karatsuba, Y. Ofman, en el nº 145, pp. 293-294, de las actas de la Academia de Ciencias de la extinta Unión Soviética (Doklady Akademii Nauk SSSR) en 1962.

Curiosamente, el mencionado artículo no fue escrito por Anatoli Alekséyevich Karatsuba (Grozny, URSS, 31 de enero de 1937 — Moscú, Rusia, 28 de septiembre de 2008) sino que, tal y como relata él mismo en su artículo “The complexity of computations” (publicado en Proceedings of the Steklov Mathematical Institute, vol. 211, pp. 169-183, 1995, copia local con clave aquí), fue escrito por Kolmogorov, probablemente ayudado por Ofman, y sin el conocimiento de Karatsuba, quien era realmente el autor del algoritmo:

[...] Later in 1962 Kolmogorov wrote a short article (probably in collaboration with Ofman) and published it in Doklady Akad. Nauk SSSR. The article was entitled: A. Karatsuba and Y. Ofman, “Multiplication of Multiplace Numbers on Automata” (Doklady Akad. Nauk SSSR, vol. 145, No. 2, pp. 293-294). I learned about the article only when I was given its reprints.

En el mismo artículo de 1995, Karatsuba reivindica su autoría:

In this section I present my algorithm for multiplying numbers. Now it is called the KML algorithm or, briefly, KML (Karatsuba Multiplication).

Anatoli Alekséyevich Karatsuba

Con posterioridad, se han desarrollado algoritmos asintóticamente más rápidos que el de Karatsuba, como el de Schönhage–Strassen (1971), de coste Θ(n log(n) log(log(n))), o el de Martin Fürer (2007), de coste n log(n) 2^Θ(log*(n)).

Leer esta anotación: http://webdiis.unizar.es/asignaturas/AB/?p=1009

Punteros a cosas (curiosidades) mencionadas hoy en clase:

• algoritmo de coste lineal para el cálculo del k-ésimo elemento de un vector (y por tanto para el cálculo de la mediana)
• orígenes del algoritmo de Karatsuba
• premio Turing de este año
  • su algoritmo (ojo, hay una errata en esa página; cuando en un párrafo de la parte final habla del “problema del algoritmo discreto”, debería decir el “problema del logaritmo discreto”)

“Simplex is not a polynomial time algorithm. Certain rare kinds of linear programs cause it to go from one corner of the feasible region to a better corner and then to a still better one, and so on for an exponential number of steps. For a long time, linear programming was considered a paradox, a problem that can be solved in practice, but not in theory!

Then, in 1979, a young Soviet mathematician called Leonid Khachiyan came up with the ellipsoid algorithm, one that is very different from simplex, extremely simple in its conception (but sophisticated in its proof) and yet one that solves any linear program in polynomial time. Instead of chasing the solution from one corner of the polyhedron to the next, Khachiyan’s algorithm confines it to smaller and smaller ellipsoids (skewed highdimensional balls). When this algorithm was announced, it became a kind of “"mathematical Sputnik", a splashy achievement that had the U.S. establishment worried, in the height of the Cold War, about the possible scientific superiority of the Soviet Union. The ellipsoid algorithm turned out to be an important theoretical advance, but did not compete well with simplex in practice. The paradox of linear programming deepened: A problem with two algorithms, one that is efficient in theory, and one that is efficient in practice!

A few years later Narendra Karmarkar, a graduate student at University of California, Berkeley, came up with a completely different idea, which led to another provably polynomial algorithm for linear programming. Karmarkar’s algorithm is known as the interior point method, because it does just that: it dashes to the optimum corner not by hopping from corner to corner on the surface of the polyhedron like simplex does, but by cutting a clever path in the interior of the polyhedron. And it does perform well in practice.

But perhaps the greatest advance in linear programming algorithms was not Khachiyan’s theoretical break through or Karmarkar’s novel approach, but an unexpected consequence of the latter: the fierce competition between the two approaches, simplex and interior point, resulted in the development of very fast code for linear programming.”

(Credit: S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms, McGraw-Hill, 2008.)

.

“A new kind of cipher that would take millions of years to break.”

Ese era el título del artículo publicado por Martin Gardner (conocidísimo divulgador científico norteamericano) en la sección Mathematical Games de la revista Scientific American, vol. 237(2), pp. 120-124, en agosto de 1977 (puede descargarse aquí).

En él, Gardner describía el método de criptografía de clave pública conocido como RSA, recién desarrollado por los investigadores del M.I.T. R.L. Rivest, A. Shamir y L.M. Adleman, y que sería publicado un año después en su artículo:

R.L. Rivest, A. Shamir y L.M. Adleman: “A method for obtaining digital signatures and public-key cryptosystems”, Communications of the ACM, 21(2), pp. 120-126, 1978.

En el artículo divulgativo de Scientific American, Gardner publicaba además el reto de descifrar un mensaje cifrado por el grupo del M.I.T. (ver figura). El reto exigía factorizar un nº de 128 cifras. El primer lector que descifrase el mensaje sería premiado con una recompensa de 100 dólares por el M.I.T. Se estimaba entonces que eran necesarios 2 millones de veces la edad del Universo de cálculo ininterrumpido del mejor computador de aquel momento para descifrar el mensaje. El M.I.T. no estaba dispuesto a pagar los 100 dólares fácilmente…

En abril de 1994, Atkins, Graff, Lenstra y Leyland resolvieron el problema propuesto por Gardner en 1977 tras más de 6 meses de cálculo, utilizando unos 1600 computadores de todo el mundo trabajando como una máquina paralela virtual. Ganaron los 100 dólares prometidos y los donaron a la Free Software Foundation. La solución era:

The Magic Words are Squeamish Ossifrage

—————

Mañana veremos en clase los detalles del algoritmo RSA, como aplicación de los métodos eficientes de multiplicación y potenciación de números grandes que hemos visto en clase los días pasados.

Ha surgido hoy en clase, es el método gráfico de multiplicar, conocido también como método maya o Tzeltal.

“Last year, a group of us were lucky enough to visit the U.K. Prime Minister’s residence at 10 Downing Street, as part of the Silicon Valley Comes to the U.K. initiative. While there, we asked about some of the paintings on the wall. When we got to a large portrait of a regally dressed woman, our host said “and of course, that’s Lady Lovelace.” So much of world history leaves out or minimizes the contributions of women, and so “of course” most of us had no idea who she was. You can imagine our surprise when we learned she was considered by some to be the world’s first computer programmer—having published the first algorithm intended for use on Charles Babbage’s Analytical Engine…”

[Seguir leyendo]

Ada Byron, Condesa de Lovelace