How to generate an prime random number??

How to generate an random number which should be a prime number and the primitive roots of a number.

Answer 1

[Samayochita]

Hi Priyanka,

To generate a random prime number, you can use the “isprime” function

(https://www.mathworks.com/help/matlab/ref/isprime.html) along with “randi” function

(https://www.mathworks.com/help/matlab/ref/randi.html) to generate random numbes within a certain range.

For finding primitive roots, you could refer any of the links below:

https://en.wikipedia.org/wiki/Primitive_root_modulo_n

https://www.geeksforgeeks.org/primitive-root-of-a-prime-number-n-modulo-n/

Hope this was useful!

Answer 2

[Walter Roberson]

Possible implementation

format long g

upperbound = flintmax() - 1;
candidate = 0;
iters = 0;
while ~isprime(candidate)
    candidate = randi([2 upperbound]);
    iters = iters + 1;
end
fprintf('iter = %d, value = %d\n', iters, candidate);

iter = 31, value = 7886127185228863

but perhaps more efficient would be

upperbound = flintmax() - 1;
batchsize = 64;
candidates = [];
iters = 0;
while isempty(candidates)
    candidates = randi([2 upperbound], 1, batchsize);
    candidates = candidates(isprime(candidates));
    iters = iters + 1;
end
candidate = candidates(1);
fprintf('iter = %d, value = %d\n', iters, candidate);

iter = 1, value = 4415414201387309

Answer 3

[John D'Errico]

A random prime? Impossible to do. That is, something that many seem to misunderstand is you cannot generate a random number on some domain, without specifying the distribution of those numbers. Just saying they are random is not sufficient.

Worse, that there are infinitely many primes means you cannot even specify a uniform random distribution, since again, that makes no sense on an infinite discrete set that goes from 2 to infinity. The probability of chosing any specific prime will be of measure zero. Can't do it.

Can you generate a random prime on some finite interval? Yes, there are several ways you might do so. But no method will be perfect, since again, the distribution has not been indicated. But, What would I do? Sigh. Grumble. Nothing will be perfect. :-)

My solution would be to: Generate a list of all primes in the interval of interest, then choose uniformly from that set. This wil be quite efficient, as long as the set is not too huge. And since you generate the set of primes in advance, that takes only one call. save it, and it need not be done again.

PrimeList = primes(1e8); % over 5 million primes in that set as I recall
numel(PrimeList)

ans = 5761455

randomPrimeGen = @(HowMany) PrimeList(randi(numel(PrimeList),[1,HowMany]));

randomPrimeGen(1) % Generate 1 random prime from the set, not exceeding 1e8

ans = 99826249

That will be a uniformly generated prime from the set. Don't go too far however. There are around 55 million primes less than 1e9 as I recall. I doubt you really want to go out much beyond that point. How many primes lie below 1e15? (Approximately?) The number of primes that do not exceed N is thought to be approximately N/log(N)

N = 1e15;
N/log(N)

ans = 2.8953e+13

So a little less than 3e13 primes below 1e15. You may not have sufficient RAM to store them all.

And how to generate the primitive roots? I posted a function called leastPrimitiveRoot on the file exchange, as I recall. And there is a function in the symbolic toolbox called isPrimitiveRoot.