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

3. 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]

4. 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).   

5. 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.

6. 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

>>> 

7. 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

Why finding big prime numbers? why study weird arithmetic sequences?

Now I am sitting on my desk thinking on a technique to help me to identify BIG prime numbers in certain arithmetic sequences using algebraic geometry.

This was part of my last project for my PhD, which I think it was very interesting. When I say "BIG" I mean thousands of digits, maybe millions.  When I say "primes in arithmetic sequences" I mean to separate prime numbers in a list like $latex \{ \alpha_n \}_{n=0}^\infty$.

A popular, a prostituted, an important and a "dumb" sequence.

Now we will describe some non trivial sequences and we will see a glimpse of why they are important (or not).

This is of course in my opinion, since there are infinitely many sequences which I ignore and could be more interesting. In fact there is a sequence of "uninteresting numbers" which contains all numbers which appear to not have known/interesting properties (like being prime, Mersenne prime, triangular number, cube, etc...).
But well, this sequence then..., is interesting as is unique, and then we get a paradox.

The popular sequence

The popular is a very famous arithmetic sequence, and is the "Mersenne Sequence", $latex \{ 2^n-1\}_{n=1}^\infty\subset\mathbb{N}$.

$latex \{ 2,7,15,31,63,127,255,...\}$

This is the sequence of all Mersenne numbers.  We denote by $latex M_n$ to the number $latex 2^n-1$.
To identify the primes in this sequence, note that if $latex n=2k$ (is even) then $latex 2^n-1=(2^k-1)(2^k+1)$ and hence... not a prime number. This means that in the sequence we can discard all the values $latex n\in 2\mathbb{Z}$, that is $latex M_{2k}$ is not prime. A less trivial fact is that if $latex n$ is composite, namely $latex n=ab$ then we have that:

 $latex 2^n-1=2^{ab}-1=(2^a-1)(\sum_{k=0}^{b-1}2^{ka})=(2^b-1)(\sum_{k=0}^{a-1}2^{kb})$

and then also $latex M_{pq}$ is not prime. So, we are left with all the elements in the sequence of the form $latex M_p$ for $latex p$ a prime number. A quick inspection says that $latex M_2, M_3, M_5, M_7$ are Mersenne primes. But $latex M_{11} = 2047 =23\cdot 89$ which is not prime. So, which Mersenne numbers are prime ?

This is a difficult question, there are big computer grids working in this, trying to find the most spectacular prime. The biggest Mersenne prime known, (and Biggest Prime in general) is $latex 2^{74207281}-1$. which has 22.3 million digits approximately. The way to check it without putting so much effort in the algebraic geometric or number theory rigor is the following:

 To check that $latex 2^p -1$ is prime:

Consider the sequence $latex \{ \sigma_1=4, \sigma_2=14,...,\sigma_j=(\sigma_{j-1}^2)-2...\}$
then $latex M_p=2^p-1$ is prime if and only if $latex \sigma_{p-1}\equiv 0 \bmod M_p$.

This is the fastest way known today. is called the Lucas-Lehmer test.
There are other elegant tests (but not necessarily faster) using elliptic curves which I knew its existence when I was talking with Benedict Gross at the conference on L-Functions at Harvard the past year, and in some sense I have to do something similar as part of my PhD program.

The prostituted

Another famous and prostituted sequence is the so called "Fibonacci sequence".

$latex \{ 1,1,2,3,5,8,13,...,F_{n-1}+F_{n-2}, ...\} $

This is famous and is always presented as the building blocks of beauty in the universe. This just an exaggeration, but well, that is another story.

Is known that $latex \lim_{n\to\infty} \frac{F_{n}}{F_{n-1}}=\phi=1.618033...$.

This number $latex \phi$ has the property that squared is equal to $latex \phi+1$ so, is appears as a root of the polynomial $latex x^2 -x -1=0$.
The value of $latex \phi$ can be found when you divide lengths of middle lines in some polygons by the length of the sides. Also in your body, if you divide your height by the distance of your feet to your belly button, and in a lot of parts of our body. This number can be analyzed in a Leonardo da Vinci drawing called "Le proporzioni del corpo umano secondo Vitruvio" which can be seen here.
This is why $latex \phi$ has some kind of mystic and esoteric significance for some people, and that is why is called sometimes The Golden Ratio. 

