Generators of Modular Prime Systems

  • Thread starter Chu
  • Start date
  • #1
Chu
10
0
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 . . .
 

Answers and Replies

  • #2
NateTG
Science Advisor
Homework Helper
2,450
6
Chu said:
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?
 
  • #3
Chu
10
0
NateTG said:
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.
 

Related Threads on Generators of Modular Prime Systems

Replies
14
Views
6K
  • Last Post
Replies
12
Views
4K
  • Last Post
Replies
5
Views
4K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
11
Views
4K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
4
Views
2K
Top