$\Big( \cfrac{q}{p} \Big)=(-1)^{\frac{p-1}{2}・\frac{q-1}{2}}\Big( \cfrac{p}{q} \Big)$ __①
これは、ガウスの平方剰余の相互法則。
この定理を分解しまして、ひねってひねって捻り倒すと…
$g_p^{\alpha}\; p+g_q^{\beta}\; q\equiv g_p^{\alpha}\;g_q^{\beta}\; (mod\; pq)$ __②
$p$、$q$は奇素数。また、$g_p$は $p$の原始根。$g_q$は $q$の原始根。
になる。
①と②は同値な命題ですので、片方を分析するともう片方の性質が分かる、かも…。
ここで特筆すべきは、
1) $\Big( \cfrac{q}{p} \Big) $ は $1$になったり $-1$になったりする。つまり、$\Big( \cfrac{q}{p} \Big)=1 or \Big( \cfrac{q}{p}\Big)=-1$
また、
2) $\Big( \cfrac{p}{q} \Big)$ も $1$になったり $-1$になったりする。従って、$\Big( \cfrac{p}{q} \Big)=1 or \Big( \cfrac{p}{q}\Big)=-1$
その他、
3) $( -1)^{\frac{p-1}{2}・\frac{q-1}{2}}$について考えましても、$( -1)^{\frac{p-1}{2}・\frac{q-1}{2}}=1 or ( -1)^{\frac{p-1}{2}・\frac{q-1}{2}}=-1$
この「3つの $1$ か $-1$ の組み合わせ」で、①は構成されている。
ここで、こう思った方はいないだろうか…？
「①の定理、$1$ と $-1$ の組み合わせによっては $1=-1$を出力するんじゃないの？」と。
述べた事をより詳しく記述してみると、
具体的に、
$p=4m_1+3$ $q=4m_2+3$の時
$\Big( \cfrac{q}{p} \Big)=-\Big( \cfrac{p}{q} \Big)$
この時、$1=1$を生成する素数のペアを探したければ
1. $\Big( \cfrac{q}{p} \Big)=1$ かつ $\Big( \cfrac{p}{q}\Big)=-1$ のペアを探すか
2. $\Big( \cfrac{q}{p} \Big)=-1$ かつ $\Big( \cfrac{p}{q} \Big)=1$ のペアを探す。
この時、$1=-1$を生成する素数のペアを探したければ
3. $\Big( \cfrac{q}{p} \Big)=1$ かつ $\Big( \cfrac{p}{q} \Big)=1$ のペアを探すか
4. $\Big( \cfrac{q}{p} \Big)=-1$ かつ $\Big( \cfrac{p}{q}\Big)=-1$ のペアを探す。
【1.である場合】
$g_p^{2A_1}\; p+g_q^{2B_1+1}\; q\equiv g_p^{2A_1}\;g_q^{2B_1+1}\;(mod\;pq)$
$2A_1=\;0 ,\;2 ,\;4 ,\;6 ,\;8 , … ,\;p-3$
$2B_1+1=\;1 ,\;3 ,\;5 ,\;7 ,\;9 ,… ,\;q-2$
【2.である場合】
$g_p^{2A_2+1}\; p+g_q^{2B_2}\; q\equiv g_p^{2A_2+1}\;g_q^{2B_2}\;(mod\;pq)$
$2A_2+1=\;1 ,\;3 ,\;5 ,\;7 ,\;9 ,… ,\;p-2$
$2B_2=\;0 ,\;2 ,\;4 ,\;6 ,\;8 , … ,\;q-3$
【3.である場合】
$g_p^{2A_1^{\prime}}\;p+q_q^{2B_1^{\prime}}\;q\equiv g_p^{2A_1^{\prime}}\;g_p^{2B_1^{\prime}}\;(mod\;pq)$
$2A_1^{\prime}=\;0 ,\;2 ,\;4 ,\;6 ,\;8 , … ,\;p-3$
$2B_1^{\prime}=\;0 ,\;2 ,\;4 ,\;6 ,\;8 , … ,\;q-3$
【4.である場合】
$g_p^{2A_2^{\prime}+1}\; p+g_q^{2B_2^{\prime}+1}\; q\equiv g_p^{2A_2^{\prime}+1}\;g_q^{2B_2^{\prime}+1}\;(mod\;pq)$
$2A_2^{\prime}+1=\;1 ,\;3 ,\;5 ,\;7 ,\;9 ,… ,\;p-2$
$2B_2^{\prime}+1=\;1 ,\;3 ,\;5 ,\;7 ,\;9 ,… ,\;q-2$
$p=4m_1+3$ $q=4m_2+1$
$p=4m_1+1$ $q=4m_2+3$
$p=4m_1+1$ $q=4m_2+1$の時
$\Big( \cfrac{q}{p} \Big)=\Big( \cfrac{p}{q} \Big)$
この時、$1=1$を生成する素数のペアを探したければ
1. $\Big( \cfrac{q}{p} \Big)=1$ かつ $\Big( \cfrac{p}{q}\Big)=1$ のペアを探すか
2. $\Big( \cfrac{q}{p} \Big)=-1$ かつ $\Big( \cfrac{p}{q} \Big)=-1$ のペアを探す。
この時、$1=-1$を生成する素数のペアを探したければ
3. $\Big( \cfrac{q}{p} \Big)=1$ かつ $\Big( \cfrac{p}{q} \Big)=-1$ のペアを探すか
4. $\Big( \cfrac{q}{p} \Big)=-1$ かつ $\Big( \cfrac{p}{q}\Big)=1$ のペアを探す。
【1.である場合】
$g_p^{2C_1}\; p+g_q^{2D_1}\; q\equiv g_p^{2C_1}\;g_q^{2D_1}\;(mod\;pq)$
$2C_1=\;0 ,\;2 ,\;4 ,\;6 ,\;8 , … ,\;p-3$
$2D_1=\;0 ,\;2 ,\;4 ,\;6 ,\;8 , … ,\;q-3$
【2.である場合】
$g_p^{2C_2+1}\; p+g_q^{2D_2+1}\; q\equiv g_p^{2C_2+1}\;g_q^{2D_2+1}\;(mod\;pq)$
$2C_2+1=\;1 ,\;3 ,\;5 ,\;7 ,\;9 ,… ,\;p-2$
$2D_2+1=\;1 ,\;3 ,\;5 ,\;7 ,\;9 ,… ,\;q-2$
【3.である場合】
$g_p^{2C_1^{\prime}}\; p+g_q^{2D_1^{\prime}+1}\; q\equiv g_p^{2C_1^{\prime}}\;g_q^{2D_1^{\prime}+1}\;(mod\;pq)$
$2C_1^{\prime}=\;0 ,\;2 ,\;4 ,\;6 ,\;8 , … ,\;p-3$
$2D_1^{\prime}+1=\;1 ,\;3 ,\;5 ,\;7 ,\;9 ,… ,\;q-2$
【4.である場合】
$g_p^{2C_2^{\prime}+1}\; p+g_q^{2D_2^{\prime}}\; q\equiv g_p^{2C^{\prime}_2+1}\;g_q^{2D^{\prime}_2}\;(mod\;pq)$
$2C_2^{\prime}+1=\;1 ,\;3 ,\;5 ,\;7 ,\;9 ,… ,\;p-2$
$2D_2^{\prime}=\;0 ,\;2 ,\;4 ,\;6 ,\;8 , … ,\;q-3$
この時、本来であれば、
赤で書かれている箇所の分析は
必要ないと思うはずです。
何故なら、1=1を生成する可能性は
「1である場合」と「2である場合」のみ
である事から。
ただ、純粋に可能性を考えてみると、
「3である場合」と「4である場合」の可能性は
排除できない。
従って、「3である場合」と「4である場合」を
分析すると、$1=-1$を出力する素数の組み合わせを
発見できるかも…。
一応これ、証明のpdfです。
$p=4m_1+3$ 及び $q=4m_2+3$ の時の証明（その１）
$p=4m_1+3$ 及び $q=4m_2+3$ の時の証明（その２）
最後に、参考文献について記しておきます。
参考文献
[1] H.N ヴィノグラードフ著（三平与右衛門・山中 建 訳）
『復刊 整数論入門』 1953年 共立出版
のみです。
