How about big numbers? ( primality tests ) [closed]

Question

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.

Closed 9 years ago.

Is this a 'real' task, that can be written on any language ( C/C++, for example )

So, my task is 'generate' random number with length over 50 digits ( maximum = 200 )?

Then, i must check this number on primality test.

So, is this task 'real' and how many time/resources it will consume?

alternative way is to generate prime Mersenn numbers or other numbers from special class ( which class could be used? )

Answer 1

There are efficient probabilistic algorithms for primality testing like Miller-Rabin that are usually used for such purposes.

Picking a random number and testing for primality using a randomized algorithm is efficient since the density of primes guarantees you that for n-bit numbers you need to pick around n numbers to test.

Answer 2

Use the Miller-Rabin primality test. Also, you'll need a library for big decimals, as numbers of 50 digits do not fit in a native datatype.

Here is a Javascript implementation of Miller-Rabin, which does 50 iterations of Miller-Rabin. It completes in a couple of seconds.