Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Generators of Modular Prime Systems

  1. Oct 19, 2004 #1


    User Avatar

    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 . . .
  2. jcsd
  3. Oct 19, 2004 #2


    User Avatar
    Science Advisor
    Homework Helper

    What do you mean by generator? Why wouldn't 2 work?
  4. Oct 19, 2004 #3


    User Avatar

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook