mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2017-06-24, 22:02   #155
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
Here's another question: What's the theoretical justification for requiring that the four squares add up exactly to N? The reason I ask is, I thought of a way to speed up the process of using 4-tuples (a, b, c, d) to find factors of N: simply drop the requirement that

a^2 + b^2 + c^2 + d^2 = N exactly.

As long as a^2 + b^2 + c^2 + d^2 is close to N, go ahead and form the sums of some or all of a, b, c, d, a^2, b^2, c^2, and d^2, and take the gcd with N. (There are 127 nonempty sums.)

I hypothesize that, there being so many possibilities, the chances are good that any factor of N under 100 will show up fairly quickly. I tried this idea with N = 1457 = 31*47, and the results were better than I expected. Even though a^2 + b^2 + c^2 + d^2 never hit N right on the nose, I still got at least one of the 15 sums of a, b, c, and d alone having a common factor with N in 6 of 8 tries.

If anyone would care to have a go at my examples N = 77, 1457, 3901, 4661, 6557, 7597, 8549, and 9869 using this approach, have at them!

I cheerfully proclaim that this approach really is nothing more than blazing away with a scattergun, in hopes that some of the buckshot will hit. The advantage over the OP's idea is, reloading is a whole lot quicker
;-)
my guess is so it's easier than the Mondrian art puzzle problem for the squares thing or that it's easier potentially than using cuboids to fill other cuboids etc. some numbers only have 2 factors so they can't be expressed as cuboids that don't have 2 side lengths of 1.
etc. I still don't see how you get 127 if you use n things for each part of the sum a sum of 4 things with n each will allow n^4 which 127 does not fit if you allow. yes I I know there's overlap I also know that some sums as squares aren't worth looking at for example for N=4 we have:

2^2+0^2+0^2+0^2
1^2+1^2+1^2+1^2

as well as these times -1 for all (a,b,c,d) (b,c,d,a) etc. some which use all negative numbers. it wasn't specified these wouldn't be used.
science_man_88 is offline   Reply With Quote
Old 2017-06-24, 23:37   #156
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

512510 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
I still don't see how you get 127 if you use n things for each part of the sum
There are 8 terms a, b, c, d, a^2, b^2, c^2, d^2. The number of sums of these terms, each with coefficient either 1 or 0, is 2^8 or 128. The terms with coefficient 1 may be viewed as a subset of a set of 8 elements. The sum with all coefficients 0 corresponds to the empty set, and is of course 0. Similarly, there are 2^4 - 1 = 15 non-empty sums of the four roots a, b, c, and d.

Of course, not all of a, b, c, and d need be different. And even if they are, not all the sums need be different.
Dr Sardonicus is offline   Reply With Quote
Old 2017-06-25, 00:42   #157
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×5×641 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
Here's another question: What's the theoretical justification for requiring that the four squares add up exactly to N? The reason I ask is, I thought of a way to speed up the process of using 4-tuples (a, b, c, d) to find factors of N: simply drop the requirement that

a^2 + b^2 + c^2 + d^2 = N exactly.

As long as a^2 + b^2 + c^2 + d^2 is close to N, go ahead ...

I cheerfully proclaim that this approach really is nothing more than blazing away with a scattergun, in hopes that some of the buckshot will hit. The advantage over the OP's idea is, reloading is a whole lot quicker
;-)
Great thinking, Doctor!

The next beautiful enhancement is to drop the requirement that a^2 + b^2 + c^2 + d^2 is close to N. And then again, what is 'close' anyway? I think 17 and 998651 are reasonably close, at least from where I sit (which is at 150-290-digit numbers).

And yet the next enhancement (because now the a^2 + b^2 + c^2 + d^2 can be equal to anything) is to restate: "Take any random a, b, c, d of size of sqrt(N), then do gcd(N, all linear combinations of {a, b, c, d and a^2, b^2, c^2, d^2} ). Repeat N times if needed. I guarantee that you will factor N." Scout's honor! In fact you will factor N faster, because you will not be uselessly check if a^2 + b^2 + c^2 + d^2 is equal (or close) to N.
Batalov is offline   Reply With Quote
Old 2017-06-25, 00:50   #158
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2×23×137 Posts
Thumbs up

