Sage and Picking a Generator ValueIn a discrete log method, we use a generator (\(g\)), a prime number (\(p\) and a value \(x\), and determine \(Y=g^x \pmod p\). The generator value must be a primitive root of \(p\). . TheoryFor \(Y=g^x \pmod p\), we can't just use any base generator value of \(g\), as we need to make sure that all of the values of \(x\) between 0 and \(p-1\) to produce values of \(Y\) between 0 and \(p-1\). To enables this the generator value must be a primitive root of \(p\). For this, we start with our prime (\(p\)), and then the order of the group will be \(p-1\). We can then factorize \(p-1\) into prime factors. For example, if \(p=97\), we have \(p-1=96\), and which can be factorized with \(2\times 2 \times 2 \times 2 \times 2 \times 3\). The prime factors of this are thus 2 and 3. We then check that \(g^x \pmod p\) for all these prime factors and make sure the result is not 1. So for 96, the factors we check are: \(2, 3, 6 (2\times3), 12 (2\times2\times3), 24 (2\times2\times2\times3), 48 (2\times2\times2\times2\times3)\) If we select \(g=3\), we get: \(3^2 \pmod {97}= 9\) \(3^3 \pmod {97}= 27\) \(3^6 \pmod {97}= 50\) \(3^{12} \pmod {97}= 75\) \(3^{24} \pmod {97}= 96\) \(3^{48} \pmod {97}= 1\) (not safe!!!) Let’s see if 5 is safe: \(5^2 \pmod {97}= 25\) \(5^3 \pmod {97}= 28\) \(5^6 \pmod {97}= 8\) \(5^{12} \pmod {97}= 64\) \(5^{24} \pmod {97}= 22\) \(5^{48} \pmod {97}= 96\) and so \(g=5\) is thus safe. An efficient way to compute this is: def getG(p): eTotient=p-1 g=3 e = eTotient/2 while (pow(g,e,p) !=eTotient): g=g+2 return(g) p = random_prime(2^256) g=getG(p) print (f"p={p}") print (f"g={g}") A sample run: p=36373411232409780758268258132016292089065592698256299081440039730756727636927 g=3 and: p=16515715843772453089333345240973802596788090716339751985426411759713577391719 g=13 and: p=21985449086439722706915209761047719363681953632324771173999878992712028497229 g=3 |