Generators of Modular Prime Systems

Click For Summary
SUMMARY

This discussion focuses on finding generators in large modular prime systems, specifically for primes up to 2^1024. The user seeks an efficient method, ideally polynomial time concerning the number of bits, to identify a generator for a given modulus, exemplified by a specific large prime number. The conversation highlights the mathematical principle that if g is a generator for a system modulo P, then all elements in P can be expressed as g^n, illustrating this with the cyclic group example of Z_7.

PREREQUISITES
  • Understanding of modular arithmetic and prime numbers.
  • Familiarity with the concept of generators in group theory.
  • Knowledge of polynomial time complexity in algorithms.
  • Experience with programming for mathematical computations.
NEXT STEPS
  • Research algorithms for finding generators in modular arithmetic, such as the Pohlig-Hellman algorithm.
  • Learn about the properties of cyclic groups and their applications in cryptography.
  • Explore efficient methods for modular exponentiation in large prime systems.
  • Investigate the use of libraries like GMP (GNU Multiple Precision Arithmetic Library) for handling large integers in programming.
USEFUL FOR

Mathematicians, cryptographers, and software developers working on algorithms related to modular arithmetic and prime number theory.

Chu
Messages
9
Reaction score
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 . . .
 
Physics news on Phys.org
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?
 
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.
 

Similar threads

Gravity Based Electricity Generator
  • · Replies 74 ·
3
Replies
74
Views
11K
MHB Prime and Maximal Ideals in PIDs .... Rotman, AMA Theorem 5.12
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Prime and Maximal Ideals in PIDs ... Rotman, AMA Theorem 5.12
  • · Replies 4 ·
Replies
4
Views
2K
MHB Prime Polynomials and Irreducible Polynomials
  • · Replies 1 ·
Replies
1
Views
4K
Graduate Forcing conditions in a solution of an under-determined system
  • · Replies 2 ·
Replies
2
Views
2K
Graduate Our Old Friend, the Twin Primes Conjecture
  • · Replies 11 ·
Replies
11
Views
2K
Graduate Solution?: Quintic Equation from Physical System
  • · Replies 4 ·
Replies
4
Views
2K
Graduate How can modular forms be used in particle physics mass models?
  • · Replies 7 ·
Replies
7
Views
6K
MHB Splitting Fields - Dummit and Foote - Example - page 541 - x^p - 2, p prime
  • · Replies 4 ·
Replies
4
Views
3K
ABC reference frame synchronous generator modelling in Ltspice
  • · Replies 1 ·
Replies
1
Views
3K