Long ago in this thread it was already apparent that using a^2 + b^2 + c^2 + d^2 = N fails the sufficiency test. And now it appears that using a^2 + b^2 + c^2 + d^2 = N also fails the necessity test.

Yay. So after all the posts here we can can finally ignore the big distraction about bothering to test for a^2 + b^2 + c^2 + d^2 = N and instead just use a bunch of random numbers.

Conclusion at last. End of thread.

Last fiddled with by retina on 2017-06-25 at 00:51
retina is offline   Reply With Quote
Old 2017-06-25, 02:56   #159
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by retina View Post
Long ago in this thread it was already apparent that using a^2 + b^2 + c^2 + d^2 = N fails the sufficiency test. And now it appears that using a^2 + b^2 + c^2 + d^2 = N also fails the necessity test.

Yay. So after all the posts here we can can finally ignore the big distraction about bothering to test for a^2 + b^2 + c^2 + d^2 = N and instead just use a bunch of random numbers.

Conclusion at last. End of thread.
In fairness I mentioned this on page 3 and showed how much faster it was.

Quote:
Originally Posted by Dr Sardonicus View Post
Here's another question: What's the theoretical justification for requiring that the four squares add up exactly to N? The reason I ask is, I thought of a way to speed up the process of using 4-tuples (a, b, c, d) to find factors of N: simply drop the requirement that

a^2 + b^2 + c^2 + d^2 = N exactly.

As long as a^2 + b^2 + c^2 + d^2 is close to N, go ahead and form the sums of some or all of a, b, c, d, a^2, b^2, c^2, and d^2, and take the gcd with N. (There are 127 nonempty sums.)

I hypothesize that, there being so many possibilities, the chances are good that any factor of N under 100 will show up fairly quickly. I tried this idea with N = 1457 = 31*47, and the results were better than I expected. Even though a^2 + b^2 + c^2 + d^2 never hit N right on the nose, I still got at least one of the 15 sums of a, b, c, and d alone having a common factor with N in 6 of 8 tries.

If anyone would care to have a go at my examples N = 77, 1457, 3901, 4661, 6557, 7597, 8549, and 9869 using this approach, have at them!

I cheerfully proclaim that this approach really is nothing more than blazing away with a scattergun, in hopes that some of the buckshot will hit. The advantage over the OP's idea is, reloading is a whole lot quicker
;-)
Here's one implementation of your approach:
Code:
scattergun(n)=my(s=sqrtint(n),a2,b2,c2,d2,g); for(a=s\2,n, a2=a^2; for(b=a,s, b2=b^2; for(c=b,s, c2=c^2; for(d=c,s, g=gcd(n,a); if(g>1, return(g)); g=gcd(n,b); if(g>1, return(g)); g=gcd(n,c); if(g>1, return(g)); g=gcd(n,d); if(g>1, return(g)); g=gcd(n,a2+b2); if(g>1 && g<n, return(g)); g=gcd(n,a2+c2); if(g>1 && g<n, return(g)); d2=d^2; g=gcd(n,a2+d2); if(g>1 && g<n, return(g)); g=gcd(n,a+b); if(g>1 && g<n, return(g)); g=gcd(n,a+c); if(g>1 && g<n, return(g)); g=gcd(n,a+d); if(g>1 && g<n, return(g)); g=gcd(n,b+c); if(g>1 && g<n, return(g)); g=gcd(n,b+d); if(g>1 && g<n, return(g)); g=gcd(n,c+d); if(g>1 && g<n, return(g)); g=gcd(n,a+b+c); if(g>1 && g<n, return(g)); g=gcd(n,a+b+d); if(g>1 && g<n, return(g)); g=gcd(n,a+c+d); if(g>1 && g<n, return(g)); g=gcd(n,b+c+d); if(g>1 && g<n, return(g)); g=gcd(n,a+b+c+d); if(g>1 && g<n, return(g)))))); "could not factor";
For comparison, the other methods:

