Browse Groups

• ## The multi-polynomial part of the multi-polynomial quadratic sieve.

(1)
• NextPrevious
• The multi-polynomial part of the multi-polynomial quadratic sieve. Hello Prime number friends. I ve worked out this part of the multiple polynomial quadratic
Message 1 of 1 , Dec 24 11:41 AM
View Source
The multi-polynomial part of the multi-polynomial quadratic sieve.

Hello Prime number friends.

I've worked out this part of the multiple

I still have not figured out the sieve part.

Let z be the positive integer to be factored.

Choose integer r, and integer k.

Find a,b,c such that

a * r**2 + b * r + c = k * z

a = int( (k * z)/ r**2 )

b = int( (k * z - a * r**2)/r )

c = k*z - a * r**2 - b * r

a * r**2 + b * r + c = 0 mod z

Derive the discriminant equation as follows.

a * r**2 + b * r + c = 0

Multiply equation by a.

a**2 * r**2 + a * b * r + a * c = 0

( a * r)**2 + b * (a * r) + (a * c ) = 0

( a * r + b/2)**2 - (b/2)**2 + (a * c) = 0

(a * r + b/2)**2 = (b/2)**2 - (a * c)

The above equation will be referred to as the
discriminant equation.

Choose integers t2, t1

a * r**2 + b * r + c = k * z

(a + t2) * r**2 + ( b - t2 * r + t1) * r + ( c - t1 * r) = k * z

Applying the discriminant equation, we get

[ (a + t2) * r + ( b - t2 * r + t1 ) / 2 ] **2
= ( b - t2 * r + t1)**2 / 4 - (a + t2)*(c - t1 * r) mod z

For each different values of t2, t1, we get a different
square mod z, with known square root.

Let A = a + t2
Let B = b - t2 * r + t1
Let C = c - t1 * r

Then we can calculate B**2/4 - A * C
more efficiently by using the algebraic identity

(B - 2*t*A)**2/4 - A * ( (A * t - B ) * t + C)
= (B**2 - 4 * A * B * t +4* t**2 * A**2)/4
- (A**2 * t**2 - A * B * t + A * C)

= (B**2 / 4 - A*B*t + t**2 * A**2)
- (A*C - A*B*t + t**2 * A**2)

= B**2/4 - A * C

To choose t, we find the value of t which minimizes

( b - t2 * (r-t) + t1)**2 + ((a + t2)* ( c - t1 * (r-t)))**2

That is, we choose for t, the integer value closest to the
t solution of

t2*( b - t2 * (r-t) + t1)+(a + t2)**2 * t1 * ( c - t1 * (r-t))=0

The puzzle now is how to use sieve technique
on t1 and t2 to find known factored values
of
( b - t2 * r + t1)**2 / 4 - (a + t2)*(c - t1 * r) mod z

so as to build the factors that multiply to an
actual integer square.
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.