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

Online

### 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.
Some cause happiness wherever they go; others, whenever they go.
If you can not overcome with talent...overcome with effort.

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

Online

### 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.
Some cause happiness wherever they go; others, whenever they go.
If you can not overcome with talent...overcome with effort.

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

Online

### 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.
Some cause happiness wherever they go; others, whenever they go.
If you can not overcome with talent...overcome with effort.

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

Online

### 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.
Some cause happiness wherever they go; others, whenever they go.
If you can not overcome with talent...overcome with effort.

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