Shankssovy čtvercové formy faktorizace - Shankss square forms factorization - Wikipedia

tento článek potřebuje pozornost odborníka na matematiku. Přidejte prosím důvod nebo a mluvit parametr k této šabloně pro vysvětlení problému s článkem. Matematika WikiProject může pomoci s náborem odborníka. (Listopadu 2008)

Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale její zdroje zůstávají nejasné, protože jí chybí vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Březen 2015) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Shanksův čtverec formuje faktorizaci je metoda pro celočíselná faktorizace vymyslel Daniel Shanks jako vylepšení Fermatova faktorizační metoda.

Úspěch Fermatovy metody závisí na nalezení celých čísel ${ displaystyle x}$ a ${ displaystyle y}$ takhle ${ displaystyle x ^ {2} -y ^ {2} = N}$, kde ${ displaystyle N}$ je celé číslo, které se má započítat. Vylepšení (všiml si Kraitchik ) je hledat celá čísla ${ displaystyle x}$ a ${ displaystyle y}$ takhle ${ displaystyle x ^ {2} equiv y ^ {2} { pmod {N}}}$. Hledání vhodného páru ${ displaystyle (x, y)}$ nezaručuje faktorizaci ve výši ${ displaystyle N}$, ale to z toho vyplývá ${ displaystyle N}$ je faktorem ${ displaystyle x ^ {2} -y ^ {2} = (x-y) (x + y)}$, a existuje velká šance, že hlavní dělitelé z ${ displaystyle N}$ jsou rozděleny mezi tyto dva faktory, takže výpočet největší společný dělitel z ${ displaystyle N}$ a ${ displaystyle x-y}$ dá netriviální faktor ${ displaystyle N}$.

Praktický algoritmus pro hledání párů ${ displaystyle (x, y)}$ které uspokojí ${ displaystyle x ^ {2} equiv y ^ {2} { pmod {N}}}$ byl vyvinut Shanksem, který jej pojmenoval Square Forms Factorization nebo SQUFOF. Algoritmus lze vyjádřit ve smyslu pokračujících zlomků nebo ve smyslu kvadratických forem. Ačkoli jsou nyní k dispozici mnohem efektivnější metody faktorizace, SQUFOF má tu výhodu, že je dostatečně malý na to, aby byl implementován na programovatelné kalkulačce.

V roce 1858 český matematik Václav Šimerka použil metodu podobnou SQUFOF ${ displaystyle (10 ^ {17} -1) / 9}$ ${ displaystyle =}$ ${ displaystyle 11111111111111111}$ ${ displaystyle =}$ ${ Displaystyle 2071723 cdot 5363222357}$.^[1]

Algoritmus

Vstup: ${ displaystyle N}$, celé číslo, které se má započítat, což nesmí být ani a prvočíslo ani a perfektní čtverec a malý multiplikátor ${ displaystyle k}$.

Výstup: netriviální faktor ${ displaystyle N}$.

Algoritmus:

Inicializovat ${ displaystyle P_ {0} = lfloor { sqrt {kN}} rfloor, Q_ {0} = 1, Q_ {1} = kN-P_ {0} ^ {2}.}$

Opakovat

${ displaystyle b_ {i} = vlevo lfloor { frac {P_ {0} + P_ {i-1}} {Q_ {i}}} pravý rfloor, P_ {i} = b_ {i} Q_ {i} -P_ {i-1}, Q_ {i + 1} = Q_ {i-1} + b_ {i} (P_ {i-1} -P_ {i})}$

dokud ${ displaystyle Q_ {i + 1}}$ je u některých dokonce perfektní čtverec ${ displaystyle i + 1}$.

Inicializovat ${ displaystyle b_ {0} = left lfloor { frac {P_ {0} -P_ {i-1}} { sqrt {Q_ {i}}}} right rfloor, P_ {0} = b_ {0} { sqrt {Q_ {i}}} + P_ {i-1}, Q_ {0} = { sqrt {Q_ {i}}}, Q_ {1} = { frac {kN-P_ { 0} ^ {2}} {Q_ {0}}}}$

Opakovat

${ displaystyle b_ {i} = left lfloor { frac {P_ {0} + P_ {i-1}} {Q_ {i}}} pravý rfloor, P_ {i} = b_ {i} Q_ {i} -P_ {i-1}, Q_ {i + 1} = Q_ {i-1} + b_ {i} (P_ {i-1} -P_ {i})}$

dokud ${ displaystyle P_ {i} = P_ {i-1}.}$

Pak pokud ${ displaystyle f = gcd (N, P_ {i})}$ se nerovná ${ displaystyle 1}$ a nerovná se ${ displaystyle N}$, pak ${ displaystyle f}$ je netriviální faktor ${ displaystyle N}$. Jinak zkuste jinou hodnotu ${ displaystyle k}$.

Shanksova metoda má časovou složitost ${ displaystyle O ({ sqrt [{4}] {N}})}$.

Stephen S. McMath vysvětluje podrobnější diskusi o matematice Shanksovy metody spolu s důkazem její správnosti.^[2]

Příklad

Nechat ${ displaystyle N = 11111, k = 1}$

