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