[Solved]Instructions Assignment Modify C Program Called Fermatc Computes Non Trivial Factorization Q37196428

Instructions: Your assignment is modify a Cprogram called fermat.c so that it computes a non-trivialfactorization (if it exists) of an arbitrarily large composite oddnumber using Fermat’s method. The C program fermat.c provided onlycomputes factorizations for small odd numbers where the componentsstay under MAXINT.

You are to modify this program so that it uses the GMP libraryto compute the same factorization for arbitrarily large inputs.

To review, Fermat’s method is based on the observation that anodd number N can be factored simply by observing that:

N = (x – y)(x + y)
N = x2 – y2
x2 – N = y2

This suggests that you all might have to do in an algorithm isset some variable x to the first square above N,and then iterate over increasing squares until you find anx2 – N that is a perfect square:

subroutine factor(N){ x = ceiling(sqrt(N))^2 while(!perfect_square(x^2 – N)) { // try next x = x + 1 }}return(x + sqrt(x^2 – N), x – sqrt(x^2 – N))

Your task is to convert fermat.c to a program that uses GMP forall of its calculations, and should be able to factor such numbersas

    1 69036 16637 97588 93752 56792 74360 9919938989 63263 20951

(The above 51 digit number looks formidable, but it is a”special” number that is actually quite amenable to factorizationmethods based on Fermat’s algorithm.)

Your work product should be a file called “fermat-new.c”.

fermat.c:

#include <stdio.h>#include <math.h>#include <stdlib.h>#include <values.h>int main(int argc, char **argv){ int N = 0; if(argc > 1) { N = atoi(argv[1]); } else { printf(“Please specify a number to factor…n”); exit(1); } if(N <= 0) { printf(“‘%s’ doesn’t appear to be a number greater than zero…n”,argv[1]); exit(1); } int base,x,xsqr; int y,ysqr; base = sqrt(N); // check for square root if(base * base == N) { printf(“Factorization: %d = %d * %dn”,N,base,base); exit(0); } int count = 0; for(x = base+1; (float)x * (float)x < (float)MAXINT && (count < (2 * N)); x++) { xsqr = x * x; ysqr = xsqr – N; y = (int)sqrt((double)ysqr); if(y * y == ysqr) { // both x+y and x-y should be a factor of N int factor1, factor2; // check x+y factor1 = x+y; if((factor1 != N) && (factor1 != 1) && (N % factor1 == 0)) { factor2 = N / factor1; printf(“Factorization: %d = %d * %dn”,N,factor1,factor2); exit(0); } } count++; } printf(“No non-trivial factorization found for %dn”,N);}

Expert Answer

---

Answer to Instructions: Your assignment is modify a C program called fermat.c so that it computes a non-trivial factorization (if … . . .