Given that a is a quadratic residue modulo p, we know
a2p−1=a2⋅2iu=(au)2i+1≡1(modp)
From this, we get (au)2i≡+1 or −1(modp). If (au)2i≡−1(modp), then μ=λ. If (au)2i≡1(modp), then we must have (au)2i−1≡1 or −1(modp). This implies μ=λ−1 or (aμ)2i−1≡1(modp), which means (au)2i−2≡−1 or +1(modp). Continuing this process, we eventually get (aμ)2≡−1 or +1(modp). This leads to μ=1 or au≡±1(modp). However, we assumed au≡±1(modp), so there must be an integer
μ=1 or 2 or ⋯ or λ,
such that
(au)2′′≡−1(modp)
Among the numbers 1,2,⋯,2j−1, there are the following 2μ−1 numbers:
2i−μ,2i−μ⋅3,2i−μ⋅5,⋯,2i−μ(2μ−1)
If t is odd, we always have
((b2u)2i−μ⋅t)2μ=(b2⋅2′μ)t≡(−1)t=−1(mod⋅p)
Thus, (b2u)2i−μ,(b2u)2i−μ⋅3,(b2u)2i−μ⋅5,(b2u)2i−μ⋅(2μ−1) are 2μ−1 solutions to the congruence equation
x2μ≡−1(modp)
This congruence equation has 2μ solutions, and the other 2μ−1 solutions are the negatives of the aforementioned 2μ−1 solutions. From the previous discussion, we know that aμ is a solution to this congruence equation, so there must be an odd number t such that
au≡+(b2u)2j−μ⋅t or −(b2u)2i−μ⋅t(modp),
which means
(b2u)2i−μ⋅t≡+au or −au(modp),
Thus, we get h˙=2i−μ⋅t. Therefore, the proposition is proved.
According to this proposition, when we need to find h, we first look for a number in the following set
(au)2,(au)22,⋯,(au)2i
that is congruent to −1 modulo p. If
(au)2A≡−1(modp)
then we must have
h=2i−μ⋅t
Next, we look for a number in the set
(b2u)2i−μ,(b2u)2i−μ⋅3,⋯,(b2u)2i−μ⋅(2μ−1),
or equivalently, in the set
b2i−μ+1⋅u,(b2i−μ+1⋅u)3,⋯,(b2i−μ+1⋅u)2μ−1
that is congruent to +aμ or −aμ modulo p. This way, we can find the integer t, and thus determine h.