Code:
factorblind(n)=my(s=(sqrtint(n)-3)\2,r); while(n%(r=2*random(s)+3),); r;
sqrtup(n)=n=ceil(n); if(issquare(n,&n),n,sqrtint(n)+1);
mahbel(n)=my(a2,b2,c2,d,d2,g); for(a=sqrtup(n/4),sqrtint(n), a2=a^2; for(b=sqrtup((n-a2)/3),min(sqrtint(n-a2),a), b2=b^2; for(c=sqrtup((n-a2-b2)/2),min(sqrtint(n-a2-b2),b), c2=c^2; if(issquare(n-a2-b2-c2,&d)&&c>=d, d2=d^2; g=gcd(n,a); if(g>1 && g<n, return(g)); g=gcd(n,b); if(g>1 && g<n, return(g)); g=gcd(n,c); if(g>1 && g<n, return(g)); g=gcd(n,d); if(g>1 && g<n, return(g)); g=gcd(n,a2+b2); if(g>1 && g<n, return(g)); g=gcd(n,a2+c2); if(g>1 && g<n, return(g)); g=gcd(n,a2+d2); if(g>1 && g<n, return(g)))))); "could not factor";
mahbelExtended(n)=my(a2,b2,c2,d,d2,g); for(a=sqrtup(n/4),sqrtint(n), a2=a^2; for(b=sqrtup((n-a2)/3),min(sqrtint(n-a2),a), b2=b^2; for(c=sqrtup((n-a2-b2)/2),min(sqrtint(n-a2-b2),b), c2=c^2; if(issquare(n-a2-b2-c2,&d)&&c>=d, d2=d^2; g=gcd(n,a); if(g>1 && g<n, return(g)); g=gcd(n,b); if(g>1 && g<n, return(g)); g=gcd(n,c); if(g>1 && g<n, return(g)); g=gcd(n,d); if(g>1 && g<n, return(g)); g=gcd(n,a2+b2); if(g>1 && g<n, return(g)); g=gcd(n,a2+c2); if(g>1 && g<n, return(g)); g=gcd(n,a2+d2); if(g>1 && g<n, return(g)); g=gcd(n,a+b); if(g>1 && g<n, return(g)); g=gcd(n,a+c); if(g>1 && g<n, return(g)); g=gcd(n,a+d); if(g>1 && g<n, return(g)); g=gcd(n,b+c); if(g>1 && g<n, return(g)); g=gcd(n,b+d); if(g>1 && g<n, return(g)); g=gcd(n,c+d); if(g>1 && g<n, return(g)); g=gcd(n,a+b+c); if(g>1 && g<n, return(g)); g=gcd(n,a+b+d); if(g>1 && g<n, return(g)); g=gcd(n,a+c+d); if(g>1 && g<n, return(g)); g=gcd(n,b+c+d); if(g>1 && g<n, return(g)); g=gcd(n,a+b+c+d); if(g>1 && g<n, return(g)))))); "could not factor";
mahbelDoubleExtended(n)=my(a2,b2,c2,d,d2,g); for(a=sqrtup(n/4),sqrtint(n), a2=a^2; for(b=sqrtup((n-a2)/3),min(sqrtint(n-a2),a), b2=b^2; for(c=sqrtup((n-a2-b2)/2),min(sqrtint(n-a2-b2),b), c2=c^2; if(issquare(n-a2-b2-c2,&d)&&c>=d, d2=d^2; g=gcd(n,a); if(g>1, return(g));g=gcd(n,b); if(g>1, return(g));g=gcd(n,c); if(g>1, return(g));g=gcd(n,d); if(g>1, return(g));g=gcd(n,a2+b2); if(g>1 && g<n, return(g));g=gcd(n,a2+c2); if(g>1 && g<n, return(g));g=gcd(n,a2+d2); if(g>1 && g<n, return(g));g=gcd(n,c+d); if(g>1 && g<n, return(g));g=gcd(n,c+d2); if(g>1 && g<n, return(g));g=gcd(n,c2+d); if(g>1 && g<n, return(g));g=gcd(n,b+d); if(g>1 && g<n, return(g));g=gcd(n,b+d2); if(g>1 && g<n, return(g));g=gcd(n,b+c); if(g>1 && g<n, return(g));g=gcd(n,b+c+d); if(g>1 && g<n, return(g));g=gcd(n,b+c+d2); if(g>1 && g<n, return(g));g=gcd(n,b+c2); if(g>1 && g<n, return(g));g=gcd(n,b+c2+d); if(g>1 && g<n, return(g));g=gcd(n,a2+b2-b); if(g>1 && g<n, return(g));g=gcd(n,b2+d); if(g>1 && g<n, return(g));g=gcd(n,b2+c); if(g>1 && g<n, return(g));g=gcd(n,b2+c+d); if(g>1 && g<n, return(g));g=gcd(n,a2+c2-c); if(g>1 && g<n, return(g));g=gcd(n,a2+d2-d); if(g>1 && g<n, return(g));g=gcd(n,a+d); if(g>1 && g<n, return(g));g=gcd(n,a+d2); if(g>1 && g<n, return(g));g=gcd(n,a+c); if(g>1 && g<n, return(g));g=gcd(n,a+c+d); if(g>1 && g<n, return(g));g=gcd(n,a+c+d2); if(g>1 && g<n, return(g));g=gcd(n,a+c2); if(g>1 && g<n, return(g));g=gcd(n,a+c2+d); if(g>1 && g<n, return(g));g=gcd(n,a2-a+b2); if(g>1 && g<n, return(g));g=gcd(n,a+b); if(g>1 && g<n, return(g));g=gcd(n,a+b+d); if(g>1 && g<n, return(g));g=gcd(n,a+b+d2); if(g>1 && g<n, return(g));g=gcd(n,a+b+c); if(g>1 && g<n, return(g));g=gcd(n,a+b+c+d); if(g>1 && g<n, return(g));g=gcd(n,a+b+c+d2); if(g>1 && g<n, return(g));g=gcd(n,a+b+c2); if(g>1 && g<n, return(g));g=gcd(n,a+b+c2+d); if(g>1 && g<n, return(g));g=gcd(n,a2-a+b2-b); if(g>1 && g<n, return(g));g=gcd(n,a+b2); if(g>1 && g<n, return(g));g=gcd(n,a+b2+d); if(g>1 && g<n, return(g));g=gcd(n,a2-a+c2); if(g>1 && g<n, return(g));g=gcd(n,a+b2+c); if(g>1 && g<n, return(g));g=gcd(n,a+b2+c+d); if(g>1 && g<n, return(g));g=gcd(n,a2-a+c2-c); if(g>1 && g<n, return(g));g=gcd(n,a2-a+d2); if(g>1 && g<n, return(g));g=gcd(n,a2-a+d2-d); if(g>1 && g<n, return(g));g=gcd(n,a2-a); if(g>1 && g<n, return(g));g=gcd(n,a2+d); if(g>1 && g<n, return(g));g=gcd(n,a2+c); if(g>1 && g<n, return(g));g=gcd(n,a2+c+d); if(g>1 && g<n, return(g));g=gcd(n,b2+c2-c); if(g>1 && g<n, return(g));g=gcd(n,b2+d2-d); if(g>1 && g<n, return(g));g=gcd(n,a2+b); if(g>1 && g<n, return(g));g=gcd(n,a2+b+d); if(g>1 && g<n, return(g));g=gcd(n,b2-b+c2); if(g>1 && g<n, return(g));g=gcd(n,a2+b+c); if(g>1 && g<n, return(g));g=gcd(n,a2+b+c+d); if(g>1 && g<n, return(g));g=gcd(n,b2-b+c2-c); if(g>1 && g<n, return(g));g=gcd(n,b2-b+d2); if(g>1 && g<n, return(g));g=gcd(n,b2-b+d2-d); if(g>1 && g<n, return(g));g=gcd(n,b2-b); if(g>1 && g<n, return(g));g=gcd(n,c2+d2-d); if(g>1 && g<n, return(g));g=gcd(n,c2-c+d2); if(g>1 && g<n, return(g));g=gcd(n,c2-c+d2-d); if(g>1 && g<n, return(g));g=gcd(n,c2-c); if(g>1 && g<n, return(g));g=gcd(n,d2-d); if(g>1 && g<n, return(g)))))); "could not factor";
Now, let's write some code to compare them, along with two standard methods for comparison:
Code:
rsp(len)=my(mn=10^(len-1),mx=10^len-1,p=randomprime([sqrtup(mn/2),sqrtint(mx)]),q=randomprime([ceil(mn/p),mx\p])); p*q;
trialDivision(n)=forprime(p=2,sqrtint(n), if(n%p==0, return(p))); n;
gpf(n)=my(f=factor(n)[,1]); f[#f];
test(len,trials,methods)=my(v=vector(trials,i,rsp(len)),t); for(i=1,#methods, gettime(); print1("Method #"i" factored "sum(j=1,#v,t=methods[i](v[j]); type(t)=="t_INT" && t>1 && t<v[j] && v[j]%t==0)); print(" "len"-digit numbers in "gettime()" ms."))
test(9, 10, [gpf, trialDivision, factorblind, scattergun, mahbelDoubleExtended, mahbelExtended, mahbel])
Here are the results so far. I've substituted the names for easier reading. Note that all methods get exactly the same numbers to factor.

PARI's internal algorithms factored 10 9-digit numbers in 0 ms.
Trial division factored 10 9-digit numbers in 4 ms.
Guessing random factors (factorblind) factored 10 9-digit numbers in 52 ms.
Searching nearby squares and nonsquares (Dr Sardonicus's scattergun) factored 10 9-digit numbers in 120 ms.
Searching squares, nonsquares, and their combinations (mahbel's double extended method) factored 10 9-digit numbers in 12677 ms.
Searching squares and nonsquares (mahbel's extended method) factored 10 9-digit numbers in 94905 ms.
Searching squares (mahbel's method) factored 10 9-digit numbers in 268852 ms.

So, the takeaways:
  • These numbers are really small. I wasn't able to go much higher because the methods were too slow.
  • Overhead matters a lot. My stupid method is twice as fast as Dr Sardonicus's stupid method just because mine does less work and so it spends more time searching.
  • Contrary to my expectations, the extensions helped a lot. I think that's because the algorithm I'm using for four-square representations is slow and the more checks you do inside of each one you find, the better (because each one is expensive to find).
  • It should surprise no one that all methods were much slower than trial division, which is much slower than a real method.
CRGreathouse is offline   Reply With Quote
Old 2017-06-25, 06:18   #160
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2×23×137 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
In fairness I mentioned this on page 3 and showed how much faster it was.
Okay, sorry. I didn't mean to ignore any particular poster. I haven't been following this thread all that closely though so it is just my inattention, not any malicious intent.
retina is offline   Reply With Quote
Old 2017-06-25, 06:22   #161
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

175B16 Posts
Default

Quote:
Originally Posted by retina View Post
Okay, sorry. I didn't mean to ignore any particular poster. I haven't been following this thread all that closely though so it is just my inattention, not any malicious intent.
Oh, no offense taken at all -- just a pointer if you were interested.

I freely admit, as I have each time performance was mentioned, that the comparison would look less bad if I had a faster method for finding four-square representations. But I think that even if they were already in the L1 cache the speed would be inferior to a properly-coded trial division, let alone Pollard rho.
CRGreathouse is offline   Reply With Quote
Old 2017-06-25, 07:04   #162
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

24·613 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
Here's another question: What's the theoretical justification for requiring that the four squares add up exactly to N? The reason I ask is, I thought of a way to speed up the process of using 4-tuples (a, b, c, d) to find factors of N: simply drop the requirement that

a^2 + b^2 + c^2 + d^2 = N exactly.

As long as a^2 + b^2 + c^2 + d^2 is close to N, go ahead and form the sums of some or all of a, b, c, d, a^2, b^2, c^2, and d^2, and take the gcd with N. (There are 127 nonempty sums.)
haha, brilliant! Very good posting.
I still don't understand why you say "close to N", any sum will do it

(edit whoops, Serge was faster, as usual...)

Last fiddled with by LaurV on 2017-06-25 at 07:06
LaurV is offline   Reply With Quote
Old 2017-06-25, 13:07   #163
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

512510 Posts
Default

Quote:
Originally Posted by Batalov View Post
And yet the next enhancement (because now the a^2 + b^2 + c^2 + d^2 can be equal to anything) is to restate: "Take any random a, b, c, d of size of sqrt(N), then do gcd(N, all linear combinations of {a, b, c, d and a^2, b^2, c^2, d^2} ). Repeat N times if needed. I guarantee that you will factor N." Scout's honor! In fact you will factor N faster, because you will not be uselessly check if a^2 + b^2 + c^2 + d^2 is equal (or close) to N.
I agree, this would be faster. My only real concern was that a, b, c, d not be too small, and your condition sees to that.

It might even give the checking of random numbers up to sqrt(N) a run for its money
Dr Sardonicus is offline   Reply With Quote
Old 2017-06-25, 15:58   #164
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·1,087 Posts
Default

Finding a geometric solution to forming a rectangle out of any given 4 squares is possible in the classical sense of using a compass and a straight-edge.
It's algebraic equivalent its:

x = (a^2 + b^2 + c^2 + d^2) / m

x is a constructible number. However it does not have to be an integer for integers a,b,c,d,m.
So it cannot be a basis for factorization without other constraints which ensue integer-ness.

https://en.m.wikipedia.org/wiki/Constructible_number

ETA
Quote:
Such a number is constructible if and only if the denominator of the fully reduced multiple is a power of 2 or the product of a power of 2 with the product of one or more distinct Fermat primes.
So if I'm not mistaking if m.x happens to have any factors of combinations of Fermat primes (skipping powers of 2), there should be a geometric solution. Very narrow set, however wider sets would not be impossible. However the only ones I can think of are equivalent to Factorials and GCD which are way too complicated to be practical.

Last fiddled with by a1call on 2017-06-25 at 16:34
a1call is offline   Reply With Quote
Old 2017-06-25, 18:02   #165
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by a1call View Post
Finding a geometric solution to forming a rectangle out of any given 4 squares is possible in the classical sense of using a compass and a straight-edge.
It's algebraic equivalent its:

x = (a^2 + b^2 + c^2 + d^2) / m

x is a constructible number. However it does not have to be an integer for integers a,b,c,d,m.
So it cannot be a basis for factorization without other constraints which ensue integer-ness.
I don't know what m is or why it is needed. But couldn't you just scale the grid by a factor of m and use smaller squares?
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A Sierpinski/Riesel-like problem sweety439 sweety439 1250 2021-10-01 12:53
Another factoring method rides the bus 3.14159 Factoring 233 2011-05-15 18:50
Square numbers and binary representation ET_ Miscellaneous Math 40 2010-06-06 12:55
Is this a feasible factoring method? 1260 Miscellaneous Math 46 2010-05-31 17:37
Representation of integer as sum of squares kpatsak Math 4 2007-10-29 17:53

All times are UTC. The time now is 10:26.


Wed Dec 1 10:26:46 UTC 2021 up 131 days, 4:55, 1 user, load averages: 1.00, 1.12, 1.14

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.