We're a community of 1076K IT Pros here for help, advice, solutions, professional growth and fun. Join us!
1,075,993 Members — Technology Publication meets Social Media

# Prime Number generation

I'm coding a encryption program where I need to generate random prime.
I wrote this code

``````for(i=3; i<10000000; i=i+2 )
{
for(j=2; j <= sqrt(i); j++ )
{
if(!(i%j)) break;
}

if (j>sqrt(i))
{
cout<<i << " ";
}
}
``````

This tests a number till is square root. Its good for small prime numbers. But encryption needs prime of range 100 digit. But a 20 digit prime would be fine. How to do this ? I googled and found AKS algorithm, but I'm finding it difficult to code. So can anyone suggest some other algorithm ? And how to get a 20 digit prime.

7
Contributors
9
Replies
21 Hours
Discussion Span
9 Months Ago
Last Updated
10
Views
Question
np complete
Posting Whiz
385 posts since Sep 2010
Reputation Points: 18
Skill Endorsements: 0

From what I glance at your code, are you sure that an int can handle 20 digit numbers? That may be the first problem you need to solve -- data type -- before you attempt to find a number...

Taywin
Posting Maven
2,633 posts since Apr 2010
Reputation Points: 275
Skill Endorsements: 17

I can use array, or linked list for storing 20 digit number.

np complete
Posting Whiz
385 posts since Sep 2010
Reputation Points: 18
Skill Endorsements: 0

Those work, but they tend to be slow.
Have you looked into Multi Precision Number libraries?
There's GMP and MPFR to name a few.
FYI: `uint64_t` will get you into the very shallow end of 20-digit numbers (i.e. 0-18446744073709551615)

DeanMSands3
Posting Whiz
310 posts since Jan 2012
Reputation Points: 80
Skill Endorsements: 1

FYI: uint64_t will get you into the very shallow end of 20-digit numbers (i.e. 0-18446744073709551615)

Do you mean `long long x` decleration ?

np complete
Posting Whiz
385 posts since Sep 2010
Reputation Points: 18
Skill Endorsements: 0

If you want an unsigned 64 bit integer you can use `unsigned long long foo;`. Check this out to see the data types and their ranges. http://msdn.microsoft.com/en-us/library/s3f49ktz%28v=vs.80%29.aspx

NathanOliver
Posting Virtuoso
1,515 posts since Apr 2009
Reputation Points: 281
Skill Endorsements: 3

There are a lot of those primes out there, but generating them will undoubtedly be slow... especially if you want the really big ones. I would suggest A) looking into an arbitrary arithmetic library (so that you can handle epicly large numbers) then B) google for lists of large numbers, there are tons of them. You could then store them in an array and randomly pick one from it. Another option is to store an array of ints representing valid exponents for Mersenne Primes, then just generate the corresponding prime.

Labdabeta
Practically a Master Poster
613 posts since Feb 2011
Reputation Points: 27
Skill Endorsements: 1

Storing list of large prime is not my option. I want to generate prime. And Labdabeta, what do you mean by arbitrary arithmetic library ?

np complete
Posting Whiz
385 posts since Sep 2010
Reputation Points: 18
Skill Endorsements: 0

And Labdabeta, what do you mean by arbitrary arithmetic library ?

Bad choice of words. He means a large-number arithmetic library? Arbitrary is not correct. You want to pick a package with care.

WaltP
Posting Sage w/ dash of thyme
Team Colleague
11,404 posts since May 2006
Reputation Points: 3,421
Skill Endorsements: 37

Most used term is maybe multi-precission numbers. Be sure not to forget first to test candidates with pseudoprime test like http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html

pyTony
pyMod
Moderator
6,301 posts since Apr 2010
Reputation Points: 879