Tuesday, April 02, 2019

Libertad de expresión y debate

El primer principio es que no debes engañarte a ti mismo, y tú eres la persona más fácil de engañar.

—Richard P. Feynman

La libertad de expresión es un concepto fundamental que se ha construido en algunas civilizaciones como parte fundamental de su estructura social, desde los griegos en la antigüedad hasta la declaración de los derechos humanos. Esto es el resultado de muchas acciones que sucedieron en el mundo occidental después de la ilustración y la revolución francesa. La libertad de expresión garantiza una mejor sinergia entre los seres humanos, de eso no hay duda. Hoy quiero hablar de errores en el debate que ocurren gracias al abuso del concepto de "libertad de expresión", antes de que me grites, trata de terminar de leerme.

Primero, formalmente la libertad de expresión es la capacidad de poder articular tus opiniones e ideas de cualquier tema (ej. política, sexualidad, arte) sin miedo, sin que te censuren o te sancionen, penalicen o agredan.

La libertad de expresión no es absoluta y esto es sabido. Podrá parecer un oxímoron decir que no es absoluta pero todos sabemos que existen temas donde no se es libre de expresar. Como ejemplos "blancos" tenemos secretos industriales, acuerdos de confidencialidad, copyrights, et cétera. Ejemplos más obscuros están la pedofilia, la violencia, la difamación, entre otros.

Una de las grandes consecuencias de la libertad de expresión es la capacidad de debate como herramienta de aprendizaje. Aquí quiero exponer unas ideas que he experimentado debatiendo de las cuales he sido el falaz y también victima de la falacia. El propósito de exponer esto es tratar de garantizar justamente que el debate sea una herramienta de aprendizaje y no de imposición ideológica. Hoy en día es necesario tener buenas bases para debatir debido al auge de las redes sociales y el impacto de estas. Con memes y opiniones violentas que reducen argumentos complejos a un dibujo que denota ironía, lo creas o no se están justificando personas a la hora de argumentar (inclusive políticos).

Los siguientes puntos son errores que considero graves y comunes en la lógica a la hora de debatir. Considero que han sido exponenciados con el uso de redes sociales y la sinergia que existe hoy en día en temas delicados (esto es una opinión con bases empíricas, no tengo fuente).

Nota importante: Estos diez puntos que expreso a continuación, antes que nada es conocimiento a posteriori. Lo que leerás es una opinión que estoy abierto a corregir si me es recalcado un error. Por lo tanto, con esta nota informo que no soy experto en el tema y sólo estoy expresando mi opinión potencialmente incompleta.

Errores comunes en el abuso de la libertad de expresión a la hora de debatir:

1. Uso de estadísticas inexistentes basadas en un potencial "sentido común". Es muy fácil decir 5 de cada 10 mujeres en el mundo han sufrido violencia de género cuando la realidad es que 7 de cada 10 mujeres en el mundo han sufrido violencia de género (Observatory of Gender (Women’s Coordinating Office, 2013)). El uso de estos números "a ojo de buen cubero", debe evitarse (y más si eres un personaje público)  porque la idea podría evolucionar de voz a voz a una mentira colectiva. A veces también se mezclan estadìsticas en espacios muestrales diferentes, cayendo en otra falacia.

2. Descalificación absoluta de argumentos basados en la ignorancia de la contraparte. Cuando una persona decide debatir con alguien, la premisa de las partes es que ambas pueden aportar al conocimiento mutuo. El utilizar argumentos no demostrables o sin fuentes es lo mismo que argumentar con falacias.
Cuando una parte decide utilizar estadísticas o afirmaciones de otras personas, deberá presentar una prueba de existencia de la fuente. Si esto no se tiene en mente, el objetivo del debate con alguien ignorante sólo será humillarlo o imponer una opinión sin propósitos de enseñanza.

3. Controlar el tema a través de obviedades, resultando en argumentos falaces. Aquí el perpetrador de la falacia supone que la contraparte no está alineada a la parte ética o moral superficial del tema en cuestión, generalmente llevando el argumento a otra falacia (por ejemplo, ad hominem). Esto podría suceder si el perpetrador de la falacia usa su opinión como absoluta e irrefutable por el hecho de estar débilmente alineada a un principio básico (e.j. libertad de expresión). El perpetrador de la falacia deberá darse cuenta que el argumento de la contraparte podría (o no) dar un contraejemplo a una situación o contexto específico, rompiendo con la generalidad de la idea. Aquí, quien controla el tema con obviedades insulta la inteligencia o ética de su contraparte gracias a la incapacidad de escuchar o de entender un panorama más complejo del superficial en el tema en cuestión. Yo y muchos le llamamos a veces a esto irse por la tangente, y es muy común.

