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: 106,439

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

Offline

**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: 106,439

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

Offline

**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: 106,439

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

Offline

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

Darn.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 106,439

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

Offline

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

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

Offline

Pages: **1**