Jeďte vpřed
${ displaystyle i}$	${ displaystyle P_ {i}}$	${ displaystyle Q_ {i}}$	${ displaystyle b_ {i}}$
${ displaystyle 0}$	${ displaystyle 105}$	${ displaystyle 1}$
${ displaystyle 1}$	${ displaystyle 67}$	${ displaystyle 86}$	${ displaystyle 2}$
${ displaystyle 2}$	${ displaystyle 87}$	${ displaystyle 77}$	${ displaystyle 2}$
${ displaystyle 3}$	${ displaystyle 97}$	${ displaystyle 46}$	${ displaystyle 4}$
${ displaystyle 4}$	${ displaystyle 88}$	${ displaystyle 37}$	${ displaystyle 5}$
${ displaystyle 5}$	${ displaystyle 94}$	${ displaystyle 91}$	${ displaystyle 2}$
${ displaystyle 6}$		${ displaystyle 25}$

Tady ${ displaystyle Q_ {6} = 25}$ je perfektní čtverec.

Reverzní cyklus
${ displaystyle i}$	${ displaystyle P_ {i}}$	${ displaystyle Q_ {i}}$	${ displaystyle b_ {i}}$
${ displaystyle 0}$	${ displaystyle 104}$	${ displaystyle 5}$	${ displaystyle 2}$
${ displaystyle 1}$	${ displaystyle 73}$	${ displaystyle 59}$	${ displaystyle 3}$
${ displaystyle 2}$	${ displaystyle 25}$	${ displaystyle 98}$	${ displaystyle 1}$
${ displaystyle 3}$	${ displaystyle 82}$	${ displaystyle 107}$	${ displaystyle 1}$
${ displaystyle 4}$	${ displaystyle 82}$	${ displaystyle 41}$	${ displaystyle 4}$

Tady ${ displaystyle P_ {3} = P_ {4} = 82}$.

${ displaystyle gcd (11111,82) = 41}$, což je faktor ${ displaystyle 11111}$.

Tím pádem, ${ displaystyle N = 11111 = 41 cdot 271}$

Ukázkové implementace

Níže je uveden příklad funkce C pro provádění faktorizace SQUFOF na celé číslo bez znaménka, které není větší než 64 bitů, bez přetečení přechodných operací.^{[Citace je zapotřebí ]}

#zahrnout <inttypes.h>#define nelems (x) (sizeof (x) / sizeof ((x) [0]))konst int násobitel[] = {1, 3, 5, 7, 11, 3*5, 3*7, 3*11, 5*7, 5*11, 7*11, 3*5*7, 3*5*11, 3*7*11, 5*7*11, 3*5*7*11};uint64_t SQUFOF( uint64_t N ){    uint64_t D, Po, P, Pprev, Q, Qprev, q, b, r, s;    uint32_t L, B, i;    s = (uint64_t)(sqrtl(N)+0.5);    -li (s*s == N) vrátit se s;    pro (int k = 0; k < nelems(násobitel) && N <= UINT64_MAX/násobitel[k]; k++) {        D = násobitel[k]*N;        Po = Pprev = P = sqrtl(D);        Qprev = 1;        Q = D - Po*Po;        L = 2 * sqrtl( 2*s );        B = 3 * L;        pro (i = 2 ; i < B ; i++) {            b = (uint64_t)((Po + P)/Q);            P = b*Q - P;            q = Q;            Q = Qprev + b*(Pprev - P);            r = (uint64_t)(sqrtl(Q)+0.5);            -li (!(i & 1) && r*r == Q) přestávka;            Qprev = q;            Pprev = P;        };        -li (i >= B) pokračovat;        b = (uint64_t)((Po - P)/r);        Pprev = P = b*r + P;        Qprev = r;        Q = (D - Pprev*Pprev)/Qprev;        i = 0;        dělat {            b = (uint64_t)((Po + P)/Q);            Pprev = P;            P = b*Q - P;            q = Q;            Q = Qprev + b*(Pprev - P);            Qprev = q;            i++;        } zatímco (P != Pprev);        r = gcd(N, Qprev);        -li (r != 1 && r != N) vrátit se r;    }    vrátit se 0;}

Reference

• D. A. Buell (1989). Binární kvadratické formy. Springer-Verlag. ISBN  0-387-97037-1.
• D. M. Bressoud (1989). Faktorizace a testování primality. Springer-Verlag. ISBN  0-387-97040-1.
• Riesel, Hans (1994). Prvočísla a počítačové metody pro faktorizaci (2. vyd.). Birkhauser. ISBN  0-8176-3743-5.
• Samuel S. Wagstaff, Jr. (2013). Radost z faktoringu. Providence, RI: American Mathematical Society. 163–168. ISBN  978-1-4704-1048-3.

externí odkazy

• Daniel Shanks: Analýza a zdokonalení metody faktorizace další frakce (přepsáno S. McMathem 2004)
• Daniel Shanks: Poznámky SQUFOF (přepsáno S. McMathem 2004)
• Stephen S. McMath: Paralelní celočíselná faktorizace pomocí kvadratických forem, 2005
• S. McMath, F. Crabbe, D. Joyner: Pokračující zlomky a paralelní SQUFOF, 2005
• Jason Gower, Samuel Wagstaff: Faktorizace čtvercového tvaru (Zveřejněno)
• Shanksův SQUFOF factoringový algoritmus
• java-math-library