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

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**calccrypto****Member**- Registered: 2010-03-06
- Posts: 96

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

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,262

Hi calccrypto;

What do you mean by a generator?

**In mathematics, you don't understand things. You just get used to them.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

**Online**

**calccrypto****Member**- Registered: 2010-03-06
- Posts: 96

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

Offline

**calccrypto****Member**- Registered: 2010-03-06
- Posts: 96

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

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,262

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.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

**Online**

**calccrypto****Member**- Registered: 2010-03-06
- Posts: 96

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

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,262

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.Of course that result can be rigorously obtained, but who cares?Combinatorics is Algebra and Algebra is Combinatorics.**

**Online**

**calccrypto****Member**- Registered: 2010-03-06
- Posts: 96

Darn.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 86,262

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.

Of course that result can be rigorously obtained, but who cares?

Combinatorics is Algebra and Algebra is Combinatorics.

**Online**

**calccrypto****Member**- Registered: 2010-03-06
- Posts: 96

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

Offline

Pages: **1**