Re: group theory question

On 10/10/2024 17:17, Phil Carmody wrote:

Mike Terry <news.dead.person.stones@darjeeling.plus.com> writes:
 

On 09/10/2024 17:21, Phil Carmody wrote:

Mod(3,17) is a generator, but its 2^n-th powers hit Mod(1,17) really
quickly.

>
Also p=13.  Well, the powers don't hit 1, but quickly cycle with a
period of 2.  Cycling "too soon" is the general way different primes
fail, rather than specifically hitting 1.

 Yeah, I chose 17 because it is a Fermat prime (of the form 2^n+1),
and I knew 2^n modulo EulerPhi(17)=16 would go 1, 2, 4, 8, 0, ..

A perhaps more important consideration is whether it is a "safe" prime of the form p=2q+1, p and q both prime.
However, I was originally thinking about exponentiation by squaring. If the cycling starts too soon then we might do exp-by-squaring faster, but that's impossible if we use a generator - two different exponents would give the same result.
To clarify, suppose we used p=17 and g=3 and the sequence ran 464646... (it doesn't). To find g^7 we could calculate 4x6x4 = 4^2x6 = 6x6 = 4 just by knowing 4^2=6 and 6^2=4. But g^1 would also equal 4, which means g is not a generator, a contradiction.
So, what are we left with? That the intro to the sequence, before it starts repeating, must be at least as long as the number of bits in the prime.
Peter Fairbrother