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
- Administrator
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.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#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
- Administrator
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.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#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
- Administrator
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.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#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
- Administrator
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.
Probability is the most important concept in modern science, especially as nobody has the slightest notion what it means.
90% of mathematicians do not understand 90% of currently published mathematics.
#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).