# Schnorr-signature calculating a coefficient

I need to create program that makes signature for selected file. I simplified algorithm a little, because I draw max 64 bit prime numbers instead of 512 bit - like its recommended in Applied Cryptography book.

I have already drew private key which is for example: $$1848661337$$, and now I need to calculate public key. I need to choose an $$a \not = 1$$, such that $$a^q = 1 \bmod p$$, where $$q$$ and $$p$$ are prime numbers. I have tried a lot of examples and it seems that the second part of this expression always is going to be $$1$$? If it is true, $$a$$ must be $$1$$?

I thought in the book is mistake but, I found other resources that confirm version from book.

I cant handle it. What should I do to solve this problem?

Numbers from trial:

• $$a^{1034069683} = 1 \bmod 3465190093$$
• $$a^{45900161} = 1 \bmod 95899459$$
• $$a^{200001283} = 1 \bmod 490810459$$
• $$a^{390810929} = 1 \bmod 890811619$$
• @kelalaka Done. As You can see, 1 mod x is always 1. – KonradDos Jan 20 at 21:31
• Hint: for 1) the mod prime, power is prime and gcd(power,mod−1)=1, then $a$ must be? – kelalaka Jan 20 at 22:50
• Hint: what you want is parameters for a Schnorr group. You need to choose $p$ and $q$ together, since $q$ must divide $p-1$. – fgrieu Jan 21 at 9:07
• Ok, so I tried to calculate the group generator. I followed the steps from source: p = qr + 1 917794499 = 917794489*r + 1 p/q - 1/q = r 917794499/917794489 - 1/917794489 = r r = 1.00000000981 h is any number gt then 1, so lets say its 2 in this example g = h^r mod p g = 2^1.00000000981 mod 917794499 g = 2.0000000136 – KonradDos Jan 21 at 22:54
• @kelalaka Next hint please :/ – KonradDos Jan 21 at 23:03