“Shanks's square forms factorization”的意思、由来-开放百科全书

词条

Shanks's square forms factorization

释义

Algorithm
Example
Example implementations
References
External links

Shanks's square forms factorization is a method for integer factorization devised by Daniel Shanks as an improvement on Fermat's factorization method.

The success of Fermat's method depends on finding integers and such that , where is the integer to be factored. An improvement (noticed by Kraitchik) is to look for integers and such that . Finding a suitable pair does not guarantee a factorization of , but it implies that is a factor of , and there is a good chance that the prime divisors of are distributed between these two factors, so that calculation of the greatest common divisor of and will give a non-trivial factor of .

A practical algorithm for finding pairs which satisfy was developed by Shanks, who named it Square Forms Factorization or SQUFOF. The algorithm can be expressed in terms of continued fractions or in terms of quadratic forms. Although there are now much more efficient factorization methods available, SQUFOF has the advantage that it is small enough to be implemented on a programmable calculator.

Algorithm

Input: , the integer to be factored, which must be neither a prime number nor a perfect square, and a small multiplier .

Output: a non-trivial factor of .

The algorithm:

Initialize

Repeat

until is a perfect square at some even .

Initialize

Repeat

until

Then if is not equal to and not equal to , then is a non-trivial factor of . Otherwise try another value of .

Shanks's method has time complexity .

Stephen S. McMath wrote

a more detailed discussion of the mathematics of Shanks's method,

together with a proof of its correctness.^[1]

Example

Let

 ! ! ! !

Here is a perfect square.

 ! ! ! !

Here .

, which is a factor of .

Thus,

Example implementations

Below is an example of C function for performing SQUFOF factorization on unsigned integer not larger than 64 bits, without overflow of the transient operations. {{cn|date=May 2017}}

include
define nelems(x) (sizeof(x) / sizeof((x)[0]))

const int multiplier[] = {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);    if (s*s == N) return s;    for (int k = 0; k < nelems(multiplier) && N <= UINT64_MAX/multiplier[k]; k++) {        D = multiplier[k]*N;        Po = Pprev = P = sqrtl(D);        Qprev = 1;        Q = D - Po*Po;        L = 2 * sqrtl( 2*s );        B = 3 * L;        for (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);            if (!(i & 1) && r*r == Q) break;            Qprev = q;            Pprev = P;        };        if (i >= B) continue;        b = (uint64_t)((Po - P)/r);        Pprev = P = b*r + P;        Qprev = r;        Q = (D - Pprev*Pprev)/Qprev;        i = 0;        do {            b = (uint64_t)((Po + P)/Q);            Pprev = P;            P = b*Q - P;            q = Q;            Q = Qprev + b*(Pprev - P);            Qprev = q;            i++;        } while (P != Pprev);        r = gcd(N, Qprev);        if (r != 1 && r != N) return r;    }    return 0;

}

References

1. ^{{Cite web|url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.107.9984&rep=rep1&type=pdf|title=Daniel Shanks’ Square Forms Factorization|last=|first=|date=|website=citeseerx.ist.psu.edu|archive-url=|archive-date=|dead-url=|access-date=2018-10-04}}

{{cite book

| author = D. A. Buell
| title = Binary Quadratic Forms
| publisher = Springer-Verlag
| year = 1989
| isbn=0-387-97037-1 }}

{{cite book

| author = D. M. Bressoud|authorlink=David Bressoud
| title = Factorisation and Primality Testing
| publisher = Springer-Verlag
| year = 1989
| isbn=0-387-97040-1 }}

{{cite book

| last=Riesel | first=Hans | authorlink=Hans Riesel
| title=Prime numbers and computer methods for factorization
| publisher=Birkhauser
|edition = 2nd
| year=1994
| isbn=0-8176-3743-5 }}

{{cite book | author =Samuel S. Wagstaff, Jr. | title=The Joy of Factoring | publisher=American Mathematical Society | location=Providence, RI | year=2013 | isbn=978-1-4704-1048-3 |url=http://www.ams.org/bookpages/stml-68 |author-link=Samuel S. Wagstaff, Jr. |pages=163–168 }}

External links

Daniel Shanks: Analysis and Improvement of the Continued Fraction Method of Factorization, (transcribed by S. McMath 2004)
Daniel Shanks: SQUFOF Notes, (transcribed by S. McMath 2004)
Stephen S. McMath: Parallel integer factorization using quadratic forms, 2005
S. McMath, F. Crabbe, D. Joyner: Continued fractions and parallel SQUFOF, 2005
Jason Gower, Samuel Wagstaff: Square Form Factorisation (Published)
Shanks's SQUFOF Factoring Algorithm
[https://github.com/TilmanNeumann/java-math-library java-math-library]

1 : Integer factorization algorithms

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。