Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

## #1 2011-01-04 07:22:42

calccrypto
Full Member

Offline

### 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).

## #2 2011-01-04 07:27:20

bobbym

Offline

### 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.
90% of mathematicians do not understand 90% of currently published mathematics.
I am willing to wager that over 75% of the new words that appeared were nothing more than spelling errors that caught on.

## #3 2011-01-04 07:35:03

calccrypto
Full Member

Offline

### 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-04 07:35:56)

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

## #4 2011-01-04 09:21:07

calccrypto
Full Member

Offline

### 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).

## #5 2011-01-04 09:28:04

bobbym

Offline

### 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.
90% of mathematicians do not understand 90% of currently published mathematics.
I am willing to wager that over 75% of the new words that appeared were nothing more than spelling errors that caught on.

## #6 2011-01-04 09:35:12

calccrypto
Full Member

Offline

### 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).

## #7 2011-01-04 09:42:49

bobbym

Offline

### 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.
90% of mathematicians do not understand 90% of currently published mathematics.
I am willing to wager that over 75% of the new words that appeared were nothing more than spelling errors that caught on.

## #8 2011-01-04 09:54:21

calccrypto
Full Member

Offline

### 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).

## #9 2011-01-04 10:47:54

bobbym

Offline

### 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.
90% of mathematicians do not understand 90% of currently published mathematics.
I am willing to wager that over 75% of the new words that appeared were nothing more than spelling errors that caught on.

## #10 2011-01-04 11:35:34

calccrypto
Full Member

Offline

### 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).