MATLAB Answers

0

Factorization

Asked by Mohsin Shah on 20 May 2011
Howto find factors of 2^1024 and 2^2048 in Matlab??

  1 Comment

John D'Errico
on 20 May 2011
Do you wish to know all of the factors, or all the divisors?

Sign in to comment.

5 Answers

Daniel Shub
Answer by Daniel Shub
on 20 May 2011

repmat(factor(2), 1, 1024)

  5 Comments

Walter Roberson
on 20 May 2011
That calculation takes a non-trivial amount of time...
Sean de Wolski
on 20 May 2011
And with the world ending in just a few hours ;-)
Andrew Newell
on 20 May 2011
Oh, no! So little time left to answer questions!

Sign in to comment.


Walter Roberson
Answer by Walter Roberson
on 20 May 2011

With some difficulty, seeing that both numbers are larger than any number that can be directly represented in MATLAB except by using the Fixed Point Toolbox or the Symbolic Toolbox.

  0 Comments

Sign in to comment.


John D'Errico
Answer by John D'Errico
on 20 May 2011

No problem. Just use a tool designed to solve the problem.
>> factor(vpi(2)^1024)
ans =
Columns 1 through 16
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
Columns 17 through 32
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
Columns 33 through 48
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
...
And so on for all 1024 factors of the number.

  0 Comments

Sign in to comment.


Andy
Answer by Andy
on 20 May 2011

For any prime p and positive integer n, the factors of p^n are all of the form p^k for 0 <= k <= n. So the factors of 2^1024 are just 2^k for 0 <= k <= 1024, and similarly for 2^2048. No need to use MATLAB.

  2 Comments

Walter Roberson
on 20 May 2011
But those numbers are not necessarily directly representable in MATLAB, especially if p is not a power of 2.
Andy
on 20 May 2011
That's true. But the OP was unclear as to whether he wanted to represent the factors of these numbers in MATLAB, or whether he simply wanted to solve this problem (and thought of MATLAB as a tool for solving it). Since all of the other answers were of the first sort, I thought I'd throw in an answer of the second sort.

Sign in to comment.


Andrew Newell
Answer by Andrew Newell
on 20 May 2011

The Symbolic Toolbox has a really nice way of handling this:
two = sym(2);
factor(two^1024)
ans =
2^1024

  2 Comments

Walter Roberson
on 20 May 2011
factor() for the symbolic toolbox does algebraic factoring and does not touch numbers.
I do not know at the moment how to produce factors in MuPad; in Maple it would be by using ifactor() or numtheory[divisors]() or one of the related numtheory package members.
Walter Roberson
on 21 May 2011
In Maple,
numtheory[divisors](2^512-5) %a smaller problem
yields an error,
Error, (in ifactor/QuadraticSieve) object too large
It thus seems unlikely that Maple would be able to factor 2^2048-5 using the built-in routines.

Sign in to comment.