requesting permission to post the code

smslca

I have written a C code program for factorization of a given number into two divisors, when the two divisors are having approximately the same number of digits . It cannot check for prime numbers.

With my code limit I can check it only upto 14 digits using long long int. It is working perfectly upto these 14 digits (condition is the two divisors must have app the same no.of.digits). Bigger than 14 digits it is yielding wrong answers.

with the permission of this forum I like to post the code here. So that someone can check its efficiency for large numbers.

If anyone's idea is to use GMP libray, I have already installed gmp using msys, and had written a C code program using gmp. The problem I faced is, when I compiled the program , it compiled perfectly. But when I selected to Run the code, It says "Project is stopped working". The problem is in input and output code lines i.e., I used printf and scanf functions to get o/p and i/p.
To avoid this problem I did not find any best tutorial on GMP. And I did not understand what he is saying about the o/p and i/p functions, in the Documentation of GMP-5.0.1.
If you accept to post the code using gmp , I will post that also.

Thankful for the forum mentors and moderators and users , If accepted to post the code. And for any replies given.

LeixlipRed

Yeh, no problem.

smslca

Here is the code.

#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<process.h>
#include <time.h>
main()
{
time_t result;
long long int a,b=0,x=0,y=0,z=0,c,c1,d,e,f,p,n1n2,l=0,p4,p7,p8,p 9,disc;
double t=2,n11,m[100],p6,p5=1,p11=1,x1,x2,p1,p2;
double sqtr();

FILE *filea1b_3 = fopen("filea1b_3.txt" , "w");
printf("Enter the value of P : ");
scanf("%I64u",&p);
printf("So , Given P = %I64u . \n\n\n\n",p);
fprintf(filea1b_3, "So , Given P = %I64u . \n",p);
p1=sqrt(p);
p4=p1;
p6=p1-p4;
if(p6>0)
{
for(a=2;(p5&&p11)>0;a++)
{
x++;
f=a*a;
for(b=1;b<f;b++)
{
if((p-b)%a==0)
{
y++;
n11=(((p+b)-(sqrt(4*p*b)))/(a*a));
p4=n11;
p5=n11-p4;
p6=n11-p5;
p7=p6;
for(c=1;c<=(b/2);c++)
{
if(b%c==0)
{
z++;
c1=(b/c);

disc=((b+(a*a*p7)-p)*(b+(a*a*p7)-p))-(4*a*c*a*p7*(b/c));/*to find discriminant*/
if(disc>0)/*distinct roots*/
{
x1=(p-b-(a*a*p7)+sqrt(disc))/(2*a*(b/c));
x2=(p-b-(a*a*p7)-sqrt(disc))/(2*a*(b/c));
}
if(disc==0)/*Equal roots*/
{
x1=x2=(p-b-(a*a*p7))/(2*a*c);
}
if(disc<0)
{
x1=(p-b-(a*a*p7))/(2*a*c);/*complex roots*/
x2=sqrt(fabs(disc))/(2*a*c);
}
p4=x1;
p5=x1-p4;
p6=x1-p5;
p8=p6;
p4=x2;
p11=x2-p4;
p6=x2-p11;
p9=p6;
if((p5==0)||(p11==0))
{
n1n2=x1*x2;
d=x+y+z;
e=(p-b)/a;
printf("\n\nNo.of.loops = %I64u\n",d);
printf("a = %I64u, b= %I64u, N = %I64u, N1 = %f, N2 = %f, N1N2 = %I64u",a,b,e,x1,x2,n1n2);
printf("\n\nb1 = %d and b2 = %d (or) b1 = %d and b2 = %d\n\n",c,c1,c1,c); 
fprintf(filea1b_3, "\n\nNo.of.loops = %I64u\n",d);
fprintf(filea1b_3, "a = %I64u, b= %I64u, N = %I64u, N1 = %f, N2 = %f, N1N2 = %I64u",a,b,e,x1,x2,n1n2);
fprintf(filea1b_3, "\n\nb1 = %d and b2 = %d (or) b1 = %d and b2 = %d\n\n",c,c1,c1,c); 
getch();
exit(0);
}
}
}
if((p5==0)||(p11==0))
{
exit(0);
}
b=b+a-1;
}
}
}
}
else 
{
printf(" Given number is a perfect square");
printf(" P = %f^2 ",p1);
fprintf(filea1b_3, " Given number is a perfect square");
fprintf(filea1b_3, " P = %f^2 ",p1);
}
getch();
}

As I said the two divisors should be closer to each other in terms of no.of.digits. This will give one factor and the other will be given number divided by the above obtained factor. It will not work on prime numbers.

