### Pseudoprimes: construction methods

In this post we're going to look at several methods for generating various kinds of pseudoprimes and we're also listing some open-problems that motivate the generation of such numbers.

By
Daniel Șuteu

In this post we're going to look at some algorithms for checking if a given number is either prime or composite. Édouard Lucas , Leonhard Euler , Carl Pomerance and Pierre de Fermat Prime numbers play an important role in public-key cryptography (e.g. RSA algorithm ) which require fast generation of large random prime numbers that have around `600` digits (or more). The simplest way to generate a prime number, is to pick a random odd integer and check its primality, repeating this process until a prime is found. This approach requires a fast algorithm for checking the primality of a number. In 2002, Manindra Agrawal , Neeraj Kayal , and Nitin Saxena published the AKS primality test , unconditionally proving that the primality of a number can be checked in polynomial time, with an asymptotic time complexity of `Õ(log(n)^12)`. Later on, in 2005, Carl Pomerance and Hendrik Lenstra improved the complexity of the AKS algorithm to run in just `Õ(log(n)^6)` steps.

By
Daniel Șuteu

The Fibonacci sequence is, without doubt, one of the most popular sequences in mathematics and in popular culture, named after Italian mathematician Leonardo of Pisa (also known as Fibonacci , Leonardo Bonacci, Leonardo of Pisa, Leonardo Pisano Bigollo, or Leonardo Fibonacci), who first introduced the numbers in Western European with his book Liber Abaci , in 1202.

By
Daniel Șuteu

RSA is a practical public-key cryptographic algorithm, which is widely used on modern computers to communicate securely over large distances. The acronym of the algorithm stands for Ron Rivest , Adi Shamir and Leonard Adleman , which first published the algorithm in 1978. # Algorithm overview Choose `p` and `q` as distinct prime numbers Compute `n` as `n = p*q` Compute `\phi(n)` as `\phi(n) = (p-1) * (q-1)` Choose `e` such that `1 < e < \phi(n)` and `e` and `\phi(n)` are coprime Compute the value of `d` as `d ≡ e^(-1) mod \phi(n)` Public key is `(e, n)` Private key is `(d, n)` The encryption of `m` as `c`, is `c ≡ m^e mod n` The decryption of `c` as `m`, is `m ≡ c^d mod n` # Generating `p` and `q` In order to generate a public and a private key, the algorithm requires two distinct prime numbers `p` and `q`, which are randomly chosen and should have, roughly, the same number of bits. By today standards, it is recommended that each prime number to have a