/******** Scott A. Zurawski ******** PROJECT 5 ********
 ** 
 **/

/** The purpose of this program is to list possible prime numbers in a
 ** range definded by the user. **
 **/

#include <stdio.h>
#include <stdlib.h>
#include "prime_head.h"  /** My own Header File. **/


/** Function Protypes **/

long epx(unsigned long long r,unsigned long long p,unsigned long long n);
unsigned long Find_gcd(unsigned long Ran_Num,unsigned long Prime_Num);
int J_Test_For_Primality(unsigned long Ran_Num,unsigned long Prime_Num);
int Solovay_Strassen_Test(unsigned long Prime_Num);
int Test_First_Few_Primes(unsigned long Prime_Num);
NODE *Linked_List_Primes(NODE *Pointer_List, unsigned long Prime_Num);
void Print_Linked_List(NODE *Pointer_List,int Min_Num,int Max_Num);

int main(void){ /** Begin Main **/

unsigned long Prime_Num;
int Max_Num,Min_Num,count=0,finish=FALSE;
NODE *Pointer_List=NULL;				

printf("\nEnter the number range you would to search over: ");
scanf("%d %d",&Min_Num,&Max_Num);
if(Min_Num%2 == 0)
   Prime_Num=Min_Num+1;
else
   Prime_Num=Min_Num;				
while(Prime_Num<Max_Num){
   if(Test_First_Few_Primes(Prime_Num)!=TRUE){
      while((count<STEPS)&&(finish==FALSE)){
         finish=Solovay_Strassen_Test(Prime_Num);
	 if((count==(STEPS-1))&&(finish==FALSE))
	    Pointer_List=Linked_List_Primes(Pointer_List,Prime_Num);
	 count++;
      }
    }
    Prime_Num+=2;
    finish=FALSE;
    count=0;
}
Print_Linked_List(Pointer_List,Min_Num,Max_Num);
} /** End Main **/

/** This function is used to compute the exponents of very large number, by
    doing the multiplcation and then performing a mod on that number. This is 
    done a number of times until the Legendre Symbol is obtained.           **/ 
 
long epx(unsigned long long r,unsigned long long p,unsigned long long n){
 
long long z=1L;				

while(p>0){
   if (p%2==1)			
       z=(z*r)%n;
   r=(r*r)%n;
   p/=2 ;
}
if(z==(n-1))			
   z=-1;					
return z;
} /** End of epx **/


/** This function is used to test two number and find there Greatest Common
    Factor. This function is used in Solovay_Strassen_Test function and the
    J_Test_For_Primality function.                                        **/

unsigned long Find_gcd(unsigned long Ran_Num,unsigned long Prime_Num){
	
unsigned long gcd;
				
gcd=Prime_Num;
while(Ran_Num>0){
   gcd=Ran_Num;
   Ran_Num=Prime_Num%Ran_Num;
   Prime_Num=gcd;
}
return gcd;
} /** End of Find_gcd **/

/** This function is used to find the Jacobi symbol and preform the tests
    for primality which is covered in the book.                          **/
int J_Test_For_Primality(unsigned long Ran_Num,unsigned long Prime_Num){
	
if(Ran_Num>=Prime_Num)
   Ran_Num%=Prime_Num;
if(Ran_Num==0)
   return 0;
if(Ran_Num==1)
   return 1;
if(Ran_Num==2){
   if(((Prime_Num*Prime_Num-1)/8)%2==0)
      return 1;
   else
      return -1;
   }
if(Ran_Num&Prime_Num&1){
   if(((Ran_Num-1)*(Prime_Num-1)/4)%2==0)
      return +J_Test_For_Primality(Prime_Num,Ran_Num);
   else
      return -J_Test_For_Primality(Prime_Num,Ran_Num);
   }
if(Find_gcd(Ran_Num,Prime_Num)==1){
   if(((Ran_Num-1)*(Prime_Num-1)/4)%2==0)
      return +J_Test_For_Primality(Prime_Num,Ran_Num);
   else
      return -J_Test_For_Primality(Prime_Num,Ran_Num);
   }
} /** End of J_Test_For_Primality **/

/** This function is used to compute the Solovay Strassen test for
    Primality.                                                  **/

int Solovay_Strassen_Test( unsigned long Prime_Num ){
	
unsigned long Ran_Num;    		
int finish=FALSE,val1,val2;

if( finish != TRUE ){
   Ran_Num=rand();
   Ran_Num%=Prime_Num;
      if(Find_gcd(Ran_Num,Prime_Num)!=1)
         finish=TRUE;       
      else{
         val1=epx(Ran_Num,((Prime_Num-1)/2),Prime_Num); 
	 val2=J_Test_For_Primality(Ran_Num,Prime_Num);
            if(abs(val1)!=abs(val2))
	       finish=TRUE;         
	    else
	       finish=FALSE;        
      }
}
return finish;
} /** End of Solovay_Strassen_Test **/


/** This function is used to test to if the first few prime number 
     divide into Prime_Num evenly.                               **/

int Test_First_Few_Primes( unsigned long Prime_Num ){
	
int First_Primes[] = {3, 5, 7, 11, 13, 17, 19, 21, 23, 29},finish = FALSE,i = 0;
while((!finish)&&(i<=TEN)){
   if((Prime_Num%First_Primes[i])!=0)
      i+=1;
   else
      finish=TRUE;
}
return finish;
} /** End of Test_First_Few_Primes **/


/** A Linked List Used to hold the prime numbers for printing later. **/

NODE *Linked_List_Primes( NODE *Pointer_List, unsigned long Prime_Num ){
	
NODE* Pointer_Node;					

NODE* Pointer_Temp=Pointer_List;		    
Pointer_Node=(NODE *)malloc(sizeof(NODE));
Pointer_Node->Prime=Prime_Num;
Pointer_Node->Pointer_Next=NULL;
if(Pointer_List==NULL)
   Pointer_List=Pointer_Node;
else{
   Pointer_Temp=Pointer_List;
   while(Pointer_Temp->Pointer_Next!=NULL)
      Pointer_Temp=Pointer_Temp->Pointer_Next;
   Pointer_Temp->Pointer_Next=Pointer_Node;
}
return Pointer_List;
} /** End of Linked_List_Primes **/


/** This is the function used to print the prime numbers that are 
    stored in the Linked List.                                   **/

void Print_Linked_List( NODE *Pointer_List,int Min_Num,int Max_Num){
	
NODE *Pointer_Current;					
int count=1; 					

Pointer_Current=Pointer_List;
printf("\nThese are the PRIME numbers between %d and %d !!!\n",Min_Num,Max_Num);
printf("*********************************************************\n\n");
while(Pointer_Current!=NULL){
   if(((count-1)%2)==0)
      printf("\n");
   printf("  %d \t--> %u\t\t",count,Pointer_Current->Prime);
   Pointer_Current=Pointer_Current->Pointer_Next;
   count++;
}
printf("\n");
}/** End of Print_Linked_List **/