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$
14
  • 1
    $\begingroup$ InverseFunction[Prime] $\endgroup$
    – Jason B.
    Mar 9, 2016 at 9:21
  • 4
    $\begingroup$ @JasonB Cheeky :-P and cruel. PrimePi is much faster. $\endgroup$
    – LLlAMnYP
    Mar 9, 2016 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, 2016 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, 2016 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, 2016 at 9:52

0

Reset to default

Browse other questions tagged or ask your own question.