How to find the largest possible odd factor of a number

Question

I'm writing a script to crack small RSA keys. I've thought of a way to save massive amounts of time in the methods I'm using. To do this, I need to know how to find the largest possible prime factor of a number, of a certain size. For example:

N = 9868690954602957859
N_MAX_FACTOR_BITSIZE = 64

Then, I run N through this algorithm:

p = floor(sqrt(n))
if p mod 2 == 0:
    p += 1
while p < N:  # Referenced above
    if p mod n == 0:
        return p
    p += 2

This algorithm works on the principle that there are only two prime numbers above floor(sqrt(N)) that will divide N evenly. Seeing as both numbers will be prime, the algorithm only checks odd numbers.

To shorten the amount of time this algorithm takes, I would like to swap the N in while p < N with the largest odd 64 bit number that could multiply into N.

EG an algorithim that takes N and N_MAX_FACTOR_BITSIZE as arguments and returns the largest odd factor of N that is N_MAX_FACTOR_BITSIZE long.

The number it returns must be N_MAX_FACTOR_BITSIZE bits long.

Any help would be appreciated.

Answer 1

def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        d = d + 1

    return factors

n = 9868690954602957859

primes =prime_factors(n)[-1]

print(primes)