Generators of Modular Prime Systems

[Chu]

Hello all, I am currently writing a program where I need to find a generator in VERY large modular prime systems, where p can be anywhere up to 2^1024. Is there an efficent (i.e. hopefully polynomial time on the number of bits) way to do this? For example, the current system I am working in is modulo 17723048916628234401577406437724122758719938296740 88132623825047072197113310897963810622728308325896 52763240077045179410289089586103444172644783259989 80086724041244898850932557457430403372351280938437 08652863559357602367345020776161489462694020982333 68030784437031602201910267514742358461638753758087 223301499. I am wondering how long it would take to find a generator on a modern system . . .

[NateTG]

Hello all, I am currently writing a program where I need to find a generator in VERY large modular prime systems, where p can be anywhere up to 2^1024. Is there an efficent (i.e. hopefully polynomial time on the number of bits) way to do this? For example, the current system I am working in is modulo 17723048916628234401577406437724122758719938296740 88132623825047072197113310897963810622728308325896 52763240077045179410289089586103444172644783259989 80086724041244898850932557457430403372351280938437 08652863559357602367345020776161489462694020982333 68030784437031602201910267514742358461638753758087 223301499. I am wondering how long it would take to find a generator on a modern system . . .

What do you mean by generator? Why wouldn't 2 work?

[Chu]

What do you mean by generator? Why wouldn't 2 work?

After doing some looking I sort of found the way to do this (i.e. reduce it to a much simpler problem). If g is a gerator for a system modulo P, then all p in P can be represented as g^n.

For example, in Z_7, the powers of 2 are:

2, 4, 8=1, 2

i.e. we have a cyclic group of order 3 so 2 is not a generator.