/------------------------------------------------------------\
/ \
Q2a: The number P := 1433 is a 4pos prime. I would like you to
"probabilistically" find a P-rono I, via the following method.
Recall numbers H, D, and J, where
H := [P-1]/2 and [2^J]·D = H.
Here D is an odd posint and J is a natnum. That is, factor out the
highest power of 2 from H. Since P is 4pos, necessarily H is even
so J is a least one.
At random, pick an integer r in [2 .. H]. Your goal is to find
one such r which is a P-NQR. [That is, r is co-prime to P, and is
*not* a mod-P square.] Once you have found such an r, you can
2: Use repeated-squaring to compute k := . Now square k,
then square that result, etc, always reducing mod-P. Argue
that before J many squarings you will have found a P-rono.
[Use -and carefully CITE- the LST as appropriate.]
1: In order to randomly have found a P-NQR, use the LST and
Repeated-squaring.
Notice that you can in fact combine steps 1 and 2, so as to
simultaneously discover whether r is a NQR and to get a P-rono.
Cite your result as a separate Lemma, and give a formal proof.
[Of course, most of your proof will be citing parts of LST.]
================
Q2b: Discussion problem. Now suppose that P is known to be a
product of two distinct 4pos primes, P = B·C, but
** we are unable to factor P **.
Discuss the (Q2a) algorithm for such a P, what works and what
doesn't. Can you suggest a deterministic or probabilistic
rono-finding algorithm for such a P?
\ /
\____________________________________________________________/