Un ejemplo de esto es cuando alguien está en contra de la legalización de cambio de sexo a menores de edad. El falaz podría usar en su contra argumentos que van alineados a una posible transofobia o de estar en contra del movimiento LGBT o inclusive homofobia. En este caso no necesariamente la transofobia juega un papel en la contraargumentación por lo que el falaz usa argumentos obvios para explicar que la transofobia "es mala", queriendo justificar implícitamente que el no estar de acuerdo en el cambio de sexo a menores de edad es una implicación directa de "su transofobia". Esto insulta y humilla indirectamente a pesar de que esencialmente nadie en el debate sea transófobo.

4. Bases éticas y morales distintas entre ambas partes resultan en argumentos circulares. Si el tema a debatir se fundamenta en bloques fundamentales distintos de ambas partes, el debate sólo será un show.
En este caso lo que hay que debatir son los fundamentos y no las consecuencias de estos fundamentos. Como ejemplo es cuando una mujer denuncia y argumenta discriminación de género laboral y es tachada de mentirosa o exagerada por alguien alineado al patriarcado. En este ejemplo es claro que no se puede llegar a una conclusión debido a que el problema yace en los fundamentos de la argumentación (machismo vs feminismo) y no en la situación puntual del debate per sé.

5. Violencia verbal. La descalificación de un argumento con el uso de palabras arriba de tono o sarcasmo podría estar insultando indirectamente a tu contraparte, destruyendo su libertad de pensamiento. Esto sucede generalmente cuando algo es legítimamente "obvio" (teniendo una base moral y ética establecida para el debate). Opino que lo que debe recalcársele a quien no ve "lo obvio", no es la idea per sé, sino la base que fundamenta su idea, ya que ésta podría diferir con los axiomas preestablecidos para ejecutar un buen debate.

6. Uso de experiencias personales. Esto conlleva fácilmente a falacias debido a que la contraparte podría ignorar las circunstancias y contexto de tu argumento. Esto como herramienta argumentativa es pobre. A la hora de debatir ambas partes deben tener acceso a la misma información y antes de concluir un resultado, este debe estar basado en un camino lógico que una la base fundamental del debate y la conclusión.

7. Descontextualización del tema a debatir. Es fácil encontrar "contraejemplos" cuando cambias el universo de un problema, descalificando rápidamente a tu contraparte. Esto a veces está ligado al punto 4. Sin embargo puede ser más sutil y me parece que es un defecto muy grande y difícil de detectar el cual todos debemos estar alerta.

8. Tono de voz cambiante al ejecutar más estrés prosódico en ciertas palabras. Esto es muy interesante porque es un fenómeno fonético y no lingüístico que cambia la semántica. Este error argumentativo puede confundir a tu contraparte y usarse como herramienta de debate sucio después. Imagina que cuando pongo una palabra en mayúsculas, debes leerla con mayor fuerza.
YO, no leí el libro.  (otro lo leyó)
Yo NO leí el libro.   (no lo leí)
Yo no LEÍ el libro.   (hice otra cosa en vez de leer)
Yo no leí EL libro.   (leí otro)
Yo no leí el LIBRO.   (el libro no es un libro per sé).

