Can someone explain to me this part of Dixon's factorization algorithm?

Question

I've been trying to implement Dixon's factorization method in python, and I'm a bit confused. I know that you need to give some bound B and some number N and search for numbers between sqrtN and N whose squares are B-smooth, meaning all their factors are in the set of primes less than or equal to B. My question is, given N of a certain size, what determines B so that the algorithm will produce non-trivial factors of N? Here is a wikipedia article about the algorithm, and if it helps, here is my code for my implementation:

def factor(N, B):
    def isBsmooth(n, b):
        factors = []
        for i in b:
            while n % i == 0:
                n = int(n / i)
                if not i in factors:
                    factors.append(i)
        if n == 1 and factors == b:
            return True
        return False

    factor1 = 1
    while factor1 == 1 or factor1 == N:
        Bsmooth = []
        BsmoothMod = []
        for i in range(int(N ** 0.5), N):
            if len(Bsmooth) < 2 and isBsmooth(i ** 2 % N, B):
                Bsmooth.append(i)
                BsmoothMod.append(i ** 2 % N)
        gcd1 = (Bsmooth[0] * Bsmooth[1]) % N
        gcd2 = int((BsmoothMod[0] * BsmoothMod[1]) ** 0.5)
        factor1 = gcd(gcd1 - gcd2, N)
        factor2 = int(N / factor1)
    return (factor1, factor2)

Maybe someone could help clean my code up a bit, too? It seems very inefficient.

Answer 1

This article discusses the optimal size for B: https://web.archive.org/web/20160205002504/https://vmonaco.com/dixons-algorithm-and-the-quadratic-sieve/. Briefly, the optimal value is thought to be exp((logN loglogN)^(1/2)).