Click here to Skip to main content
13,559,672 members
Click here to Skip to main content
Add your own
alternative version


8 bookmarked
Posted 27 Nov 2007

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

, 27 Nov 2007
Rate this:
Please Sign up or sign in to vote.
This algorithm is needed to find the nearest prime number to some input pPrime ,is useful for encryption algorithms

Screenshot - newPrime.jpgIntroduction

This is an updated article of my old stupid one, i posted in hurry which was the first time i post an article on this great site , i'm sorry to delete that old one , but i'm glad to post this one because of the confusion the old article caused.

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)


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.


(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 :

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'


????? 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


( 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


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:


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,p;
//Theorem:if the given pPrime devides any number less or equal the root(pPrime)
//then the given number is not a prime,otherwise it is a prime.

    primeRoot=System.Math.Floor( System.Math.Sqrt(pPrime));

            //not prime;
            goto start;
//Worst Case = O(n)


Points of Interest

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


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.

28-11-2007 : Dramatic changes , i was totaly wrong . now it's much easier and simpler.

if you want the old stupid code ;) tell me about it.


This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


About the Author

Web Developer
Jordan Jordan
No Biography provided

You may also be interested in...


Comments and Discussions

Answercompute nearest Pin
sofiastrange6-Aug-09 22:56
membersofiastrange6-Aug-09 22:56 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web01 | 2.8.180527.1 | Last Updated 27 Nov 2007
Article Copyright 2007 by Pali.Sniper
Everything else Copyright © CodeProject, 1999-2018
Layout: fixed | fluid