Hi, I have recreated Fermat's alg for factorising numbers using GMP's bignum. However when I try to factor extremely large numbers e.g.3049818439605086085304554688619895660771188041 327
I get an 'abort trap'
Can anyone tell me - What is an abort trap?
I have no problem with numbers up until then.
My code is below.
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include "gmp.h"
clock_t start, end;
double cpuTime;
void fermat(mpf_t n){
mpf_t a, b, bsq, p, q, result, asq, sqrtbsq, ceil_sqrtbsq, a_sub_sqrtbsq, a_add_sqrtbsq, sqrtbsq_sub_ceilsqrtbsq;
int compValue;
mpf_t sqrtn;
mpf_init(a);
mpf_init(asq);
mpf_init(b);
mpf_init(bsq);
mpf_init(p);
mpf_init(q);
mpf_init(result);
mpf_init(sqrtn);
mpf_init(a_sub_sqrtbsq);
mpf_init(a_add_sqrtbsq);
mpf_init(sqrtbsq);
mpf_init(ceil_sqrtbsq);
mpf_init(sqrtbsq_sub_ceilsqrtbsq);
start = clock(); /*starts timing CPU Time*/
/*based on the belief that (a^2 - b^2) = n*/
mpf_sqrt(sqrtn, n); /*calculates root n*/
mpf_ceil(a, sqrtn); /*a = ceil(sqrt)*/
mpf_mul(asq, a, a); /*sets asq to a*a*/
mpf_sub(bsq, asq, n); /*sets bsq to asq-n. These 2 lines equivalent of : bsq = (a*a) - n;*/
mpf_sqrt(sqrtbsq, bsq);
mpf_ceil(ceil_sqrtbsq, sqrtbsq);
mpf_sub(sqrtbsq_sub_ceilsqrtbsq, sqrtbsq, ceil_sqrtbsq); /*sets sqrtbsq_sub_ceilsqrtbsq to sqrt(bsq) - ceil(sqrt(bsq))*/
//compValue = mpf_cmp_ui(sqrtbsq_sub_ceilsqrtbsq, 0); /*compares sqrtbsq_sub_ceilsqrtbsq and 0 for while loop*/
while(compValue!= 0){
compValue = mpf_cmp_ui(sqrtbsq_sub_ceilsqrtbsq, 0); /*compares sqrtbsq_sub_ceilsqrtbsq and 0 for while loop*/
/*while b squared isnt a square number we increment a until it is*/
mpf_add_ui(a, a, 1); /*a++*/
mpf_mul(asq, a, a);
mpf_sub(bsq, asq, n); /*//bsq = (a*a) - n;*/
mpf_sqrt(sqrtbsq, bsq);
mpf_ceil(ceil_sqrtbsq, sqrtbsq);
mpf_sub(sqrtbsq_sub_ceilsqrtbsq, sqrtbsq, ceil_sqrtbsq);
//compValue = mpf_cmp_ui(sqrtbsq_sub_ceilsqrtbsq, 0);
}
/*once bsq becomes a squared number, we return a - root(bsq) and a+root(bsq)*/
/*p = a - sqrt(bsq);*/
mpf_sub(p, a, sqrtbsq);
/*q = a + sqrt(bsq);*/
mpf_add(q, a, sqrtbsq);
end = clock(); /*Stops timing CPU Time*/
cpuTime= (end-start)/ (CLOCKS_PER_SEC);
//mpf_set(q, a_add_sqrtbsq);
printf("Efficiency - CPU TIME\n");
printf("%lf\n", cpuTime);
gmp_printf("%Ff %Ff\n", p, q);
/*result = p * q; */
mpf_mul(result, p, q);
}
int main(void){
mpf_t n;
mpf_init;
gmp_scanf("%Ff", n);
fermat;
}
Cheers. Very grateful!
I get an 'abort trap'
Can anyone tell me - What is an abort trap?
I have no problem with numbers up until then.
My code is below.
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include "gmp.h"
clock_t start, end;
double cpuTime;
void fermat(mpf_t n){
mpf_t a, b, bsq, p, q, result, asq, sqrtbsq, ceil_sqrtbsq, a_sub_sqrtbsq, a_add_sqrtbsq, sqrtbsq_sub_ceilsqrtbsq;
int compValue;
mpf_t sqrtn;
mpf_init(a);
mpf_init(asq);
mpf_init(b);
mpf_init(bsq);
mpf_init(p);
mpf_init(q);
mpf_init(result);
mpf_init(sqrtn);
mpf_init(a_sub_sqrtbsq);
mpf_init(a_add_sqrtbsq);
mpf_init(sqrtbsq);
mpf_init(ceil_sqrtbsq);
mpf_init(sqrtbsq_sub_ceilsqrtbsq);
start = clock(); /*starts timing CPU Time*/
/*based on the belief that (a^2 - b^2) = n*/
mpf_sqrt(sqrtn, n); /*calculates root n*/
mpf_ceil(a, sqrtn); /*a = ceil(sqrt)*/
mpf_mul(asq, a, a); /*sets asq to a*a*/
mpf_sub(bsq, asq, n); /*sets bsq to asq-n. These 2 lines equivalent of : bsq = (a*a) - n;*/
mpf_sqrt(sqrtbsq, bsq);
mpf_ceil(ceil_sqrtbsq, sqrtbsq);
mpf_sub(sqrtbsq_sub_ceilsqrtbsq, sqrtbsq, ceil_sqrtbsq); /*sets sqrtbsq_sub_ceilsqrtbsq to sqrt(bsq) - ceil(sqrt(bsq))*/
//compValue = mpf_cmp_ui(sqrtbsq_sub_ceilsqrtbsq, 0); /*compares sqrtbsq_sub_ceilsqrtbsq and 0 for while loop*/
while(compValue!= 0){
compValue = mpf_cmp_ui(sqrtbsq_sub_ceilsqrtbsq, 0); /*compares sqrtbsq_sub_ceilsqrtbsq and 0 for while loop*/
/*while b squared isnt a square number we increment a until it is*/
mpf_add_ui(a, a, 1); /*a++*/
mpf_mul(asq, a, a);
mpf_sub(bsq, asq, n); /*//bsq = (a*a) - n;*/
mpf_sqrt(sqrtbsq, bsq);
mpf_ceil(ceil_sqrtbsq, sqrtbsq);
mpf_sub(sqrtbsq_sub_ceilsqrtbsq, sqrtbsq, ceil_sqrtbsq);
//compValue = mpf_cmp_ui(sqrtbsq_sub_ceilsqrtbsq, 0);
}
/*once bsq becomes a squared number, we return a - root(bsq) and a+root(bsq)*/
/*p = a - sqrt(bsq);*/
mpf_sub(p, a, sqrtbsq);
/*q = a + sqrt(bsq);*/
mpf_add(q, a, sqrtbsq);
end = clock(); /*Stops timing CPU Time*/
cpuTime= (end-start)/ (CLOCKS_PER_SEC);
//mpf_set(q, a_add_sqrtbsq);
printf("Efficiency - CPU TIME\n");
printf("%lf\n", cpuTime);
gmp_printf("%Ff %Ff\n", p, q);
/*result = p * q; */
mpf_mul(result, p, q);
}
int main(void){
mpf_t n;
mpf_init;
gmp_scanf("%Ff", n);
fermat;
}
Cheers. Very grateful!