Este tipo de error al debatir también puede darse de forma escrita con el uso de comillas (").

9. Falsas conclusiones porque tu contraparte sucede que tiene la misma opinión que tú. Esto es peligroso ya que es una falacia ad hominem, donde la conclusión estará basada en la coincidencia de argumentos de tu contraparte aunque estos no estén desarrollados. Por ejemplo dos racistas infiriendo que un argumento racista no es incorrecto en X o Y contexto (cuando con base en la ética occidental es incorrecto en todo contexto).

10. Uso de emociones ante temas sensibles. Este es el más controvertido a mi gusto pero es una realidad que es una herramienta usual en la argumentación moderna. Este pretende hacer sentir culpable a la contraparte de su postura con base en ejemplos en un contexto muy específico, forzando a la contraparte a abortar su postura por miedo a la humillación moral o descalificación social.

En mi opinión no hay argumentos que engloben la generalidad de una situación. En temas subjetivos cuya métrica de veracidad es inexistente y sólo es categórica o subjetiva siempre habrán contextos en donde tus ideas no embonen, por lo que a la hora de debatir siempre es importante plantear bases axiomáticas aceptadas por ambos para el inicio del debate.
Tratemos de eliminar la tendencia a fijarse solo en la evidencia que apoya nuestros puntos de vista, eso nos hace... tontos a la hora de debatir.

Más información, lee la interesante parte de "falacias informales" en la lista de Falacias de Wikipedia (https://en.wikipedia.org/wiki/List_of_fallacies#Informal_fallacies)

Eduardo Ruíz Duarte
Twitter: @toorandom
PGP: toorandom en Gmail.com FEE7 F2A0 

Tuesday, March 19, 2019

Quantum factorization intuition and how RSA is broken with examples from Fourier analysis


In this post I give an idea of how a quantum computer may factor an integer. This post is not formal and is intended for non experts, even non-mathematicians (in fact I wrote it for colleagues which are computer engineers). This is not exactly Shor's algorithm but I will explain the main essence of it. Therefore, some gaps may be here. I will explain how the Fourier Transform is used to factor an integer. Calculating the Fourier transform in a classical computer is expensive, however, for a quantum computer due to its physical nature, takes just 1 cycle using quantum gates. I won't delve into details about quantum gates in this post, just in the mathematical part but I will try to be as smooth as possible without any fancy words and language. This is intended for you to finally grasp how a quantum computer is supposed to break RSA and I will provide you some code to play with.


What you need to know first? 

a) What is GCD of two integers? :   If a and b are two integers, the Greatest common divisor (GCD) of a and b is the biggest integer g such that  a/g and b/g is “exact” (leaves no residue, this g is always a positive integer).   This GCD is very easy to calculate even that a and b are thousands of bits (this is how RSA public keys are being compared on the internet to find repeated factors in them and vulnerate its corresponding private keys)
The way of calculating the GCD number is really straightforward, for instance in python recursively as easy as:
        def gcd(a,b):
               if(b==0):
                       return a
               else:
                       return gcd(b,a%b)

Where % is the modulo operation in python, this is explained in (c).  GCD(a,b)=1 means that a and b share no factors and 1 is the biggest divisor of both.


b) A fact from highschool: The polynomial  $latex x^{2n}-1$   factors as  $latex (x^n + 1)(x^n -1)$. This is something you all know from highschool as difference of squares.

c) Modular arithmetic: $latex A=B \bmod N$   means “B is the residue of dividing A/N” and this residue of course is always strictly less than N.


d) Periodicity of modulo operation: Take any integer a, and build the sequence $latex a^0, a^1, a^2, a^3,\ldots, a^k\bmod N$ (this is a sequence “reduced” modulo N, which means dividing by N each element in the sequence and inserting the residue).

This list will be periodic eventually since N is finite. (patterns in the sequence will appear)
For example take N=14 the sequence $latex \lbrace 3^0, 3^1, 3^2, 3^3, 3^4, 3^5, 3^6, 3^7, 3^8,\ldots\rbrace\bmod 14$ is reduced to $latex \lbrace 1,3,9,13,11,5,1,3,9,\ldots \rbrace$.

This “signal $latex 3^x \bmod 14$” has period 6 since $latex 3^{x+6} \bmod 14 = 3^x \bmod 14$  for all x (in highschool you see for example that $latex\sin(x)$ has period $latex 2\pi$ since $latex \sin(x)=\sin(x+2\pi)$

e) Fourier transform of periodic function: If you have a periodic signal and you feed it to a Fourier transform, this will output a function where in the x-axis you will have the frequencies of the original data. In the y-axis the magnitude (size) of the periodic data. 
To find the longest period of a signal, since Period = 1/Frequency (highschool) you just need to find all the highest amplitudes (y values) and check its corresponding x-coordinate (frequency)  and transform it to period. This is 1/x to get the period of the original high amplitude y value (you are interested in the highest period). For example, if you have a high Y value (amplitude), and its x-coordinate X is 0.1428 HZ then 1/X=1/0.1428 = 7 ( and the period is P=7).


Factorization Algorithm using periods mod N 
INPUT (An integer N to Factorize), OUTPUT (A factor)

  1. Pick a random $latex x$ between $latex 2$ and $latex N$
  2. If $latex g=\gcd(x,N)\geq 2$ then return $latex x$ (since $latex g$ is greater than $latex 1$ and $latex \gcd(x,N)$ is a common divisor of $latex N$, we found accidentally a factor $latex g$ which is improbable)
  3. Calculate the sequence $latex S:=\lbrace x^0, x^1, x^2, \ldots, x^N\rbrace \bmod N$ (this is a quantum step which is done in a quantum register in one cycle)
  4. Calculate the period $latex P$ of $latex S$ using quantum fourier transform (this is the same as the fourier transform but using quantum parallelism which for now you see as a blackbox since this is the fast part that is calculated in 1 Cycle on a quantum processor, since it is done using the physical nature of the processor)
  5. If $latex p$ is not even, goto  step 1  ($latex P$ will be even with high probability, this is a deep mathematical number theoretical argument)
  6. Since $latex P$ is the period, we have that $latex x^P \equiv 1 \bmod N$. Further since $latex P$ is even, put “1” in the other side of the previous equality and using (b) above we can factor       $latex (x^{P/2}+1)(x^{P/2}-1) \equiv 0 \bmod N$  .
  7. Since $latex (x^{P/2}+1)(x^{P/2}-1) \equiv 0 \bmod N$  this means that the left hand side of the equation leaves 0 residue when divided by $latex N$ (see c) above). This means that at least one of both factors shares a factor with N. This factor is one (or both) of $latex \gcd((x^{P/2}\pm 1),N)$.
