Pocklingtonův algoritmus - Pocklingtons algorithm - Wikipedia

Pocklingtonův algoritmus je technika řešení a shoda formuláře

${ displaystyle x ^ {2} equiv a { pmod {p}},}$

kde X a A jsou celá čísla a A je kvadratický zbytek.

Algoritmus je jednou z prvních účinných metod řešení takové kongruence. Popsal to H.C. Pocklington v roce 1917.^[1]

Algoritmus

(Poznámka: všechny ${ displaystyle equiv}$ se rozumí ${ displaystyle { pmod {p}}}$, pokud není uvedeno jinak.)

Vstupy:

• p, zvláštní primární
• A, celé číslo, které je kvadratickým zbytkem ${ displaystyle { pmod {p}}}$.

Výstupy:

• X, celé číslo uspokojující ${ displaystyle x ^ {2} equiv a}$. Všimněte si, že pokud X je řešení, -X je také řešením a od té doby p je zvláštní, ${ displaystyle x neq -x}$. Když se nějaké najde, vždy existuje druhé řešení.

Metoda řešení

Pocklington odděluje 3 různé případy pro p:

První případ, pokud ${ displaystyle p = 4m + 3}$, s ${ displaystyle m in mathbb {N}}$, řešení je ${ displaystyle x equiv pm a ^ {m + 1}}$.

Druhý případ, pokud ${ displaystyle p = 8m + 5}$, s ${ displaystyle m in mathbb {N}}$ a

1. ${ displaystyle a ^ {2m + 1} equiv 1}$, řešení je ${ displaystyle x equiv pm a ^ {m + 1}}$.
2. ${ displaystyle a ^ {2m + 1} ekv. -1}$, 2 je (kvadratický) zbytek ${ displaystyle 4 ^ {2m + 1} ekv. -1}$. Tohle znamená tamto ${ displaystyle (4a) ^ {2m + 1} equiv 1}$ tak ${ displaystyle y equiv pm (4a) ^ {m + 1}}$ je řešením ${ displaystyle y ^ {2} equiv 4a}$. Proto ${ displaystyle x equiv pm y / 2}$ nebo když y je zvláštní, ${ Displaystyle x equiv pm (p + y) / 2}$.

Třetí případ, pokud ${ displaystyle p = 8m + 1}$, dát ${ displaystyle D equiv -a}$, takže rovnice k řešení se stane ${ displaystyle x ^ {2} + D equiv 0}$. Nyní vyhledejte metodou pokusu a omylu ${ displaystyle t_ {1}}$ a ${ displaystyle u_ {1}}$ aby ${ displaystyle N = t_ {1} ^ {2} -Du_ {1} ^ {2}}$ je kvadratický zbytek. Kromě toho

${ displaystyle t_ {n} = { frac {(t_ {1} + u_ {1} { sqrt {D}}) ^ {n} + (t_ {1} -u_ {1} { sqrt {D }}) ^ {n}} {2}}, qquad u_ {n} = { frac {(t_ {1} + u_ {1} { sqrt {D}}) ^ {n} - (t_ { 1} -u_ {1} { sqrt {D}}) ^ {n}} {2 { sqrt {D}}}}}$.

Nyní platí následující rovnosti:

${ displaystyle t_ {m + n} = t_ {m} t_ {n} + Du_ {m} u_ {n}, quad u_ {m + n} = t_ {m} u_ {n} + t_ {n} u_ {m} quad { mbox {a}} quad t_ {n} ^ {2} -Du_ {n} ^ {2} = N ^ {n}}$.

Předpokládám to p je ve formě ${ displaystyle 4m + 1}$ (což je pravda, pokud p je ve formě ${ displaystyle 8m + 1}$), D je kvadratický zbytek a ${ displaystyle t_ {p} equiv t_ {1} ^ {p} equiv t_ {1}, quad u_ {p} equiv u_ {1} ^ {p} D ^ {(p-1) / 2 } equiv u_ {1}}$. Nyní rovnice

${ displaystyle t_ {1} equiv t_ {p-1} t_ {1} + Du_ {p-1} u_ {1} quad { mbox {a}} quad u_ {1} equiv t_ {p -1} u_ {1} + t_ {1} u_ {p-1}}$

dát řešení ${ displaystyle t_ {p-1} equiv 1, quad u_ {p-1} equiv 0}$.