here factor is (aN1+b1) if we got N1 as an integer . or (aN2+b1) if we got N2 as an integer.
Here b1 = anyone of the b1 values we got in the answer.

Any replies given will be helpful to me . thanks.

smslca

Sorry for reposting the same code. I am reposting the code with explanation using the comments in the program.

#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<process.h>
#include <time.h>
main()
{
      time_t start,end;
  char szInput [256];
  double dif;
      long long int a,b=0,x=0,y=0,z=0,c,c1,d,e,f,p,n1n2,l=0,p4,p7,p8,p9,disc;
      double t=2,n11,m[100],p6,p5=1,p11=1,x1,x2,p1,p2;
      double sqtr();
      
      FILE *filea1b_3 = fopen("filea1b_3.txt" , "w");//Start of a file named filea1b_3.txt
     
      printf("Enter the value of P : ");// Enter your P value to be factorized. 
                                       //And we must know that the no.of .dgits of two divisors of P must be approximately of equal values. 
                                       //This is our input 
      scanf("%I64u",&p);
      
      printf("So , Given P = %I64u . \n\n\n\n",p);
      fprintf(filea1b_3, "So , Given P = %I64u . \n",p);
      
      time (&start);     // start of the time to calculate time taken to get the answer
      fprintf(filea1b_3, "So , Given P = %I64u . \n",p);
      
      
      p1=sqrt(p);// this is not necessary , It is to check wether given P is a perfect square or not.
      p4=p1;
      p6=p1-p4;
      
      if(p6>0)// If not a perfect square
      {
      for(a=2;(p5&&p11)>0;a++)
      {
                      x++;
                      f=a*a;
                      for(b=1;b<f;b++)
                      {
                                          if((p-b)%a==0)
                                          {
                                                        y++;
                                                        n11=(((p+b)-(sqrt(4*p*b)))/(a*a));
                                                        // this is the equation that calculates the product of N1 and N2 values in
                                                        //  P = ((a*N) + b) = [ ((a*N1)+b1) * ((a*N2)+b2) ]
                                                        
                                                        // Here a , b are integer values taken to run the loops , and b = ( b1 *b2 )
                                                        p4=n11;
                         p5=n11-p4;
                         p6=n11-p5;
                         p7=p6;
                                                        for(c=1;c<=(b/2);c++)
                                                        {
                                                                         if(b%c==0)
                                                                         {
                                                                                        z++;
                                                                                        c1=(b/c);
                         // below is the roots of an equation f(N1) or f(N2). There is no condition one must come first
                         // because as from the equation of P, N1 and N2 are equally interchangeable variables
                         disc=((b+(a*a*p7)-p)*(b+(a*a*p7)-p))-(4*a*c*a*p7*(b/c));/*to find discriminant*/
if(disc>0)/*distinct roots*/
{
x1=(p-b-(a*a*p7)+sqrt(disc))/(2*a*(b/c));
x2=(p-b-(a*a*p7)-sqrt(disc))/(2*a*(b/c));
}
if(disc==0)/*Equal roots*/
{
x1=x2=(p-b-(a*a*p7))/(2*a*c);
}
if(disc<0)
{
x1=(p-b-(a*a*p7))/(2*a*c);/*complex roots*/
x2=sqrt(fabs(disc))/(2*a*c);
}
p4=x1;
                         p5=x1-p4;
                         p6=x1-p5;
                         p8=p6;
                         p4=x2;
                         p11=x2-p4;
                         p6=x2-p11;
                         p9=p6;
                         if((p5==0)||(p11==0)) // this is condition to check wether we got an answer or not 
                         {
                                         n1n2=x1*x2;
                                         d=x+y+z; // No .of. loops taken to get an answer .
      e=(p-b)/a;
      
      // This is the of output of our work 
      
      printf("\n\nNo.of.loops = %I64u\n",d);
      
      
      printf("a = %I64u, b= %I64u, N = %I64u, N1 = %f, N2 = %f, N1N2 = %I64u",a,b,e,x1,x2,n1n2);   
      printf("\n\nb1 = %d and b2 = %d (or) b1 = %d and b2 = %d\n\n",c,c1,c1,c); 
      // Here we will get values of the required values of
      // " a" , "two values of b1 " , " b2 = 0 " , and the integer value of either N1 or N2.
      // So If we got N1 as an Integer ,  Then one of the divisor is (aN1+b1) 
      // If we got N2 as an Integer ,  Then one of the divisor is (aN2+b1) 
      // Here b1 is any one of the two values we got .
      // So another divisor is ( P / (aN1+b1) ) or (P / (aN2+b1))
      
      fprintf(filea1b_3, "\n\nNo.of.loops = %I64u\n",d);
      fprintf(filea1b_3, "a = %I64u, b= %I64u, N = %I64u, N1 = %f, N2 = %f, N1N2 = %I64u",a,b,e,x1,x2,n1n2);
      fprintf(filea1b_3, "\n\nb1 = %d and b2 = %d (or) b1 = %d and b2 = %d\n\n",c,c1,c1,c); 
      
      gets (szInput);
  time (&end);       // End of the loops and displays the time taken to complete the process
  dif = difftime (end,start);
  printf ("It took you %f seconds to execute the program.\n", dif );
  fprintf (filea1b_3, "It took you %f seconds to execute the program.\n", dif );
      getch();
                                                                                       exit(0); // If we got an answer exit the loops and
                                                                                                // display the answers.
                                                                                       }
                                                                                       }
                                                                                       }
      if((p5==0)||(p11==0))
                         {
                                                                                       exit(0);
                         // always (b1*b2) = b ( mod a ) 
                         // So here I have taken  b = b1*b2 = b+a-1                                                          }
                         b=b+a-1;
                         }
                         }
      }
      }
      }
      else 
      {
      printf(" Given number is a perfect square"); // If given P is a perfect square.
      printf(" P = %f^2 ",p1);
      fprintf(filea1b_3, " Given number is a perfect square");
      fprintf(filea1b_3, " P = %f^2 ",p1);
      }
      getch();
      }