Therefore, $latex f=\gcd(x^{P/2}+1) , N)$  OR $latex f=\gcd(x^{P/2}-1),N)$ is a factor of $latex N$ and Voila.

Example, factorizing N=15 using the previous algorithm:

We will factor the number 15 by hand using the previous algorithm.
  1. We pick randomly $latex x=7$
  2. We have that $latex \gcd(15,7) = 1$ therefore, we can stay with our choice of $latex x$ since this $latex x$ does not share factors with $latex N$, we verify this quickly (even that $latex N$ or $latex x$ have thousands of bits) as:
>>> N=15
>>> x=7
>>> from math import gcd
>>> gcd(N,x)
1

  1. We calculate the sequence $latex S=\lbrace 7^0, 7^1, \ldots , 7^N\rbrace \bmod N=15$
>>> N=15
>>> x=7
>>> S=[]
>>> for k in range(0,N+1):
...     S.append((x**k)%N)
...
>>> S
[1, 7, 4, 13, 1, 7, 4, 13, 1, 7, 4, 13, 1, 7, 4, 13]

  1. We use the Fourier transform to calculate the period $latex P$ of $latex S$ looking at the frequencies (x coordinates) of the highest amplitudes (y coordinates). We can see this visually below (ignore the high frequency at 0.0 which is infinity and it is a technicality).
Note that the period of $latex S$ seems to be 4 just by looking the sequence $latex S$, but we do not know that, and in real life sequences will be much larger, and this is a toy example.
>>> import numpy as np
>>> S = np.array(S)
>>> fourierS=np.abs(np.fft.fft(S))
>>> freqdomain = np.fft.fftfreq(S.size,d=1)
### WE PLOT THE SIGNAL AND THE FOURIER TRANSFORM OF IT
>>> import matplotlib.pyplot as plt
>>> plt.subplot(2,1,1)
>>> plt.plot(np.arange(S.size), S, 'r--')
>>> plt.subplot(2,1,2)
>>> plt.plot(freqdomain,np.abs(fourierS),'ro')
>>> plt.show()



Look that the frequency coordinate (in the x axis) of one of the highest amplitudes (in the y axis). In the Fourier spectrum, the marked high amplitude has frequency 0.250737 (x coordinate).  Using the highschool formula 1/Freq = Period we have that 1/0.250737  is 3.99  (which is rounded to 4) and this is the highest period $latex P$ of the original signal (we already knew it was 4 but we are literally looking at the frequency through Fourier analysis).   

  1. We saw that the highest amplitude (interpret it as highest length of a period of S, since there are a lot of small periods within our signa, for example 1,7 repeats also or 7,4,13 too with some gaps) has frequency 0.2507 Hz in the Fourier spectrum, and the period P was obtained by 1/T=P as 1/0.2507 which is 3.99 ~= 4 so the highest period P=4.
  1. We calculate  $latex x^{P/2} + 1$ and $latex x^{P/2} - 1$, namely $latex 7^2 + 1$ and $latex 7^2 - 1$  which are 50 and 49 respectively. Further, we check for common factors with $latex N$ (recall by b) and 7. above that $latex x^P \equiv 1 \bmod N$ since the signal has period $latex P$) and therefore $latex x^P-1 = (x^{P/2}+1)(x^{P/2}-1) \equiv 0 \bmod N$.
>>> P=4
>>> from math import gcd
>>> gcd(x**(int(P/2))+1,N)
5
>>> gcd(x**(int(P/2))-1,N)
3
>>> 


  1. Voila, we have the factors 5 and 3.

There are some technicalities to explain when the signal is cut suddenly at the end without finishing the “wave” , the period needs to be approximated since it wont be exact, but it is a matter of rounding correctly.

A more serious calculation using the fourier spectrum is for a 4 digit number


Using another technique to calculate periods via convolution:



Source code and more information

Source code that finds the periods using Fourier and other implementation with discrete Convolution (faster). Screenshots for more complex factorizations are in http://ff2.nl/quantum-factorization/

Eduardo Ruiz Duarte (beck)
toorandom@gmail.com
twitter: @toorandom