Factoring large integers: classical method
RSA strength depends on the difficulty to find prime factors of large integers and this is why these kind of algorithms gain a lot of attention.
Take an RSA key of 512 bits [ RSA-512 ]….
The GNFS (Generalize Number Field Sieve) algorithm needed 2 months and 10 days to be completed:
- 2 months for the sieving part on 300 PC 400 MHz with 64Mb di RAM ( for an equivalent of 8000
MIPS-Year ) - 10 days on a Cray C90 to compute the matrix
Having t = ( time to compute 2^512 )
A simple calculus shows that we neeed:
- LOG(2^576) / LOG(2^512) = 10.9 -> 10.9 * t for a 576 bits RSA key
- LOG(2^1024) / LOG(2^512) = 7 * 10^6 * t for a 1024 bits RSA key
- LOG(2^2048) / LOG(2^512) = 9 * 10^15 * t for a 2048 bits RSA key
As we can see from this results, time required for a 2048 bits key is near the eternity;
even if we have 10^6 computers time required to compute a 2048 bits key is 9 * 10^9 bigger
than time required for a 512 bits key… so it is out of our possibilities.
Note that the best algorithm for integer factorization is NFS ( Number Field Sieve ).
Now we’ll take a look to the classical ( and slowest ) method for integers factorization to understand the complexity of this problem.
Classical method algorithm
- N >= 2
- S = square root of N ( we take only the integer part )
- Divide N / K (with K odd , K > 1 and K < S)
- If K is a divisor of N we have found a prime factor of N and then N = N / K Restart from 2.
Classical method implementation
The following program need GMP (GNU Multi Precision) library
Compile: gcc cfmi.c -o cfmi -lgmp
/*****************************************************************************/
/* This program is free software; you can redistribute it and/or modify */
/* it under the terms of the GNU General Public License as published by */
/* the Free Software Foundation; either version 2 of the License, or */
/* (at your option) any later version. */
/* This program is distributed in the hope that it will be useful, */
/* but WITHOUT ANY WARRANTY; without even the implied warranty of */
/* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
/* GNU General Public License for more details. */
/* */
/* You should have received a copy of the GNU General Public License */
/* along with this program; if not, write to the Free Software */
/* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
/*****************************************************************************/
/* (c) 2003 by Paolo Ardoino <paolo.ardoino@gmail.com> */
/*****************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <gmp.h>
int main(int argc, char *argv[])
{
unsigned long long int tmpui = 0;
mpz_t N, sqrt, tmp, ctr;
struct timeval tm0, tm1;
if (argc != 2) {
fprintf(stderr, "CFMI - Classical Factorization Method \
Implementaion.\n");
fprintf(stderr, "Usage: %s <N>\n", *argv);
fprintf(stderr, "\t<N>: integer to factorize.\n");
exit(EXIT_FAILURE);
} else if (*(argv + 1)){
mpz_init_set_str(N, *(argv + 1), 10);
if (mpz_cmp_ui(N, 1) <= 0) {
fprintf(stderr, "Errot: Please insert N >= 2");
exit(EXIT_FAILURE);
}
gmp_printf("N = %Zd\n", N);
mpz_init(tmp);
gettimeofday(&tm0, NULL);
/* Tries to compute m = N mod 2 */
/* if m == 0 => 2|N [2 is a factor of N] */
while (mpz_mod_ui(tmp, N, 2) == 0) {
printf("Factor = 2\n");
mpz_div_ui(N, N, 2);
}
/* Checks if N == 1 */
if (mpz_cmp_ui(N, 1) == 0) {
mpz_clear(tmp);
mpz_clear(N);
gettimeofday(&tm1, NULL);
printf("Factorization has been completed in %ld seconds.\n",\
tm1.tv_sec - tm0.tv_sec);
exit(EXIT_SUCCESS);
}
/* Checks if N is prime */
/* Uses a probility primality test that has */
/* probabity of failure == 0.25 ^ x [here x == 10] */
if (mpz_probab_prime_p(N, 10) > 0) {
gmp_printf("Factor = %Zd\n", N);
mpz_clear(tmp);
mpz_clear(N);
gettimeofday(&tm1, NULL);
printf("Factorization has been completed in %ld seconds.\n",\
tm1.tv_sec - tm0.tv_sec);
exit(EXIT_SUCCESS);
}
mpz_init(sqrt);
mpz_init_set_ui(ctr, 3); /* sets ctr = 3 */
mpz_sqrt(sqrt, N);
if (mpz_odd_p(sqrt) == 0)
mpz_add_ui(sqrt, sqrt, 1);
/* while ctr < sqrt(N) */
while (mpz_cmp(ctr, sqrt) < 0) {
while (1) {
mpz_mod(tmp, N, ctr);
if (mpz_cmp_ui(tmp, 0) == 0) {
gmp_printf("Factor = %Zd\n", ctr);
mpz_div(N, N, ctr);
mpz_sqrt(sqrt, N);
if (mpz_odd_p(sqrt) == 0)
mpz_add_ui(sqrt, sqrt, 1);
} else
break;
}
mpz_add_ui(ctr, ctr, 2);
if (mpz_cmp_ui(N, 1) == 0) {
mpz_clear(tmp);
mpz_clear(N);
mpz_clear(ctr);
mpz_clear(sqrt);
gettimeofday(&tm1, NULL);
printf("Factorization has been completed in %ld seconds.\n",\
tm1.tv_sec - tm0.tv_sec);
exit(EXIT_SUCCESS);
}
if (mpz_probab_prime_p(N, 10) > 0) {
gmp_printf("Factor = %Zd\n", N);
mpz_clear(tmp);
mpz_clear(N);
mpz_clear(ctr);
mpz_clear(sqrt);
gettimeofday(&tm1, NULL);
printf("Factorization has been completed in %ld seconds.\n",\
tm1.tv_sec - tm0.tv_sec);
exit(EXIT_SUCCESS);
}
}
}
return 0;
}
Download this code: classical.txt
Results of classical method
HARDWARE :
CPU model name : AMD Athlon(TM) XP 2000+
CPU MHz : 1666.240
CPU cache size : 256 KB
CPU bogomips : 3322.67
RAM MB : 512 MB
RAM MHz : 266 MHz
SOFTWARE :
Operative System : Gentoo GNU/Linux [kernel v2.6.2]
cfmi.c : my implementation of the classical method
RESULTS :
N[integer to factorize]: 3369738766071892021 [2^64]
Factor: 204518747
Factor: 16476429743
Factorization has been completed in 1115-1142 seconds.
