An Algorithm to compute the nearest possible prime number to an input pPrime

• Download Prime_Algorithm.zip - 8.5 KB
• Download Prime_Algorithm_-_Updated.zip - 8.7 KB

Introduction

This code is an application of an algorithm to find out whether a given number pPrime is a

prime number or not , As an addition to that it will continue until it finds the nearest prime number to that given pPrime.

Lets point out a useful thing of this algorithm : suppose that you want to apply an

encryption algorithm which uses the prime numbers as in RSA Encryption algorithm,

there might be other ways to find the prime number better than this way, But "According to

discrete mathematics scientist(My Instructor)" ,This one is Fast ,and so i applied this Fast way to find the prime number ( Which some told me its not Fast as i also Believe)

Background

In Encryption World lets define the following:

P: Plain Text.

C : Cipher (Encrypted) Text.

N : Modulus.

K : "The Key" A given Number(Integer less-than N) < N , Relative(co) Prime to N.

K' : K Prime .

If we want to encrypt the plain text P ,using an encryption Key K , and the key K Range

is from 1 to N , then we'll get an formula as following:

(P*K)mod N = C.

Similarly

(C*K')mod N = P.

The problem is that if N Is not a prime Number ,then we need to find each Relative(co)Prime to N,

which is impractical, because it will reduce the number of encryption keys, which may cause

the algorithm to be broken by using a Brute Force Attack , so what we might need is the following:-

*Choose a huge number N

*Find all relative Primes For N

Now we can see the use of the algorithm , A Theorem Says the following:

IF N IS A Prime Number Then All Numbers(Integers) < N Are relative(co)Prime Of N.

Thats it !! , all we need to find is a huge Prime Number , and the Encryption Keys will be:

# Of Keys = N - 1

This way we can eliminate the BFA ( Brute Force Attack ).

More Reading ,More To find On : http://wikipedia.org/

Its clear now , the algorithm finds that huge prime number to be used in the encryption Alg.

*More to explain in using the code section.

Using the code

The code is easy and a direct implementation to the real algorithm that checks the prime

Numbers and finds the prime numbers.

Lets see:

i choose 26 because it represents the # of English Characters.

Now Give numbers to the Characters A-Z From 1 To 26.

Lets Say, i Want to encrypt The Letter 'C',Using the key 15:

P: 'C'

K: 15

N: 26

C= (P*K) mod 26

The Letter 'C' Is represented with 2 as said above.

Then C= (2*15) mod 26 = 4 , which represents the Letter 'E'

cool

????? Does P=(C*k')mod 26 ?????

C:'E' ,Represents 4.

K':7 why ??? because 4*26 + 1 = 105 <===> (k)15 * (k')7 = 105

Anywayz , Check wikipedia.org

now

( 4*7) mod 26 = 2 , Which represents the letter 'C'

The problem rises when we choose 8 as a key or 13 ,

these tow numbers have a common factor with N (26)

and so their will be irreversible mapping (wiki..) in the encryption

means that if i encrypt some letter using the key 8 i might get the letter g

Which is the same letter we'll get if we use the key 13

Problem.!!!

the solution is by choosing all key values that have no common

factor with N (e.g 26 ) & < N , they will be :{1,2,3,5,7,11,13,17,19,23}

this is what we talked about up their , the number of keys is getting smaller,

& it's really hared to search the the relative primes, it's better IF N Is prime,

and then we can use all N-1 values as A Key so by applying the algorithm,

we find the nearest prime number to 26 is 29 so the key values will be:

{1,2,3,4,5,6,.......26,27,28}=N-1

cool , now we can even represent more than the alphabetic characters, we can add

the comma for example or the * , of course here we can add only tow more symbols {27,28}

what if we want to represent tow letters @ a time ? 'AA' or 'BZ'

we will have 26*26 combinations {'AA' ,'AB','AC' ...'ZW','ZY','ZZ'}

number of keys will be 676 , And by accident 677 is a Prime Number

But what about (26^3 = 26*26*26 = 17576) to encrypt 3 letters @ a time =??

Is it a prime number????

lucky !! orrrr (unlucky) ... we have my code to check it out.

double pPrime,primeRoot;
pPrime=8031810176;//example
start:
primeRoot=System.Math.Floor( System.Math.Sqrt(pPrime));

int counter=0;
bool NotPrime=false;

double [] lessRootPrimeTable=new double[1000000];

for(double possiblePrime=2;possiblePrime<primeRoot;++possiblePrime)
      {
    for(double p=2;p<possiblePrime;p++)
        while((possiblePrime%p)==0)//if
            {
         NotPrime=true;
         break;
                  }
       if(NotPrime==true)
       {
           NotPrime=false;
           continue;}

       if(NotPrime==false)
       {
           lessRootPrimeTable[counter]=possiblePrime;
           while((pPrime)%lessRootPrimeTable[counter]==0)
           {
               //MessageBox.Show("Not Prime");
               pPrime++;
               goto start;
           }
           counter++;
       }
   }


           MessageBox.Show(pPrime.ToString());

Points of Interest

This thing drives you to the world of cryptography , its amazing if i can break the RSA Algorithm,

i hope this is a good start to do that.

History

26 - 11 -2007: I made some updates to fix some syntax and grammar mistakes upon the recommendation of Fernando.

Also I'd like to say that soon i'll post a full program that encrypts and decrypts some plain-text ,using this algorithm or other one more efficient than this one.

27 - 11 -2007: i have Updated the code , it will reduce the worst case , to see the old code its attached up their.