[Math] Smooth numbers algorithm

algorithmsnumber theory

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?

Best Answer

Identifying smooth numbers that factor over a constant factor base, can be done efficiently using the following algorithm:

  1. Let $n$ be the number to be tested
  2. Let $k$ be the product of the primes in the factor base
  3. Compute the greatest common divisor: $g = gcd(n, k)$
  4. If $g$ is greater than $1$, then $n = r g^e$, for some $e \ge 1$.
    • If $r = 1$, then $n$ is smooth over the factor base.
    • Otherwise, set $n = r$ and go to step $3$.
  5. If this step is reached, then $n$ is not smooth.
Related Question