Hello all,
I read Jomandi's useful tips, and I have a few questions.
I am new at this, so bear with me, I am probably missing something really simple.
1) how do we know m < p ?
Is there a guarantee that there are always a few m's < p, such that m^e = m mod p ?
2) in the quote, "for each number m with 0[HTML_REMOVED]
3) if the generator g is also 0 < g < p, then together with x, doesn't it mean that it is going to take (p-1)^2 power modulo operations to find all the (g, x) pairs ?
4) given m < p, wouldn't it be faster to calculate m^e mod p directly, since it requires "only" (p-1) power modulo operations ?
5) "analog for q": I take it to mean 'use the CRT and qinv', and not 'do all the same operations than for p', given that q > p.
Unless all the steps for p can be done 'easily'.
I have read a few papers that all mention how to calculate the fixed points; however, they don't describe how to get all the other m's in a non-"brute force" way.
I would be grateful if someone could point to where my logic fails.
I like these mathematical puzzles, and I learn a lot in the process!
Thanks,
Eric
Hi Eric,
this is a really nice challenge, well worth the work! I'll try to answer your questions as far as I can (no number theory crack …)
Generally, you need to understand finite fields of prime order (see e.g. https://en.wikipedia.org/wiki/Finite_field) and Euler's theorem (https://en.wikipedia.org/wiki/Euler%27s_totient_function). The integers mod p are such a finite field F_p, and such field have the property that they are cyclic, i.e. there exists a generator g such that
F_p = {0} U {g^x : 1 <= x <= p-1}
All elements y of F_p have the property (Euler's Theorem)
y^(p-1) = 1 mod p
1) We do not know that m < p. This is the reason why the CRT is required to construct m from solutions m_p, m_q of m_p^e = m_p mod p and m_q^e = m_q mod q.
Let r = (p-1) / gcd(e-1, p-1).
If you start with a generator g of F_p, take
y = g^r mod p
Then y^(e-1) = 1 mod p, and the same holds for powers of y. Because r * gcd(e-1,p-1) = p-1, there are only gcd(e-1,p-1) distinct powers of y modulo p.
2) See above … 1 <= x <= p-1. Note that x is unique.
3) Why do you need to find all (g, x) pairs? All you need is one generator g, and take modular powers of that.
4) You only need gcd(e-1, p-1) modular powers once you found the generator g, see answer to 1). Luckily!!! [HTML_REMOVED]
5) No, the finite field F_q is quite different from F_p; it is irrelevant that q>p. The generator is (usually) different, so you need to do it again.
Hope this helps (without spoiling …). Good luck!!