How to get a prime of a given length in Sage?

primes sage
Chin picture Chin · Dec 7, 2015 · Viewed 7k times · Source

How can I get a random prime of a given bit length in Sage?

For example, to get a 512-bit prime, I tried

p = random_prime(2^512)

but according to the documentation:

The command random_prime(a, True) will return a random prime between 2 and a

so I can't use it, since I need a prime of an exact length.

Answer

kcrisman picture kcrisman · Dec 7, 2015 
sage: random_prime?
Signature:      random_prime(n, proof=None, lbound=2)
Docstring:
   Returns a random prime p between lbound and n (i.e. lbound <= p <=
   n). The returned prime is chosen uniformly at random from the set
   of prime numbers less than or equal to n.

   INPUT:

   * "n" - an integer >= 2.

   * "proof" - bool or None (default: None) If False, the function
     uses a pseudo-primality test, which is much faster for really big
     numbers but does not provide a proof of primality. If None, uses
     the global default (see "sage.structure.proof.proof")

   * "lbound" - an integer >= 2 lower bound for the chosen primes

So is this sufficient?

sage: random_prime(2^512-1,False,2^511)
7484165189517896027318192121767201416039872004910529422703501933303497309177247161202453673508851750059292999942026203470027056226694857512284815420448467
sage: is_prime(7484165189517896027318192121767201416039872004910529422703501933303497309177247161202453673508851750059292999942026203470027056226694857512284815420448467)
True

Related questions

Printing prime numbers from 1 through 100

This c++ code prints out the following prime numbers: 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97. But I don't think that's the way my book wants it to be written. It mentions something about square root of a number. So I did try changing my 2nd loop …

Read More
Which is the fastest algorithm to find prime numbers?

Which is the fastest algorithm to find out prime numbers using C++? I have used sieve's algorithm but I still want it to be faster!

Read More
How to create the most compact mapping n → isprime(n) up to a limit N?

Naturally, for bool isprime(number) there would be a data structure I could query. I define the best algorithm, to be the algorithm that produces a data structure with lowest memory consumption for the range (1, N], where N is a …

Read More