To identify primes in the Fibonacci sequence, there are no good ways. This is mainly because the sequence highly depends on the "addition" operation and not "multiplication", and believe it or not, addition in number theory is a mystery.
A very important Conjecture in mathematics about this mystery, predicts the possible relation between the multiplication and the addition of integers, through its prime factorization, called the abc conjecture, so Fibonacci, is difficult as a problem in terms of primality, but as seen, has more significance in geometry.

The important sequence

Now for the important sequence is this

$latex \{2, 1729, 87539319, 6963472309248, 48988659276962496, 24153319581254312065344...\}$

Do you see it?

Well, is not too easy to see, is called the "Hardy-Ramanujan sequence", if you denote by $latex \tau(n)$ the $latex n^{th}$ element of the sequence, it means that $latex \tau(n)$ can be written in $latex n$ different ways as a sum of two cubes. Fermat Proved that there are infinitely many of these numbers hundreds of years before, but they caught the attention of Hardy by Ramanujan in a very nice story.

When Ramanujan was dying at the hospital in England, Hardy went to visit him. Hardy told him that the number in his taxi to the hospital was a dull, boring number, 1729. Ramanujan said:

 'No, Hardy, it is a very interesting number. It is the smallest number expressible as the sum of two cubes in two different ways' 

That is why we use the letter $latex \tau$ because these numbers are called "taxicab numbers" because of this story.

The importance of these numbers, is the new theory in arithmetic geometry that arose,  which in fact I am very interested personally, and professionally.

Practically Ramanujan discovered in his way of thinking, an integral solution to the equation $latex x^3+y^3=z^3+w^3$ which nowadays is studied over $latex \mathbb{Q}$ and then twisted.

This kind of surfaces are called K3 Surfaces (Kodaira-Kummer-Kahler, smooth minimal complete surface with trivial canonical bundle), there is no smart way of obtaining these numbers other than using this algebraic geometry in these surfaces. An example of these surfaces with a family of rational curves parametrized  (the curves may contain taxicab solutions in it) is:

  

And yeah 1729 has the desired property, that is, $latex \tau(2)$ is a sum of two cubes in only two different ways. 

Srnivasa Ramanujan was a human computer, in fact to verify this, we check for the $latex \tau(2)=1729$ and $latex \tau(6)=24153319581254312065344$ can be written as the sum of 2 cubes in 2 and 6 different ways respectively:

$latex \begin{matrix}\tau(2)&=&1729&=&1^3 + 12^3 \\&&&=&9^3 + 10^3\end{matrix}$

...
$latex \begin{matrix}\tau(6)&=&24153319581254312065344&=&582162^3 + 28906206^3 \\&&&=&3064173^3 + 28894803^3 \\&&&=&8519281^3 + 28657487^3 \\&&&=&16218068^3 + 27093208^3 \\&&&=&17492496^3 + 26590452^3 \\&&&=&18289922^3 + 26224366^3\end{matrix}$

The "dumb" sequence

There are plenty other sequences, for example, there are some "dumb" sequences that at the end... they are not so dumb, for example, consider the following sequence:

$latex \{1, 11, 21, 1211, 111221, 312211, 13112221, ... \}$

Do you see the pattern?

Well, the pattern is visual, you begin with "1" and then the following will be the "description of the previous", that is, you ask yourself "What symbols are in the preceding element of the sequence?", and you say "one one" (11) then the next is "two ones"  (21), and so on... This sequence is called "look and say sequence".

There are a lot of things you can do in your spare time with this sequence, for example, prove that a "4" cannot appear in any element of the sequence. The number 13112221 is in fact the biggest prime known in this sequence, are there others?

