Home » Tutorials » When prime numbers are one after another…

Today, different software use semiprime numbers to encrypt your message or data in general. A semiprime number consists in a product of two large prime numbers. This idea is used because large semiprime numbers are very hard to factorize.

In cryptography, there are different ways to factorize a semiprime number, from the high-school 1 to sqrt(n) algorithm to general number field sieve. But, there is also an algorithm to factorize the semiprime number easily if the prime numbers are one after another or close.

Let’s name the two prime numbers p and q and the semiprime number m. So, we get the following equation:

1
p * q = m

We also know Goldbach’s Conjecture that states that the result of any two prime numbers added together is an even number which we will call 2n. So…

1
p + q = 2n

When adding this two equations together and removing q, we will come up with:

1
p^2 - 2pn + m = 0

Solving the equation will reveal:

1
2
p = n - sqrt(n^2 - m)
q = n + sqrt(n^2 - m)

This two equations are really interesting because:
• p and q are integers
• sqrt(n^2 – m) must be an integer number, so (n^2 – N) must be a perfect square

To start cracking, we will calculate n as ceiling(sqrt(m)) and increment it until n^2 – m is a perfect square.

The algorithm for this method is the following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
<?php
//The semiprime number m passed in the console
$m = $argv[1];

//Steps used in the algorithm
$steps = 0;

//Condition to start
$cond = 1;

//Calculating n as ceiling(sqrt(m))
$n = ceil(sqrt($m));

//The good part where we verify if the number
//(n^2 - m) is a perfect square

while($cond == 1)
{
    $steps++;
    $nr = $n*$n-$m;
    if((int) sqrt($nr) == sqrt($nr))
    {
        $cond = 0;
    }else{
        $n++;
    }
}  

echo "p=" . ($n + (sqrt($n*$n-$m))) . "\n";
echo "q=" . ($n - (sqrt($n*$n-$m))) . "\n";
echo "Steps: " . $steps . "\n";

Leave a Reply

Your email address will not be published. Required fields are marked *

*
*