9
$\begingroup$

How are generators of a (large prime) set calculated in popular programs such as pgp and libraries such as java's bouncycastle? i cannot imagine them just churning away at every value between 2 and p until something comes up, but there does not seem to be any description of some other method programmers use to find them.

even if they test every number between 2 and p, what is the test? is it checking if the set generated is {1,2,...p-1}? that seems like it would take too much memory.

can anyone give me some pseudocode on how to do it? im trying something thats probably incredibly naive and the program is using 1.5gb ram after a few seconds, with only a 32 bit value

  • 2
    The search term you want is **primitive root** (http://en.wikipedia.org/wiki/Primitive_root_modulo_n) (I have edited the title to reflect this so it is more informative; I hope you don't mind). Churning away at every value between $2$ and $p$ is not actually such a bad idea; conditional on the generalized Riemann hypothesis you're guaranteed to find a primitive root between $2$ and $O(\log^6 p)$ (although I have no idea how big the constant is).2012-06-09
  • 0
    I suspect the OP's disinclination to check many values is related to the inefficiency of checking each one by the current implementation.2012-06-09
  • 0
    yeah. more or less, and there's really no good non-super-technical explanation on how to find them (havent checked the links in the answers provided yet)2012-06-10
  • 0
    Enumerating and testing is not a good idea... For cryptographic purposes, $p$ will usually be above $2^{2048}$.2012-11-09

4 Answers 4