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!!