This apparently dumb sequence has an amazing property which transforms it from dumb to analytic and it was due to John Conway.
Consider the $latex k^{th}$ element of that sequence, call it $latex a_k$  , and define $latex \ell(a_k)=$number of digits of $latex a_k$.
Is proved that $latex \lim_{n\to\infty} \frac{\ell(a_k)}{\ell(a_{k-1})}=\lambda=1.303577269034...$. The surprising thing is that $latex \lambda$ is an algebraic number that can be found as a root of a polynomial of degree 71. This was proved by John Conway, for more information, look at wikipedia.


But why?, why you want to find big primes or classify properties of sequences?


 I have been questioned plenty of times "Why you want to find big primes?", today was one of these days where a master student asked me.
There is a FALSE answer which is very popular among a lot of people, namely

 "It has cryptographic applications, since prime numbers are the basis for today's e-commerce and the development of cryptographic schemes" 

This is false, since cryptographic schemes for public key cryptography need prime numbers with no more than 1000 decimal digits (and this is already too long). Using more than 1000 digits maybe would be more secure, but the speed will decrease exponentially, that is why you don't use 1 million bits of security.

 Identifying these "cryptographic" prime numbers at random with certain properties (Like being a Sophie-Germain prime) to generate a public key with 4096 bits which has approx 1234 digits, (which is already paranoid for the public techniques of cryptanalysis) takes less than a second in my workstation (try: time openssl genrsa 4096).
 So, cryptography is not a good excuse to generate BIG prime numbers, when I say big, I mean thousands of digits, millions.


The answer in my case is easy... To collect them...  they are difficult to find, but they are present in a lot of shapes, for example in the last sequence, which elements are prime ? which is the biggest known ? how to identify them with geometric techniques?.

That is how the theory in mathematics is born, with a question regarding classification.

So, finding big primes is difficult, so is valuable, there are only 49 Mersenne Primes and nobody has proved that they are infinite. (but is believed heuristically that they are).

A couple of years ago I wrote here about finding a big prime of the form $latex 3\cdot 8^n -1$ , which I found here, there are a lot of possible primes disguised in infinitely many shapes, you could just define whatever recursive relation and analyze it.

Other people could say to test a big cluster, or to get some money (yes you get money if you break the records). Maybe an analytic number theorist could say To understand more the distribution of prime numbers which is unknown.

Conclusion

So well in conclusion, I think is good to collect primes and analyze sequences. This to find something hidden in the unknown nature of the logic of sequences of natural numbers, since, we don't know yet how the prime numbers arise. There is still a mystery of how the prime numbers are distributed among all the natural numbers,  even with quantum computers is hard to find them arbitrarily large, so there are still work to do in mathematics.

For more information of all the known published sequences (yes, whatever you think will be there) go to www.oeis.org, this is the Online Encyclopedia of Integer Sequences.


Eduardo Ruíz Duarte (beck)
twitter: @toorandom

Encontrando números primos grandes con approach matemático-computacional

Si estás de un smartphone no se verán los símbolos, probablemente quieras verlos así que haz click aquí

Recientemente me vi en la necesidad de encontrar algunos números primos grandes de la forma $latex (3*8^n)-1$ por una cuestión de un problema de geometría aritmética y primality testing, quiénes creo que se podrían interesar en esto fueron en Facebook Esteban Gutierrez y Manuel López Michelone quiénes comentaron sobre esto, un análisis rápido te dice que ese número es primo para $latex n\in \lbrace 1,2,6,72,1092,5687 \rbrace$ pero otro análisis no tan rápido que hice fue para descubrir $latex n=17129$, estos número para el ojo inocente parecerían inofensivos, pero para $latex n=17129$ nos encontramos con un número de 16,000 dígitos aproximadamente, y ahora mi workstation está checando $latex >n=35000$ que son como 32,000 dígitos decimales, es decir 105,000 bits, tardándose aproximadamente 30 minutos por cada thread (hice 32 POSIX-threads) entonces me arroja aproximadamente 32 resultados cada media hora, y el tiempo sube por cada iteración logarítmicamente, así que si sigo así pronto comenzará a tardar horas, el código lo voy a publicar ahorita, así que encontrarán las ligas al final de este post para que lo corra cualquier linuxero, o mejor decir... "POSIXERO" ya que toda el api que uso al final es POSIX compliant y para manejar números grandes y hacer aritmética uso BN  (Bignum) de OpenSSL que considero es lo más rápido ya que se usa en la industria, el código detecta tus procesadores y usa TODOS, así que tomalo en cuenta con el nice, tiene macros para funcionar en OSX (Apple) ya que pthread_set_affinity_np() y CPU_SET funcionan diferente.

