Ask Your Question
0

factor with a bound

asked 2013-06-25 03:29:04 +0100

anonymous user

Anonymous

Hi,

I need to find relatively small prime factors of some big numbers. How do I make factor command working with a bound? For instance let's say I am just interested in prime divisors less than 20 and I want to factor 11891. The answer I want would be 11*1081.

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
0

answered 2013-06-25 03:48:32 +0100

vdelecroix gravatar image

You can implement a small function

def factorize_small_primes(N,bound):
    res = []                  # list of pairs (prime,multiplicity)
    for p in Primes():
        if p >= bound:
            break
        k = N.valuation(p)    # the nb k such that p^k || N
        res.append((p,k))
        N /= p^k
    return Factorization(res + [(N,1)])

And use it as follows

sage: N = 2^3 * 13^5 * 523^2 * 541^3
sage: f = factorize_small_primes(N,20)
sage: f
2^3 * 13^5 * 43310697015709

You can also check that the answer is somewaht consistent

sage: f.expand() == N
True
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2013-06-25 03:29:04 +0100

Seen: 433 times

Last updated: Jun 25 '13