5
$\begingroup$

Consider p such that PrimeQ[p] == True. How do I compute n such that Prime[n] == p?

In other words, what is the inverse function of "Prime"?

EDIT:

As a concrete example, consider p to be the first prime that factorizes rsa-768, 

p = rsa768a = 33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489

PrimeQ[rsa768a] is True; I want to know its n.

Trying Jason's suggestion, InverseFunction[Prime][rsa768a], does not return the expected result (for a small prime it does). Trying LLlAMnYP suggestion, PrimePi[rsa768a] returns

PrimePi::largp: Argument ... in PrimePi[...] is too large for this implementation. >>

| improve this question | |
$\endgroup$
  • 1
    $\begingroup$ InverseFunction[Prime] $\endgroup$ – Jason B. Mar 9 '16 at 9:21
  • 4
    $\begingroup$ @JasonB Cheeky :-P and cruel. PrimePi is much faster. $\endgroup$ – LLlAMnYP Mar 9 '16 at 9:24
  • 1
    $\begingroup$ It's so direct, it's almost mocking the OP, but I like, how it shows off Mathematica's capability to do the thinking for you. But on a more serious note, I can't imagine when it would be preferable to PrimePi. $\endgroup$ – LLlAMnYP Mar 9 '16 at 9:28
  • 4
    $\begingroup$ You can attempt to use NextPrime[#, -1]& but good luck waiting for that computation to end in this universe. There's a reason, that these things are used for encryption, y'know :-) $\endgroup$ – LLlAMnYP Mar 9 '16 at 9:36
  • 2
    $\begingroup$ @J.C.Leitão This question What is so special about Prime? explicitly states this problem. Prime has an extensible domain, however you can't extend it up to rsa768a unless you have an enormous amount of RAM, but it is unlikely realizable. $\endgroup$ – Artes Mar 9 '16 at 9:52

Browse other questions tagged or ask your own question.