La pregunta matemática sería:

¿Existen una cantidad infinita de números primos de esta forma?


Ahora explicaré cómo lo hice para que sea lo más óptimo que se me pudo ocurrir.

1. Construir número optimamente

$latex (3*8^n)-1$ lo podemos fabricar en binario en vez de calcularlo, con esto nos evitamos muchos ciclos del procesador


Por un lado tenemos que $latex 8^n=2^{3n}$  y $latex 2^m=1000...000B$ con $latex m$ $latex 0$'s eso significa que $latex 8^n$ tiene $latex 3n$ ceros y un $latex 1$ al principio, después multiplicar por $latex 3$ es lo mismo que sumar $latex 3$ veces $latex 1000...000B$ el cual será el número $latex 11000...000B$ con $latex 3n$ ceros y restar $latex 1$ será negar todos los ceros y el segundo $latex 1$ por lo que va a quedar    $latex (3*8^n)-1=10111...111B$   donde el número de $latex 1$'s menos significativos es $latex 3n$ , con esto ya no tenemos que calcular exponenciación que es muy costosa.

2. Ignorar números que nos harán perder el tiempo

Sucede MUY frecuentemente que $latex (3*8^n)-1$ es múltiplo de $latex 5$ , esto es fácil verlo
ya que si $latex 3*8^n$ termina en $latex 6$ o $latex 1$ entonces $latex (3*8^n)-1$ es múltiplo de $latex 5$, pero no puede terminar en $latex 1$ porque $latex 3*8^n$ es par, y para que termine en $latex 6$ como $latex 8^n$ termina en $latex 8,4,2,6,8,4,2,6,8,...$ (en ese orden comenzando con n=1) nos interesa saber cuándo $latex 8^n$ termina en $latex 2$ para que $latex 3*8^n$ termine en $latex 6$ y por consiguiente $latex (3*8^n)-1$ sea múltiplo de $latex 5$.

Un chequeo rápido y respaldado por la propiedad inductiva en los número naturales sobre $latex n$ tenemos que $latex 8^n$ termina en $latex 2$ si $latex n=3,7,11,15$ es decir si $latex n=4t-1$ y más computacionalmente si $latex n\equiv 3 \mod 4$ o más humano "si $latex n-3$ es múltiplo de $latex 4$" entonces esto nos dice que podemos eliminar automáticamente 25% de todos los exponentes al checar $latex (3*8^n)-1$ ya que serán múltiplos de $latex 5$

3. Optimizar test de primalidad y utilizar números más familiares para una computadora

Una vez construido el número, y filtrados los exponentes que hacen trivialmente compuesto al número, necesitamos ver que lo que tenemos en efecto sea un número primo.

Para hacer esto nos auxiliaremos en el pequeño teorema de Fermat el cual lo escribo diferente a Fermat para que se entienda dice:

Teorema de Fermat
Si $latex p$ es primo y $latex mcd(p,a)=1$ $latex \Rightarrow$ $latex a^p - a$ es múltiplo de $latex p$

Equivalente

Si $latex p$ es primo y $latex mcd(p,a)=1$ $latex \Rightarrow$ $latex a^{p-1} \equiv 1 \bmod p$

