Primes are a fascinating group of integer numbers. They definition is short and clear (a prime number is a number that can be divided without remainder only by itself and 1), there are infinite primes and “quite frequent” (for number of n digits they are about n/(log n), so one number every log n is… Continue reading Mersenne Primes and Perfect Numbers
Tag: prime numbers
Integer Factoring – Quadratic Sieve
SPOILER ALERT!!! Long and boring article, quite technical, it is in preparation to a Java implementation of the QS that will be included in the Factoring App presented in this site. So far the Java library is not yet ready, but it is under development. In previous posts we saw something about integer factorization, in… Continue reading Integer Factoring – Quadratic Sieve
Pollard’s Rho Factoring Method
Finally it comes the weekend and you can go to the mountain, but as soon as you exit home and you reach the car you find a 2256+1 sleeping on the hood. You try to move it but it is too heavy. Oh no, again! you’ll have to factor it so you can move smaller… Continue reading Pollard’s Rho Factoring Method
Trial Division and Eratosthene’s Sieve
Let’s suppose you change telephone number. Almost surely the first thing you think is “is my new phone number prime?”. Since the number is small the naive method “let’s try to divide the phone number by all numbers less than it” is good (at least if you do it with the computer). You can improve… Continue reading Trial Division and Eratosthene’s Sieve
