Prev: Is There a Canonical Way of Giving a Complex n-Manifold a real 2n-str
Next: unknown Taylor series
From: Phil Bewig on 9 Aug 2010 23:00
I am trying to implement Shanks' SQUFOF algorithm for integer
factorization as defined in a paper by Gower and Wagstaff
(homes.cerias.purdue.edu/~ssw/squfof.pdf), Section 3.6. Here, F(A, B,
C) and G(A, B, C) are quadratic forms Ax^2 + Bxy + Cy^2.

SQUFOF:

1. Initialize:
Read the odd positive integer N to be factored. If N is the square of
an integer, output the square root and stop. If N == 1 mod 4, then
set D = N, m = 1, d = floor(sqrt(D)), and b = 2 * floor((d-1) / 2) +
1. Otherwise (N == 2 or 3 mod 4), set D = 4*N, m = 2, d =
floor(sqrt(D)), and b = 2 * floor(d / 2). Let F = (1, b, (b^2 - D) /
4), i = 2, L = floor(sqrt(d)), and Bound = 4 * L. Create an empty
list. Let g = |(b^2 - D) / 4| / gcd(|(b^2 - D) / 4|, m). If g <= L,
add g to the list.

2. Cycle forward to find a proper square form:
2a: Set F = (A, B, C) = rho(F), where rho was defined in 2.1.2.
2b: If i is even, go to Step 2d. If C is the square of an integer,
let c > 0 be a square root. If c is not in the list, go to Step 3.
If c = 1, stop because the algorithm has gone through the entire
principal period without finding a proper square form.
2c: Let g = |C| / gcd(|C|, m). If g <= L, add g to the list.
2d: Let i = i + 1. If i > Bound, give up. Otherwise, go to Step 2a.

3. Compute an inverse square root of the square form:
Set G = (a, b, c) = rho((cA, -B, -C)).

4. Cycle in the reverse direction to find a factor of N:
4a. Set b' = b and G = (a, b, c) = rho(G).
4b. If b = b', then go to Step 5, else go to Step 4a.

5. Print the factor of N:
If c is even, let c = c / 2. Output |c| as a non-trivial factor of N.

Section 2.1.2 defines the reduction operator rho on indefinite
quadratic forms with positive discriminants -- that is, delta(a,b,c) =
b^2-4ac -- as follows:

For any indefinite form f(a, b, c) with ac != 0 we define the standard
reduction operator by [if the formatting gets messed up, the reduced
form is c, r(-b,c), and the fraction r(-b,c) squared - delta over 4c]

r(-b,c)^2 - delta
rho(a, b, c) = c, r(-b,c), -----------------
4c

where r(-b, c) is defined to be the unique integer r such that r + b
== 0 mod 2c and

-|c| < r <= |c| if sqrt(delta) < |c|,
sqrt(delta) - 2|c| < r < sqrt(delta) if |c| < sqrt(delta)

I am working an example by hand prior to implementing a program to
perform the calculation, but I am having trouble. I have taken as an
example N = 991 * 997 = 988027. N is an odd positive integer and is
not the square of an integer. N == 3 mod 4 so I set D = 4 * N =
3952108, m = 2, d = floor(sqrt(3952108)) = 1987, and b = 2 *
floor(1987 / 2) = 1986. Then F is the quadratic form (1, 1986,
(1986^2 - 3952108) / 4) = (1, 1986, -1978), i = 2, L =
floor(sqrt(1987)) = 44 and Bound = 4 * 44 = 176. Then g = |(1986^2 -
3952108) / 4| / gcd(|(1986^2 - 3952108) / 4|, 2) = 1978 / gcd(1978, 2)
= 989 and the list is empty.

The next step, 2a, computes the reduction of (1, 1986, -1978) using
the rho operator. I first compute r = 1986 mod (2 * -1978) = -1970.
Then, with delta = 1986^2-4*1*-1978 = 3944196 - -7912 = 3952108 and
sqrt(delta) = 1987.99, which is greater than |-1978|, I need
sqrt(delta) - 2*|c| < r < sqrt(delta), thus 1987.99 - 2*|-1978| < r <
1987.99, thus -1968.01 < r < 1987.99, r is less than -1968.01, so I
add r = -1970 - 2 * -1978 to get a final value of r = 1986. Thus, the
reduction of (1, 1986, -1978) is (-1978, 1986, 1), since (1986^2 -
3952108) / 4*-7912 = 1.

Now that we have the reduced form of F, we go back to Step 2b. Since
i = 2 is even, we go to Step 2d, set i = 3, and go back to Step 2a to
reduce F again. But without bothering to show the calculation, the
reduction of F = (-1978, 1986, 1) is just (1, 1986, -1978), so we are
back where we started. The SQUFOF algorithm cycles uselessly until i
reaches Bound, when it quits.

