Factorization

Howto find factors of 2^1024 and 2^2048 in Matlab??

[John D'Errico]

Do you wish to know all of the factors, or all the divisors?

Answer 1

[Daniel Shub]

repmat(factor(2), 1, 1024)

[Sean de Wolski]

Yup!

You could always get the same result with John's VPI:

two = vpi('2')

two =

2

>> two^2048

ans =

323170060713110073007148766886699519604441026697154840321303454275246

551388678908931972014115229134636887179609218980194941195591504909210950

881523864482831206308773673009960917501977503896521067960576383840675682

767922186426197561618380943384761704705816458520363050428875758915410658

086075523991239303855219143333896683424206849747865645694948561760353263

220580778056593310261927084603141502585928641771167259436037184618573575

983511523016459044036976132332872312271256847108202097251571017269313234

696785425806566979350459972683529986382155251663894373355436021354332296

04645318478604952148193555853611059596230656

factor(two^2048)

[Zakir]

how to I find factors of this Value

a = vpi(2);

b = a^2048

c=b-5

then I want to find factors of c.

Although i get the factors but only i get factors less then 32bits?

Why?

[Walter Roberson]

That calculation takes a non-trivial amount of time...

[Sean de Wolski]

And with the world ending in just a few hours ;-)

[Andrew Newell]

Oh, no! So little time left to answer questions!

Answer 2

[Walter Roberson]

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.

Answer 3

[John D'Errico]

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.

Answer 4

[Andy]

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.

[Walter Roberson]

But those numbers are not necessarily directly representable in MATLAB, especially if p is not a power of 2.

[Andy]

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.

Answer 5

[Andrew Newell]

The Symbolic Toolbox has a really nice way of handling this:

two = sym(2);
factor(two^1024)

ans =

2^1024

[Walter Roberson]

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]

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.