Shoda čtverců - Congruence of squares - Wikipedia

tento článek ne uvést žádný Zdroje. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: "Shoda čtverců"  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Prosince 2009) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v teorie čísel, a shoda čtverců je shoda běžně používané v celočíselná faktorizace algoritmy.

Derivace

Vzhledem k tomu, pozitivní celé číslo n, Fermatova faktorizační metoda spoléhá na hledání čísel X, y uspokojení rovnost

${ displaystyle x ^ {2} -y ^ {2} = n , !}$

Můžeme pak faktorovat n = X² - y² = (X + y)(X - y). Tento algoritmus je v praxi pomalý, protože potřebujeme prohledat mnoho takových čísel a jen několik z nich splňuje přísnou rovnici. Nicméně, n lze také zohlednit, pokud dokážeme uspokojit slabší shoda čtverců stav:

${ displaystyle x ^ {2} equiv y ^ {2} { pmod {n}}}$

${ displaystyle x not equiv pm y { pmod {n}}}$

Odtud můžeme snadno odvodit

${ displaystyle x ^ {2} -y ^ {2} equiv 0 { pmod {n}}}$

${ displaystyle (x + y) (x-y) equiv 0 { pmod {n}}}$

Tohle znamená tamto n rozdělí produkt (X + y) (X - y). Tím pádem (X + y) a (X − y) každý obsahuje faktory n, ale tyto faktory mohou být banální. V tomto případě musíme najít další X a y. Výpočet největší společní dělitelé z (X + y, n) a (X - y, n) dá nám tyto faktory; to lze rychle provést pomocí Euklidovský algoritmus.

Kongruence čtverců jsou extrémně užitečné v celočíselných faktorizačních algoritmech a jsou široce používány například v kvadratické síto, síto obecného čísla, pokračující frakcionační faktorizace, a Dixonova faktorizace. Naopak, protože hledání druhých odmocnin modulo složeného čísla se ukazuje jako pravděpodobnostní polynomiálně-časově ekvivalentní faktorování tohoto čísla, lze k identifikaci shody čtverců efektivně použít jakýkoli celočíselný faktorizační algoritmus.

Další zobecnění

Je také možné použít faktorové báze pomoci rychleji najít shodu čtverců. Místo hledání ${ displaystyle textstyle x ^ {2} ekv y y {2} { pmod {n}}}$ od samého počátku jich najdeme mnoho ${ displaystyle textstyle x ^ {2} equiv y { pmod {n}}}$ Kde y mají malé hlavní faktory a pokuste se několik z nich znásobit, abyste získali čtverec na pravé straně.

Příklady

Faktorizujte 35

Bereme n = 35 a najít to

${ displaystyle textstyle 6 ^ {2} = 36 equiv 1 equiv 1 ^ {2} { pmod {35}}}$.

Faktorujeme tedy jako

${ displaystyle gcd (6-1,35) cdot gcd (6 + 1,35) = 5 cdot 7 = 35}$

Rozdělte 1649

Použitím n = 1649, jako příklad nalezení shody čtverců vytvořených z produktů jiných čtverců (viz Dixonova faktorizační metoda ), nejprve získáme několik shody

${ displaystyle 41 ^ {2} equiv 32 { pmod {1649}}}$

${ displaystyle 42 ^ {2} equiv 115 { pmod {1649}}}$

${ displaystyle 43 ^ {2} equiv 200 { pmod {1649}}}$

z toho dva mají jen malá prvočísla jako faktory

${ displaystyle 32 = 2 ^ {5}}$

${ displaystyle 200 = 2 ^ {3} cdot 5 ^ {2}}$

a jejich kombinace má rovnoměrnou sílu každého malého prvočísla, a je tedy čtvercem

${ displaystyle 32 cdot 200 = 2 ^ {5 + 3} cdot 5 ^ {2} = 2 ^ {8} cdot 5 ^ {2} = (2 ^ {4} cdot 5) ^ {2} = 80 ^ {2}}$

čímž se získá shoda čtverců

${ displaystyle 32 cdot 200 = 80 ^ {2} equiv 41 ^ {2} cdot 43 ^ {2} ekviv 114 ^ {2} { pmod {1649}}}$

Takže s použitím hodnot 80 a 114 jako našich X a y dává faktory

${ displaystyle gcd (114-80,1649) cdot gcd (114 + 80,1649) = 17 cdot 97 = 1649.}$

Viz také

• Vztah kongruence