// *************************************************************
// * Author: Tony Perrie
// * Date: 7/30/2001
// * File: rsa_576.C
// * Version: 0.001
// *
// * This is my first attemp at a distributed factoring 
// * application.  This program is fairly inefficient.  
// * It's merely an exhaustive approach to finding the
// * factors of an arbitrarily big number.
// * 
// * I'll hope to implement GNFS into this algorithm soon,
// * and make it run a bit faster.
// * 
// * You'll need libgmp, and the gmp source to compile this.  
// * libgmp source: ftp://ftp.gnu.org/gnu/gmp/gmp-3.1.1.tar.gz
// *
// * Here's my compile statement:
// * gcc /usr/lib/libgmp.so.3.1 -I./usr/src/gmp-3.1.1 rsa_576.C
// *
// * This algorithm lends itself very well to parallel execution.
// * Just run it with different ranges on different machines (or
// * processes on an SMP box).
// *
// * Change Log:
// * - Version 0.001:
// *   - 07/28/2001 - Created
// *   - 07/29/2001 - Added state support (don't lose previous computations). 
// *   - 07/30/2001 - Added comments.
// *
// * Future Changes:
// *   - Use a better sieve GNFS? (0.002)
// *   - Optimize execution speed (0.002)
// *   - Better results reporting (0.002)
// *   - Distributed client to send packets (0.004)
// *   - Distributed Server (0.020)
// *   - Tcl/tk front end (0.030)
// * 
// *************************************************************

#include <stdio.h>
#include <gmp.h>
#include <stdlib.h>
#include <string.h>

#define BASE 10               // Used to tell gmp the default base representation

int main() {

  mpz_t current;
  mpz_init_set_ui(current,0);

  mpz_t rsa_576;              // RSA-576 show me the money

  mpz_init_set_str (rsa_576, "188198812920607963838697239461650439807163563379417382700763356422988859715234665485319060606504743045317388011303396716199692321205734031879550656996221305168759307650257059", 0);

  FILE *fp;
  int i;
  unsigned start_exp = 299;   // The starting exponent - starting prime to test is 2 ^ start_exp
  unsigned end_exp = 300;     // The ending exponent - ending prime to test is 2 ^ end_exp
  unsigned rem6;              // Remainder six - this is used for avoiding primality tests on known composite numbers
  unsigned addend;            // This addend is also used in avoiding primality tests
  unsigned count=0;
  int probability;
  char cmd[]="cat factor-576.txt | mail name@domain.com -s \"Possible RSA-576 Factor\"";

  mpz_t start_num;
  mpz_init_set_ui(start_num, 0);

  mpz_t unity;
  mpz_init_set_ui(unity, 1);

  mpz_t end_num; 
  mpz_init_set_ui(end_num, 0);

  mpz_t six;
  mpz_init_set_ui(six, 6);

  mpz_t temp_rem;
  mpz_init_set_ui(temp_rem, 0);

  mpz_t iterator;
  mpz_init_set_ui(iterator, 0);

  mpz_t end_iterate;
  mpz_init_set_ui(end_iterate, 0);

  mpz_t complete;
  mpz_init_set_ui(complete, 0);

  fp = fopen("factor-576.txt", "r"); 
  if (fp != NULL) {
    mpz_inp_str(start_num, fp, BASE);
    fclose(fp);
  } else {
    fclose(fp);
    fp = fopen("factor-576.txt", "w"); 
    mpz_mul_2exp(start_num, unity, start_exp);
    mpz_out_str(fp, BASE, start_num);
    fclose(fp);
  }
  mpz_mul_2exp(end_num, unity, end_exp);
  rem6 = mpz_tdiv_r_ui(temp_rem, start_num, 6);
  while(rem6 != 1 && rem6 != 5) {  
    mpz_add_ui(start_num, start_num, 1);
    rem6 = mpz_tdiv_r_ui(temp_rem, start_num, 6);
  }
  addend = (rem6 == 1) ? 4 : 2;
  mpz_init_set(iterator, start_num);
  printf("Starting at -> ");
  mpz_out_str(stdout, BASE, start_num);
  printf("\nEnding at --->");
  mpz_out_str(stdout, BASE, end_num);
  //  printf("\n");
  //  printf("rem6 ---> %d\n", rem6);
  //  printf("addend -> %d\n", addend);
  // mpz_add_ui(end_iterate, start_num, 0xFFFFF);
  mpz_set(end_iterate, end_num);
  printf("\n");

  while(mpz_cmp(end_iterate, iterator) > 0) {
    probability = mpz_probab_prime_p(iterator, 5);
    ++count;
    if (probability>0) {       
      mpz_tdiv_r(temp_rem, rsa_576, iterator);
      if (count > 5000) {
	// printf("prob ---> %d\n", probability);
        printf("CHK: rem ----> ");
        mpz_out_str(stdout,BASE,temp_rem);
        printf("\n");
        printf("CHK: iter ---> ");      
        mpz_out_str(stdout, BASE, iterator);
        printf("\n");   
        count=0;
        fp = fopen("factor-576.txt", "w");  
        mpz_out_str(fp, BASE, iterator);
        fclose(fp);
        fp = fopen("factor-576a.txt", "a");  
        mpz_out_str(fp, BASE, iterator);
        fprintf(fp, "\n");
        fclose(fp);
      }
      if (mpz_cmp(temp_rem,six)<=0) {
        printf("!FND: rem -> ");
        mpz_out_str(stdout,BASE,temp_rem);
        printf("\n");  
        printf("!FND: iter ---> ");      
        mpz_out_str(stdout, BASE, iterator);

        fp = fopen("factor-576.txt", "w");  
        mpz_out_str(fp, BASE, iterator);
        fclose(fp);

        fp=fopen("rsa-576-potent.txt", "w");
        mpz_out_str(fp, BASE, iterator);
        fclose(fp);
        printf("\n"); 
 
        system(cmd);
        
      }
    }
    mpz_add_ui(iterator, iterator, addend);
    addend = (addend == 2) ? 4 : 2;
  }

}