sidef-scripts/Math/is_smooth_over_product.sf

#!/usr/bin/ruby

# Author: Daniel "Trizen" Șuteu
# Date: 25 October 2018
# https://github.com/trizen

# A new algorithm for testing N for B-smoothness, given the product of a subset of primes <= B.
# Returns a true value when N is the product of a subset of powers of prime factors of B.
# This algorithm can be useful in some modern integer factorization algorithms.

# 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 >= 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.

func is_smooth_over_prod(n, k) {

    return true  if (n == 1)
    return false if (n <= 0)

    for (var g = gcd(n,k); g > 1; g = gcd(n,g)) {
        n.remdiv!(g)                # remove any divisibility by g
        return true if (n == 1)     # smooth if n == 1
    }

    return false
}

# Example for checking 19-smooth numbers
var k = 19.primorial      # product of primes <= 19

for n in (1..1000) {
    say (n, ' = ', n.factor) if is_smooth_over_prod(n, k)
}