What are some efficient algorithms for factoring an integer when the (short~) list of primes appearing in the factorisation is known?

Question

I'm not strictly a beginner programmer, but I have no formal education outside of mathematics - so this is purely hobbyistic and potentially amateurish.

I recently developed an algorithm for the problem myself, but I'm wondering if there are any relatively simple algorithms which are notably more efficient/faster?

A very rough description of the strategy is a comparison to what you might use if someone asks you to determine what number they're thinking of, between 1 and 100: Is it greater than 50? "Yes". Is it greater than 75? "No". Is it greater than 62.5? "Yes". Is it greater than 68.75? etc. You halve the range of values containing the answer each time until you get to the answer.

(Commented) algorithm follows (in python):

import math

#### <parameters>

z = (2**28)*(3**45)*(5**21)*(7**22)*(11**41) # (example) number to factor

Pl = [2, 3, 5, 7, 11] # list of primes in fatorisation (in order)

#### </parameters>

def a(z1, k1, p1): # roughly: gives the maximum possible power of p1 (in factorisation of z1), divided by 2^(k1)
    return int(round(math.log(z1, p1)/2**k1, 0))

Fact = [] # this will be the list of powers of the primes in Pl

for i in range(len(Pl)-1):
    p = Pl[i]
    b = a(z, 1, p)
    k = 2
    while a(z, k, p) != 0:
        if z % (p**b) == 0:
            b += a(z, k, p)
        else:
            b -= a(z, k, p)
        k += 1
    if z % (p**b) != 0: # the above while loop narrows down to two possible values, this narrows down between those two
        b -= 1
    Fact.append(b)
    z = z/(p**b)
Fact.append(int(round(math.log(z, Pl[-1]), 0)))

print(Fact)

Also, I have little to no idea how to go about finding a "Big O" expression for the above. It's not the core of this question, I'm just curious as to what it would be if anyone cares to figure it out.

Answer 1

This is known as Binary Search, it's a very well known algorithm that you can find all sorts of documentation on.

It has a big-O complexity of O(log N).