I am doing a paper on textbook RSA (this is for high school btw) and in my example I need two very large primes, but I want my $e = 3$.

Is there a short way to calculate the values of $p$ and $q$ such that $gcd(e, φ(pq)) = 1$?

  • 5
    $\begingroup$ Sample primes at random until you find two (p, q) such that 3 divides neither (p-1) nor (q-1). $\endgroup$ – puzzlepalace Oct 14 '15 at 22:37
  • 2
    $\begingroup$ Do you need to know how to find large primes, or just how to find large primes with that property? $\endgroup$ – Seth Oct 15 '15 at 2:02
  • $\begingroup$ puzzlepalace's hint can be rewritten as "test only numbers that are 2 mod 3 for primeness". $\endgroup$ – j.p. Oct 15 '15 at 8:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.