smslca

A pal named rpenner in sci forum, had rewritten the code, may be now you can understand what I intended to do in the code with his code.

#include <stdio.h>
#ifdef windows
#include <conio.h>
#endif
#include <math.h>
#ifdef windows
#include <process.h>
#endif
#include <time.h>
#ifndef windows
#include <stdlib.h>
#endif

#define INPUT_BUFFER_SIZE 256

#ifndef windows
int
#endif
main()
{
  time_t start_time;
  char ignored_input_buffer [INPUT_BUFFER_SIZE];
  long long int input_number;
  long long int trial_square;
  long long int floor_misc, floor_n11;
  double trial_diff, trial_square_root;
  double left_difference=1, right_difference=1;
  double n11;

  FILE *output_fp = fopen("filea1b_3.txt" , "w"); //Start of a file named filea1b_3.txt

  printf("Enter the value of P : "); // Enter your P value to be factorized. 
  //And we must know that the no.of .dgits of two divisors of P must be approximately of equal values. 
  //This is our input 
  scanf("%I64lld", &input_number);

  printf("So , Given P = %I64lld . \n\n\n\n", input_number);
// warning: ISO C does not support the 'I' scanf flag
// warning: ISO C does not support the 'I' printf flag

  fprintf(output_fp, "So , Given P = %I64lld . \n", input_number);

  time (&start_time);     // start of the time to calculate time taken to get the answer
  fprintf(output_fp, "So , Given P = %I64lld . \n", input_number);


  // This dependence on doubles and squareroot breaks for
  // 9223372030926249000 which is not a perfect square.
  trial_square_root=sqrt((double)input_number); // this is not necessary , It is to check wether given P is a perfect square or not.
  trial_square = trial_square_root;
  trial_square *= trial_square; // Bug -- this line was missing
  trial_diff=input_number-trial_square;

  if(trial_diff>0)// If not a perfect square
  {
    long long int trial_center;
    long long int loop_counter_one = 0;
    long long int loop_counter_two = 0;
    long long int loop_counter_three = 0;
    for(trial_center = 2; left_difference && right_difference; trial_center ++)
    {
      long long int ballast;
      loop_counter_one ++;
      trial_square = trial_center * trial_center;
      for(ballast = 1; ballast<trial_square; ballast ++)
      {
        if((input_number-ballast)%trial_center == 0)
        {
          long long int ballast_left; // One factor of ballast
          loop_counter_two++;
          n11 = (((input_number + ballast)-(sqrt(4.0 * input_number * ballast)))/(trial_square));
          // this is the equation that calculates the product of N1 and N2 values in
          //  P = ((trial_center*N) + ballast) = [ ((trial_center*N1)+b1) * ((trial_center*N2)+b2) ]

          // Here trial_center , ballast are integer values taken to run the loops , and ballast = ( b1 *b2 )

          floor_misc = n11;
          left_difference=n11-floor_misc;
          floor_n11=n11-left_difference;

          for(ballast_left=1; ballast_left<=(ballast/2); ballast_left++)
          {
            if(ballast%ballast_left==0)
            {
              long long int ballast_right=(ballast/ballast_left); // Other factor
              long long int discriminant;
              long long int floor_x1, floor_x2;
              double x1, x2;
              loop_counter_three++;
              // below is the roots of an equation f(N1) or f(N2). There is no condition one must come first
              // because as from the equation of P, N1 and N2 are equally interchangeable variables
              discriminant=((ballast+(trial_square*floor_n11)-input_number)*(ballast+(trial_square*floor_n11)-input_number))-(4*trial_square*ballast_left*floor_n11*ballast_right); /*to find discriminant*/
              if(discriminant>0)/*distinct roots*/
              {
                x1=(input_number-ballast-(trial_square*floor_n11)+sqrt((double)discriminant))/(2*trial_center*ballast_right);
                x2=(input_number-ballast-(trial_square*floor_n11)-sqrt((double)discriminant))/(2*trial_center*ballast_right);
              }
              else if(discriminant==0)/*Equal roots*/
              {
                x1=x2=(input_number-ballast-(trial_square*floor_n11))/(2*trial_center*ballast_left);
              }
              else /* if(discriminant<0) */
              {
                x1=(input_number-ballast-(trial_square*floor_n11))/(2*trial_center*ballast_left); /*complex roots*/
                x2=sqrt(fabs((double)discriminant))/(2*trial_center*ballast_left);
              }

              floor_misc=x1;
              left_difference=x1-floor_misc;
              floor_x1=x1-left_difference;

              floor_misc=x2;
              right_difference=x2-floor_misc;
              floor_x2=x2-right_difference;

              if((left_difference==0)||(right_difference==0)) // this is condition to check wether we got an answer or not 
              {
                long long int n1n2 = x1*x2;
                // No .of. loops taken to get an answer .
                long long int total_loop_count = loop_counter_one
                  + loop_counter_two
                  + loop_counter_three;
                time_t end_time;
                double elapsed_time_seconds;
                long long int n_for_output =(input_number-ballast)/trial_center;

                // This is the of output of our work 

                printf("\n\nNo.of.loops = %I64lld\n", total_loop_count);


                printf("trial_center = %I64lld, ballast= %I64lld, N = %I64lld, N1 = %f, N2 = %f, N1N2 = %I64lld\n", trial_center, ballast, n_for_output, x1, x2, n1n2);   
                printf("\n\nb1 = %I64lld and b2 = %I64lld (or) b1 = %I64lld and b2 = %I64lld\n\n", ballast_left, ballast_right, ballast_right, ballast_left); 
                // Here we will get values of the required values of
                // " trial_center" , "two values of b1 " , " b2 = 0 " , and the integer value of either N1 or N2.
                // So If we got N1 as an Integer ,  Then one of the divisor is (trial_center N1+b1) 
                // If we got N2 as an Integer ,  Then one of the divisor is (trial_center N2+b1) 
                // Here b1 is any one of the two values we got .
                // So another divisor is ( P / (trial_center N1+b1) ) or (P / (trial_center N2+b1))

                fprintf(output_fp, "\n\nNo.of.loops = %I64lld\n", total_loop_count);
                fprintf(output_fp, "trial_center = %I64lld, ballast= %I64lld, N = %I64lld, N1 = %f, N2 = %f, N1N2 = %I64lld\n", trial_center, ballast, n_for_output, x1, x2, n1n2);
                fprintf(output_fp, "\n\nb1 = %I64lld and b2 = %I64lld (or) b1 = %I64lld and b2 = %I64lld\n\n", ballast_left, ballast_right, ballast_right, ballast_left); 

                fgets (ignored_input_buffer, INPUT_BUFFER_SIZE, stdin);
                time (&end_time);       // End of the loops and displays the time taken to complete the process
                elapsed_time_seconds = difftime (end_time, start_time);
                printf ("It took you %f seconds to execute the program.\n", elapsed_time_seconds );
                fprintf (output_fp, "It took you %f seconds to execute the program.\n", elapsed_time_seconds );
#ifdef windows
                getch();
#endif
                exit(0); // If we got an answer exit the loops and
                // display the answers.
              }
            }
          }
          if((left_difference==0)||(right_difference==0))
          {
            exit(0);
            // always (b1*b2) = ballast ( mod trial_center ) 
            // So here I have taken  ballast = b1*b2 = ballast+trial_center-1
            ballast=ballast+trial_center-1;
          }
        }
      }
    }
  }
  else 
  {
    printf(" Given number is a perfect square\n"); // If given P is a perfect square.
    printf(" P = %f^2 \n", trial_square_root);
    fprintf(output_fp, " Given number is a perfect square\n");
    fprintf(output_fp, " P = %f^2\n", trial_square_root);
  }
#ifdef windows
  getch();
#endif
  exit(0);
#ifndef windows
  return 0;
#endif
getch();
}

Here trial_center = a ; ballast = b; and all others are same.

Thomas_S_Hunterson

I take it this doesn't expose any vulnerability in RSA then?
:P