Can someone please tell me what I have done wrong?

Many thanks,

Phil
From: Gerry Myerson on 9 Aug 2010 23:55
In article
<0703d784-59d7-4e78-b76b-a624b22ad225(a)w30g2000yqw.googlegroups.com>,
Phil Bewig <pbewig(a)gmail.com> wrote:

> I am trying to implement Shanks' SQUFOF algorithm for integer
> factorization as defined in a paper by Gower and Wagstaff
> (homes.cerias.purdue.edu/~ssw/squfof.pdf), Section 3.6.

My recollection is that SQUFOF works by going through
the continued fraction for sqrt(n) [which amounts to the same
thing as going through those quadratic forms you write about]
until something good happens and a factorization drops out;
but if the cycle is very short you may get all the way through it
without anything good happening. In other words, if my memory
of SQUFOF is right, it isn't guaranteed to work - there are
composite n for which it will fail. Maybe you've just hit one of them?

--
Gerry Myerson (gerry(a)maths.mq.edi.ai) (i -> u for email)
From: Phil Bewig on 10 Aug 2010 00:04
On Aug 9, 10:55 pm, Gerry Myerson <ge...(a)maths.mq.edi.ai.i2u4email>
wrote:
> In article
> <0703d784-59d7-4e78-b76b-a624b22ad...(a)w30g2000yqw.googlegroups.com>,
>  Phil Bewig <pbe...(a)gmail.com> wrote:
>
> > I am trying to implement Shanks' SQUFOF algorithm for integer
> > factorization as defined in a paper by Gower and Wagstaff
> > (homes.cerias.purdue.edu/~ssw/squfof.pdf), Section 3.6.  
>
> My recollection is that SQUFOF works by going through
> the continued fraction for sqrt(n) [which amounts to the same
> thing as going through those quadratic forms you write about]
> until something good happens and a factorization drops out;
> but if the cycle is very short you may get all the way through it
> without anything good happening. In other words, if my memory
> of SQUFOF is right, it isn't guaranteed to work - there are
> composite n for which it will fail. Maybe you've just hit one of them?
>
> --
> Gerry Myerson (ge...(a)maths.mq.edi.ai) (i -> u for email)

Good suggestion, but my method also fails for N = 633003781, which
is the example in the paper. I'm pretty sure the error is in the
reduction of the quadratic form, but I don't see it.

Thanks,

Phil
From: Colin Barker on 13 Aug 2010 06:44

"Phil Bewig" <pbewig(a)gmail.com> a �crit dans le message de
news:0703d784-59d7-4e78-b76b-a624b22ad225(a)w30g2000yqw.googlegroups.com...
> I am working an example by hand prior to implementing a program to
> perform the calculation, but I am having trouble. I have taken as an
> example N = 991 * 997 = 988027. N is an odd positive integer and is
> not the square of an integer. N == 3 mod 4 so I set D = 4 * N =
> 3952108, m = 2, d = floor(sqrt(3952108)) = 1987, and b = 2 *
> floor(1987 / 2) = 1986. Then F is the quadratic form (1, 1986,
> (1986^2 - 3952108) / 4) = (1, 1986, -1978), i = 2, L =
> floor(sqrt(1987)) = 44 and Bound = 4 * 44 = 176. Then g = |(1986^2 -
> 3952108) / 4| / gcd(|(1986^2 - 3952108) / 4|, 2) = 1978 / gcd(1978, 2)
> = 989 and the list is empty.
>
> The next step, 2a, computes the reduction of (1, 1986, -1978) using
> the rho operator. I first compute r = 1986 mod (2 * -1978) = -1970.
> Then, with delta = 1986^2-4*1*-1978 = 3944196 - -7912 = 3952108 and
> sqrt(delta) = 1987.99, which is greater than |-1978|, I need
> sqrt(delta) - 2*|c| < r < sqrt(delta), thus 1987.99 - 2*|-1978| < r <
> 1987.99, thus -1968.01 < r < 1987.99, r is less than -1968.01, so I
> add r = -1970 - 2 * -1978 to get a final value of r = 1986.

Just an idea...
Shouldn't the final value of r be 1970?
Because c=-1978, 2*c=-3956, b=1986, r+b=3956, (r+b) mod 2c = 0.
I think you used b=-1986.
--
Colin


 | 
Pages: 1
Prev: Is There a Canonical Way of Giving a Complex n-Manifold a real 2n-str
Next: unknown Taylor series