3 ms·
Is there a way to find groups with easy generators/primitive roots? I imagine you'd want a small root of unity, but also be able to choose a bigger modulus for
by programjames 2y ago
Is there a way to find groups with easy generators/primitive roots? I imagine you'd want a small root of unity, but also be able to choose a bigger modulus for extra big multiplications. Also, afaik it's discrete-logarithm level of difficulty to even find a generator if you choose a random modulus, though I don't know if it's easier to find a modulus after you choose the generator.
- adgjlsfhk1 2y agosince the groups you're looking at are is size log(n), you can do a lot of work without issue. as long as you do experimental it less work, it doesn't affect the runtime.
- archgoon 2y ago> though I don't know if it's easier to find a modulus after you choose the generator. Sure, pick a large prime. Double it and add 1 (and call it n). If it's still prime, then you know the prime factorization of n-1. Pick your generator, and check if it raised to the p is 1, or if squaring it is one. If not, it's a generator of the multiplicative group mod n.