Edit Question - KnowledgeHub

Title Body

I am looking for an implementation or clear algorithm for getting the prime factors of N in either python, pseudocode or anything else well-readable. There are a few requirements/constraints: N is between 1 and ~20 digits No pre-calculated lookup table, memoization is fine though Need not to be mathematically proven (e.g. could rely on the Goldbach conjecture if needed) Need not to be precise, is allowed to be probabilistic/deterministic if needed I need a fast prime factorization algorithm, not only for itself, but for usage in many other algorithms like calculating the Euler phi(n) . I have tried other algorithms from Wikipedia and such but either I couldn't understand them (ECM) or I couldn't create a working implementation from the algorithm (Pollard-Brent). I am really interested in the Pollard-Brent algorithm, so any more information/implementations on it would be really nice. Thanks! EDIT After messing around a little I have created a pretty fast prime/factorization module. It combines an optimized trial division algorithm, the Pollard-Brent algorithm, a miller-rabin primality test and the fastest primesieve I found on the internet. gcd is a regular Euclid's GCD implementation (binary Euclid's GCD is much slower then the regular one). Bounty Oh joy, a bounty can be acquired! But how can I win it? Find an optimization or bug in my module. Provide alternative/better algorithms/implementations. The answer which is the most complete/constructive gets the bounty. And finally the module itself: import random def primesbelow(N): # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188 #""" Input N>=6, Returns a list of primes, 2 <

Tags (comma-separated) Cancel