Ask Your Question

factor with a bound

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 close merge delete

1 Answer

Sort by ยป oldest newest most voted

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

more

Your Answer

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

Add Answer

Stats

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

Seen: 288 times

Last updated: Jun 25 '13