Esto es lo mejor que tenemos y lo peor es que existe la posibilidad de un "falso positivo"
ya que el teorema aquí ya supone que $latex p$ es primo, es decir estamos checando una propiedad que tiene un número primo siempre, pero podría tenerla otro número también ya que el teorema no es un "si y sólo sí" $latex \Leftrightarrow$ , pero para nuestra fortuna, los números que cumplen la propiedad de Fermat y no son primos son "strong pseudo-primes" , "Fermat Liars" y son raros, de hecho yo prefiero Números de Carmichael quién fue el que los estudió y para nuestra fortuna, no hay tantos y son raros, y si nos toparamos con un "posible primo" , cambiamos la $latex a$ del teorema de Fermat y volvemos a probar y si también se cumple la congruencia, es ya casi un hecho que lo que tenemos es primo.

Pero bueno aún podemos optimizar MÁS , vamos a optimizar el teorema de Fermat, ya que como pueden ver... vamos a tener que elevar un número (en mi caso 2) a la $latex x$ donde $latex x$ es un número de más de 30 mil dígitos, módulo es número de 30 mil dígitos... afortunadamente existen algoritmos para hacer esto en tiempo logarítmico pero aún así es tardado, así que si podemos eliminar más ciclos sería bueno.

Tenemos que $latex x=(3*8^n)-1$ nunca es el número primo $latex 2$ así que podemos suponer que es impar sin ningún problema , por un lado tenemos que $latex a^{x-1} \equiv 1 \bmod x \Leftrightarrow a^{x-1} -1 \equiv 0 \bmod x$ si $latex x$ es primo,  ahora,  $latex x-1=2k$ es decir es par, entonces $latex a^{x-1}-1 = a^{2k}-1 = (a^k -1)(a^k + 1) \equiv 0 \bmod x$ (diferencia de cuadrados), como $latex k=\frac{x-1}{2}$ entonces tenemos  que $latex (a^{\frac{x-1}{2}}-1)(a^{\frac{x-1}{2}}+1) \equiv 0 \bmod x$ lo que significa que para que se cumpla Fermat, tiene que suceder que $latex a^{\frac{x-1}{2}}\equiv 1$ ó $latex -1 \bmod x$ donde $latex -1\equiv x-1 \bmod x$ y con esto reducimos 1 ciclo más en la exponenciación modular que es muy costosa, y usamos $latex a=2$ ya que la exponenciación por 2 sólo es shifting a la izquierda, y usando 2 es hermoso para el algoritmo de exponenciación modular porque la complejidad
$latex o(3kn^{1.585})$ (Multiplicación Karasuba y reducción Montgomery para mod_exp hasta donde sé que usa BN de OpenSSL) esperada baja considerablemente teniendo muchos 0's en su expresión lo que reduce pasos (por eso la $latex o(g[n]))$ y no la $latex O(g[n]))$),  donde $latex 3k$ es el número de bits de $latex x$ (nota aquí que la $latex n$ representa la variable de complejidad y no el exponente), y con eso hemos encontrado los primos que mencioné al principio.

Espero opiniones, source code aquí

Eduardo Ruíz Duarte
twitter: @toorandom

Por Morbo aquí les dejo el más grande que he encontrado, tardó 3 minutos en 1 thread. el cual es $latex (3*8^{17129})-1$ el cual tiene 51,388 bits .

