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 177230489166282344015774064377241227587199382967408813262382504707219711331089796381062272830832589652763240077045179410289089586103444172644783259989800867240412448988509325574574304033723512809384370865286355935760236734502077616148946269402098233368030784437031602201910267514742358461638753758087223301499. 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 177230489166282344015774064377241227587199382967408813262382504707219711331089796381062272830832589652763240077045179410289089586103444172644783259989800867240412448988509325574574304033723512809384370865286355935760236734502077616148946269402098233368030784437031602201910267514742358461638753758087223301499. 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.