## Prime Number derivation sieve

Another strange title of the project which I came across. To keep things simpler, it’s an ancient algorithm for finding all prime numbers up to any given limit. It does so by interactively marking as composite (i.e. not prime) the multiples of each prime, starting with the multiples of 2. The author made this wonderful project for his sister, who will be teaching Mathematics in high school. It features an LED matrix along with its driver and of course an arduino. The project was completely self-designed and that includes it covering box too which was design using a CAD tool. With the help of a 3-d printer, he designed the box after putting the sketch in a software called Ultimaker. Talking about the algorithm, it takes a square 2D array (in this case, let’s say of booleans), with each value originally set to true. Starting from 2, for every number that’s true, go through and set all multiples of that number to false. When you reach the end of the (outer) loop, all primes are true (and 1, which is… Continue reading

## FPGA based prime number generator for RSA encryption

RSA encryption and decryption algorithm operates with prime numbers. If are familiar with RSA encryption you know that here involves two keys – public and private. In order to generate these we need a two prime numbers p, q to calculate modulus n=pq. Prime numbers are numbers that has no other divisor than 1 and itself and is greater than 1. For instance prime numbers are 2, 3, 5, 7, … Finding prime number is a first task that FPGA has to do. There are many algorithms that may help finding prime numbers. Cornell university students are using Rabin-Miller Strong Pseudoprime Test probabilistic algorithm that allows to test if number is prime. With large numbers like 1231164598461316549… you cant test all division variants that would take endless time. Anyway theory is way deeper here that we are capable to cover. FPGA is pretty fast to take multiple tests on number to determine prime numbers. And as you guessed these numbers are used to generate RSA keys to encode message. NiosII soft processor is used to help with encryption. They also… Continue reading