32026423315381466050277915530786335800393823366890894981259290036648161553494994617558347456939958845983080809781780843277379143842511321157300439716316621258468518963948059640880521931439098619360470902127202739263724498727354638561114775469410152002760785630729882805025686247898899808911618409162136670680087277684487378095087887490583145258613139912396900825975697214682477274814156070359889110867811362193110348467393951992492345402056332383241386444305433601523085645869776811285646919087537466338016988423008766811472396005675392998881736916741912590189429331612837325373810452416030933831306867192676710269198951414458490437515264053051733873759760089225408336099284078093859455689148594434825613934497979781554179399202461221624253778300943176804460380502043924360948006335930676276227451427823493631843987911309636588431232386671032205960984005755897461961694816343511105402244581305974926489787769176727530282950574991748927557944410793100152205427813737629867224719749629559616541154571702402344007533555385071678935056951177266337611794442895925353683999178922756717467868112921444235536843814816587988381808259378763566339936575469133821904985670022768297621487042685072937645035397418762898088879966518834617431717616238160653229933317675561804324889864152610093010599664552103022407658203362826225135467122903372349775404454265894274031612183834433948175013815731731843768742711463425691140151259964862216909975488504743216033971257070468582283917816001081411729083210816836157717534301930744010414980424399802727757779067704711766548222713340284109481557728641051371992861091880789035561130198577315011688318769929786698521625431301832480788848469161536541203402106348915684835706031086198583470841503903548287043913330764995542582104558499052946524398642023915418094252775225135009392516216639788849081686649422414816420666524703609315132700144025576596698848194947599190340291543335651139477044320381872498206346425778242974783028340973498127326252357750612335602225108453954123859141624811742539990879575619773935510158546410141054095024924790241748920937072243685910974276469625883231365286281146397745282169224983577575852655025299677792623835241690537842870710528349067292463062257545894983725514137453620357976030228008635191305568411517021214777322011903026859601083554815240483942419038213153965732868181464332882027463093394450027202039114912743513771018541173505400069482374254318086098853632651567194952960545899057851574317234825560325729148747127013748646167661011675033243786731813402924344723783663066299906756407070530905173417647177285662615563890874013554204722859804826783319723895173795270908631147615754087439314263020476261354882689909166015907511051623119212879465867556909644440100632138353562083646966088393779513894343599588950053243809581940981833880678424982730382004328421941439072636800592877300140048085384317222361179303861645355317608391899423839079837905186750572454810469022406363372588948686204901139113299980435620209872045747933603059130972696653746953604532417492903736570671296699105655923819429995588811467179873672852431251204448040809915863163514335540089427059903930482164420870043452193744616222493706789929016164765070777799153453961045107726915484605407070139659338306471198522417856040168525001743452798331018200032516982674115924542207247561332705748100446483628681758170277861279289599258673198185708528378663459785909178096390845218020629053192057841759202932782309711814026123607150376911940748135836533906883752444763036721353897269880408805386078398045366480484951224112577584082675114895273853399084137327610229509328970706333462386945933615225142344089090446121520471032079274695108327379700854569636711391422529411618554876423454704114335714668077792468687086576736091448314825802520170346995090349720987439473605228224586805882340461196462558836145583970685095961833008585739864656363328302986709618224658592061790170440213776071852284933724917317499943202018446618210793294932831097623750797416246378349485892742882242489517967732592792481355599182598675646982241076442612020185511034050637482303910568507849800434585110875928913264144917561728507483873787584779156636819491649231469052768465384827615887208338319057096162237372005045429022403914234522895948109125618822616830011877945500320746041816052399512404707120200149549307311742265568523260555270588190891088146372739404374609532572772005797711009523114710103299579557147452176909952118545682110695102391553837852971501889513088222486987723921202415262209457238513791459203972870093386953048894801746214435712103477352922752928791906655786957516121929344278692478022077201558938914429157414192182892992028571663350174293119784111516284937872290882995528284151163236783105238160116300616254926975435140120536460294894410442753982342285715596774450547688510540950609379199176038748244276624271511162021898465702381739554745903292368453929023793055915664947937134935491330980718736217997428692810379092480664406511201873764269913663647020985956314161402000383439218120742135271552526071319102832539386295104448025731371374719348527163508063409657644511483601027063141269736285818775573658317881599404287364002332020457775029972569361743675624369268068117893284658209857784788545339202829190234333573510725635332114732388415720177686698830992999310828225254838530442450211498457933037804583792899416998160092466471334917779332924285621209393547865615433381452726968988212217944363239160938499077454607308202875136763555648760496640998480414396908114196518199386149585672336456043989071695238312288960081259962428139207487337862311363664235353355741056558668800464140710661218731996083813228309464181512824198473099835338147549021620784938152526403884390915371010004103078720376198785754267231632364475196249423028430296607633185992949806664821669508769010395593020867265768241356602352619944658174291464218293290651513925863985300257092863217772635441366596007681209046202751531928654365904486480637896037524609924560756737487555941653455392568655608180047527596306525572672891104374795309986323951969131709938262130944930794116800383445065248433923593381063574380087876957452711241937139283341986739106521622406898428983948046724085183024676505731621744665800497853221066191995732134553165719198648689135257528892602964255853707448817858352523437863421426102418117389544983206042308860683466269434657391645604299058196009634534319799146142598318942762623665930578733123571550032271299551114477333140685887321380068779030520881901530995711544355981117803607975968517499227648018428854655983473350493961762777920029051990792375397413824629029725111324189020468036861701447775824977257286314969930798035433627722690476216793743259593862757494785251530728454141362285932172007019448646822993271982444067467511428273397361690368237878111466206232963438330207726200080194611554342535208143831928801129239615572665628913222777854337631162257572382401793069038204155873152194648221501879285765056884379731159884546949750078461272929585042335506924134975880741347636497891449035978435021137529059174101402963872488774055561871763906005995523112899268150145675230528838855491232516570415185657872854886290162991073611832895236728088095860213006479909366614293585377658649333618462661081337250855184818048918280095216771124919354017900316074686948848666096561888434199822022864315541727689104723180042673931538717736387214138023901177682380480573112291135017398314529185431570271124814738098761072609216606999034113642258974107978719402360004973983466905902220813267671856406327086943579910433158637016416320152392435734326402865259058273022480138148188943021020384024506061902144679691028765137048209827552145995276652839943973336959426861497791033259830231723590523648498835822832310074455043040176962529346513059433633982359304138147553887485074486267391219132827142128335706403319422134084444025461591415872438467681229654425434633494593254114591133359674756811870187942825563687040492646952300630610982000264767473553602225155962233169190888460758352343896019871785984159532458130055709200931106493045763269590995530937189497063631830785082964079799523231260807321064954724345171548330473944837948003158443648883656429657821491956256504263890572005938508038381077649008380039581215475512164674386754377503163134803108273243041775665133283203530877641413091640784342349226191942006609524592938809381209539984692931251689753565266660069225820293301694201093380755714940533267406389212538472737345389920939638830120261737007640910540478856973611235739472554054732492599378321173386948659654872894505995568627052612775511578286760509286861768721974406755260200693773145017206683870773831784040386709044145859000178680454409827037232424821580153078526733906602635501448413155506471616532000380246549340334416808898434387410310767186271678651657125956330997135514287078037552835249014425147171712299257324870293646478104446879005854587240740583374971104742080118407293376250478292379654435036077102162699707316802765421226043298626360886593259957682295399635161319003729817233310836488878679452228196539460170236747951470219093715468757201428276567346844650203948349754588389125473669983324294915461031237867790032803164212486116627265051342591429261672735326004971500809554757104809198941710250369014929980399788042439092012739807413496910294722408654685906467188445652852679463510111588848714966994012633053111140523488797686496074404075035403032823629222238696411817644483300212092444148203586311124377532534089957832358357772985060452544714354695728594506029245228474290363244268026739022540462324210220094777074046735835916531079392171548754284909023490741942672576020109502086289324949189131229866882158751044579431073510058638580112970399400848012598667869946183555382577600203193941610086977918428282164298924318017243031208758208540683610170253540720335918689087434714730194564568976981777204445322986698373283390613470588168852889384592420528734963148995278955127941606122747080059367271673385322580445859123918237395666091441934678389289512890922392344993878800705035425791621906338667172499766162845453799509129825300440130012452422744967544346925837444005229552678073813615644879122257996997585678579511199674812593313238824764101761027353677321483720341880084732506793520846691464229711911399127721595694352403218401554932929595580588474107092800484536679906402882561774736289011712497922621582368337057910519632385879773294033551311658003580394298225128044755081583957070106775832608786270843701706632218236607363754573786689965846170399266338261414148862926960078807493024676636241821780944571096941752160727585488941102816572881758376655843234513616963008536787097251683013326148161450318083878017455643651554618261609966657262498344963281756373673269194825457120102335098430053525126126433050268325257610505256130462410397690925472067734961438549322304026644954794880041403058925796970496923953825506922111728360818654368875624837101641043903975798923440983174868771201734139437540847299331370990285604146267866907128889409552307757336422613848203004832657228332873404485085691176592522515171277306509004682948792277048468532631094588527157849361469770828540588429898016076708761086577687829794189995013320624862541504004344723993123491408236967534492449686611053666809249670558680801820699727271874125672980265867805587536003161611257602573879807891275145042611104947170932266106091329413068356104455079652564819613052988898269750866283631671361118418750456959898175596314235967214072736323242812555211430437013788931433823216158115282033550906925064093752025137605666797295274782995312635995982152649414790767022457876214220333912735265753742268349688660929764774270479063514369370861571597970542022613471507522362653019693799529912763689666033819469364626587974886877639192115375028613651480474237164637235577738383600508857173217109336525549418866366010878280531299766307762080753760829697569168773083049209471459983537669269749153891301730779513444000645411763110787536847848686483217045928561483760722316598284514141270858839546812101630071239179032956638848984251827861941056826930437770466758033287498621544428023782166008169892843744703334403973198509454469653826983957736270787015555281492220757292858206568385304706192386416009657097062675214919086924216423433082063409209311813441547525266882033030668389112810244305096535177323575119407014819701961205635561634299118583642973681614473867812760938254926147367318960324585092493458614097308885022089170245855482501639479877016629089888620237451538542215959748191190996154872699122004208858124356425712289922851204949134411296871871505058976506035287831568373306323310695563258651236862057327569996796911418552990931961498290680579647629977698154027601737797565070075670436437896473389755670610648189530779671896891147235752619825335341831322815436136245747406230116513486353562601815554701725083110004688886614174662693748369757301146366654631875732233511601846261172108525514149644247885971023535804115307394827643499777188215486121755438199799974589394310076094346886917173548688179362619895779807540625016179427636036019351588403299774724856215195371747489704244497091701187959447220506739300275179481331762578140018563599145933801046835852603238159978903048913593666079142988674647257869565599811291804268574482598601239002812924615248443546197951688030321300760876091551080394357570206848563007174933062203385569468701074474453445181914471929569957932053554812974962824730533730321134981872742052460822465894315329796485647981106519209011070672227096921158799879437700574304848454981802421492286924451866419782080313978740292819201278161706224217725190371403757643026425623517826097611507643390259047590959932320545975284905982569652107326483812384715289985015459922154716822488321689550299263619341284113403436700781861588646420485438604540704027253441622650851675586492071210226532484984591013815461270342863783178683556187689063539912330972619666981892869317909270155819553452716936453676065787164609958676345722669724366516240566266437213654002248924605767519825524209815555833816522154978528910130474700299093317031044211046499872477143240327616617922983636426879957616855080920171289624631399643044926826859302733475147604311961190699077188429263949513452638462772625523478131071010133683582732987635966888334444166545133327777444950723754056816509592356504697117206941441165086849098972184037539794426671844030825833598853963114053824272932540517635711466482759453660721092062140898635239403909145540034949144004169612367460203691048738979781621164967729498632571736651022575485003412715989505615918816044598119400139330568417038172877563337999983250824731788378825900711541921702608288945567177423468793416752642938061266551297859681355577376381057215722300869238366170358650342498421330507990183857556924897965345058959140779958958539450309245045806703864539795637542958885985702987995937529239296860784907341981603308133066795374351314700910108776438125912477798323517153710396153185384044296997650774166602334305686826095686072735997307216804515717706691064830830039274370337931442167526341392075205171338884374247627205672231641873433802187192310055109876868922197752744289994593440764759961686774526545765501935087092519809508864042914699268218861038321472400274858274379127887774609639024710710010354246368036753163679085955338782446481692502409390267529445980102117063380633877777427298698152522242904231639473660870716516498037296215852813557422423482411368716331820788501942447761707086086382920195423676221267291530130105693483847048880634760003583