Generators of Modular Prime Systems

In summary, the speaker is looking for a way to efficiently find a generator in very large modular prime systems, with p potentially being up to 2^1024. They are also wondering how long it would take to find a generator on a modern system. They mention that 2 does not work as a generator and explain that if g is a generator for a system modulo P, then all p in P can be represented as g^n. They use the example of Z_7 and show that the powers of 2 do not form a cyclic group of order 3, so 2 is not a generator.
  • #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 . . .
 
Physics news on Phys.org
  • #2
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
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 to Generators of Modular Prime Systems

1. What is a generator of modular prime systems?

A generator of modular prime systems is a mathematical concept used in number theory and cryptography. It is a number that, when raised to different powers, generates a set of distinct prime numbers. This set of prime numbers is called a modular prime system.

2. How are generators of modular prime systems used in cryptography?

Generators of modular prime systems are used in cryptography to generate large prime numbers that are used as the basis for encryption algorithms. These prime numbers are crucial for ensuring the security of data transmission and storage.

3. Can any number be a generator of modular prime systems?

No, not every number can be a generator of modular prime systems. The number must meet certain criteria, such as being a primitive root modulo all the prime factors of a given modulus. This is known as the primitive root theorem.

4. Are there any practical applications for generators of modular prime systems?

Aside from their use in cryptography, generators of modular prime systems have practical applications in areas such as random number generation, coding theory, and error-correcting codes. They also have potential applications in fields such as physics and biology.

5. What is the connection between generators of modular prime systems and the Riemann hypothesis?

The Riemann hypothesis, one of the most famous unsolved problems in mathematics, states that all non-trivial zeros of the Riemann zeta function lie on the critical line of 1/2. The existence of a generator of modular prime systems is closely related to the Riemann hypothesis, and a proof of the hypothesis would have implications for the distribution of prime numbers and the existence of generators of modular prime systems.

Similar threads

What is the fastest algorithm for finding large prime numbers?
    • Programming and Computer Science
Replies
14
Views
2K
ABC reference frame synchronous generator modelling in Ltspice
    • Electrical Engineering
Replies
1
Views
993
I Prime and Maximal Ideals in PIDs ... Rotman, AMA Theorem 5.12
    • Linear and Abstract Algebra
Replies
4
Views
1K
I "Map" point between coordinate systems
    • Linear and Abstract Algebra
Replies
5
Views
2K
MHB Prime and Maximal Ideals in PIDs .... Rotman, AMA Theorem 5.12
    • Linear and Abstract Algebra
Replies
3
Views
1K
A How can modular forms be used in particle physics mass models?
    • Beyond the Standard Models
Replies
7
Views
4K
A Solution?: Quintic Equation from Physical System
    • Linear and Abstract Algebra
Replies
4
Views
1K
MHB Prime Polynomials and Irreducible Polynomials
    • Linear and Abstract Algebra
Replies
1
Views
3K
Is There Still a Market for Mechanical High Power DC/AC Generators?
    • Electrical Engineering
Replies
7
Views
1K
I Generate a trackmap with speed and g forces
    • Mechanics
Replies
9
Views
817

Hot Threads

Recent Insights

Back
Top