Math Is Fun Forum

calccrypto

Member

Registered: 2010-03-06

Posts: 96

Whats a fast way to find generator g in Zp?

Is there some way to find a generator for a large prime number without checking each number individually?

---

Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Whats a fast way to find generator g in Zp?

Hi calccrypto;

What do you mean by a generator?

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

calccrypto

Member

Registered: 2010-03-06

Posts: 96

Re: Whats a fast way to find generator g in Zp?

Hi bobbym. Its been a long time

totient(x) = {1,2, 3,...,etc.}, for some number (ignore prime p for now)
im looking for integer g (that is in totient(x) ) such that:
the set of {for 1 <= i < x: g ^ i mod x (removing all duplicates)} will equal the totient of x

since x = p = prime, totient(p) = {1,2, ... p-1}
since p is big, testing all those values will take forever

Last edited by calccrypto (2011-01-03 08:35:56)

---

Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

calccrypto

Member

Registered: 2010-03-06

Posts: 96

Re: Whats a fast way to find generator g in Zp?

Any ideas on how to get g for a big p?

---

Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Whats a fast way to find generator g in Zp?

I am still asking questions. For totient(7) you would get {1,2,3,4,5,6}. What do you get for totient(10)?

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

calccrypto

Member

Registered: 2010-03-06

Posts: 96

Re: Whats a fast way to find generator g in Zp?

10 would be {1, 3, 7, 9}. However, since 10 is not prime, theres no need for it

---

Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Whats a fast way to find generator g in Zp?

I know what you want now, the generator. Offhand I do not know of anything faster than trying them all. The expected time is ( p - 1 ) / 2. Let me do a search around.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

calccrypto

Member

Registered: 2010-03-06

Posts: 96

Re: Whats a fast way to find generator g in Zp?

Darn.

---

Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Whats a fast way to find generator g in Zp?

Hi calccrypto;

I am sorry.

The only thing I found out is that T(7) and T(11) both have more than one generator. I could find nothing faster than trying them all. Maybe someone else can do more.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

calccrypto

Member

Registered: 2010-03-06

Posts: 96

Re: Whats a fast way to find generator g in Zp?

Darn. Oh well. I will keep on searching. Thanks for looking!

---

Visit calccrypto.wikidot.com for detailed descriptions of algorithms and other crypto related stuff (not much yet, so help would be appreciated).