Nechat ${ displaystyle p-1 = 2r}$. Pak ${ displaystyle 0 equiv u_ {p-1} equiv 2t_ {r} u_ {r}}$. To znamená, že buď ${ displaystyle t_ {r}}$ nebo ${ displaystyle u_ {r}}$ je dělitelné p. Pokud to je ${ displaystyle u_ {r}}$, dát ${ displaystyle r = 2s}$ a postupujte obdobně s ${ displaystyle 0 equiv 2t_ {s} u_ {s}}$. Ne každý ${ displaystyle u_ {i}}$ je dělitelné p, pro ${ displaystyle u_ {1}}$ není. Pouzdro ${ displaystyle u_ {m} equiv 0}$ s m zvláštní je nemožné, protože ${ displaystyle t_ {m} ^ {2} -Du_ {m} ^ {2} equiv N ^ {m}}$ drží a to by znamenalo, že ${ displaystyle t_ {m} ^ {2}}$ je v souladu s kvadratickým nezbytkem, což je rozpor. Takže tato smyčka se zastaví, když ${ displaystyle t_ {l} equiv 0}$ pro konkrétní l. To dává ${ displaystyle -Du_ {l} ^ {2} equiv N ^ {l}}$, a protože ${ displaystyle -D}$ je kvadratický zbytek, l musí být rovnoměrné. Dát ${ displaystyle l = 2k}$. Pak ${ displaystyle 0 equiv t_ {l} equiv t_ {k} ^ {2} + Du_ {k} ^ {2}}$. Takže řešení ${ displaystyle x ^ {2} + D equiv 0}$ se získá řešením lineární kongruence ${ displaystyle u_ {k} x ekviv pm t_ {k}}$.

Příklady

Následují 4 příklady odpovídající 3 různým případům, ve kterých Pocklington rozdělil formy p. Všechno ${ displaystyle equiv}$ jsou brány s modul v příkladu.

Příklad 0

${ displaystyle x ^ {2} equiv 43 { pmod {47}}.}$

Toto je první případ, podle algoritmu, ${ displaystyle x equiv 43 ^ {(47 + 1) / 2} = 43 ^ {12} equiv 2}$, ale pak ${ displaystyle x ^ {2} = 2 ^ {2} = 4}$ ne 43, takže bychom algoritmus neměli vůbec používat. Důvod, proč algoritmus není použitelný, je ten, že a = 43 je kvadratickým nezbytkem pro p = 47.

Příklad 1

Vyřešte shodu

${ displaystyle x ^ {2} equiv 18 { pmod {23}}.}$

Modul je 23. To je ${ displaystyle 23 = 4 cdot 5 + 3}$, tak ${ displaystyle m = 5}$. Řešení by mělo být ${ displaystyle x equiv pm 18 ^ {6} equiv pm 8 { pmod {23}}}$, což je skutečně pravda: ${ displaystyle ( pm 8) ^ {2} equiv 64 equiv 18 { pmod {23}}}$.

Příklad 2

Vyřešte shodu

${ displaystyle x ^ {2} equiv 10 { pmod {13}}.}$

Modul je 13. To je ${ displaystyle 13 = 8 cdot 1 + 5}$, tak ${ displaystyle m = 1}$. Nyní se ověřuje ${ displaystyle 10 ^ {2m + 1} equiv 10 ^ {3} equiv -1 { pmod {13}}}$. Řešení tedy je ${ displaystyle x equiv pm y / 2 equiv pm (4a) ^ {2} / 2 equiv pm 800 equiv pm 7 { pmod {13}}}$. To je skutečně pravda: ${ displaystyle ( pm 7) ^ {2} equiv 49 equiv 10 { pmod {13}}}$.

Příklad 3

Vyřešte shodu ${ displaystyle x ^ {2} equiv 13 { pmod {17}}}$. K tomu napište ${ displaystyle x ^ {2} -13 = 0}$. Nejprve najděte a ${ displaystyle t_ {1}}$ a ${ displaystyle u_ {1}}$ takhle ${ displaystyle t_ {1} ^ {2} + 13u_ {1} ^ {2}}$ je kvadratický zbytek. Vezměme si například ${ displaystyle t_ {1} = 3, u_ {1} = 1}$. Nyní najděte ${ displaystyle t_ {8}}$, ${ displaystyle u_ {8}}$ výpočtem

${ displaystyle t_ {2} = t_ {1} t_ {1} + 13u_ {1} u_ {1} = 9-13 = -4 equiv 13 { pmod {17}},}$

${ displaystyle u_ {2} = t_ {1} u_ {1} + t_ {1} u_ {1} = 3 + 3 equiv 6 { pmod {17}}.}$

A podobně ${ displaystyle t_ {4} = - 299 equiv 7 { pmod {17}}, u_ {4} = 156 equiv 3 { pmod {17}}}$ takhle ${ displaystyle t_ {8} = - 68 equiv 0 { pmod {17}}, u_ {8} = 42 equiv 8 { pmod {17}}.}$

Od té doby ${ displaystyle t_ {8} = 0}$, rovnice ${ displaystyle 0 equiv t_ {4} ^ {2} + 13u_ {4} ^ {2} equiv 7 ^ {2} -13 cdot 3 ^ {2} { pmod {17}}}$ což vede k řešení rovnice ${ displaystyle 3x equiv pm 7 { pmod {17}}}$. To má řešení ${ displaystyle x equiv pm 8 { pmod {17}}}$. Vskutku, ${ displaystyle ( pm 8) ^ {2} = 64 equiv 13 { pmod {17}}}$.

Reference

• Leonard Eugene Dickson, „History of the Theory of Numbers“, svazek 1, str. 222, nakladatelství Chelsea 1952