Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to understand quadratic sieve algorithm and now I am thinking of the way to check if number is smooth over a factor base?
For example, say I have number $n = 87463$.
First,I find bound $B = 43$.
Second, using Tonelli-Shanks algorithm I construct factor base = $\{2, 7, 11, 13, 17, 37, 41\}$.
Third, construct a sieveing interval of length $2 * B = 2 * 43$ around $\lfloor \sqrt{n} \rfloor = 295$:

{251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 291, 292, 293, 294, 295, 296, 297, 298, 299, 300, 301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339}

Now the question is how can efficiently identify smooth numbers in this list over a factor base? Are there any algorithms known for that?
Or can I just go through the list and try to factor our all powers of number in the factor base. In number then becomes 1 - it is smooth and I can use the powers later. Is this approach efficient?

share|improve this question
1  
Been a while since I looked at quadratic sieve, but I think it's not the numbers 251, 252, ... that need to be smooth, it's the numbers $n-251^2,n-252^2,\dots$. Test one of these numbers for divisibility by the primes in the factor base; if $p$ divides $n-k^2$, then it divides $n-(k+tp)^2$ for all $t$. That's the sieve part. –  Gerry Myerson Aug 14 '12 at 13:10
    
Oops! Yes, you are absolutely right! I found Pomerance's paper and now it makes much more sense! Thanks! –  Ypsilon IV Aug 14 '12 at 13:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.