Archived

This topic is now archived and is closed to further replies.

Khaos

Factoring integers

Recommended Posts

After lots and lots of thinking, I still cannot correctly code a program to factor integers into its prime products. My program correctly factors 100 (2,2,5,5) and 6 (2,3) and a few others. But it does not factor 16 (it says 2,2) or 4 (it says 2) and others like 81 (it says 3,9) and 32, and 40, etc. I''ve been over this many a times. Is there some pseudocode that describes the algorithm for breaking down integers into prime factors (fast and efficiently)? Thank you!

Share this post


Link to post
Share on other sites

A. Find lowest factor of int starting at 2. If none, END, otherwise continue.
B. If factor is prime, print/save it and goto: D, otherwise continue.
C: Find next lowest factor of int. goto: B
D: Divide your int by the prime factor, goto: A


Something like that would be pretty simple.

Share this post


Link to post
Share on other sites
Factoring is NP-complete, which is relevant to you in that one can be fairly certain that it has to be done in exponential time or above. What I do is square root the number to get the maximum value of any prime factor. Then take all the primes under this square root, find the first one that divides it exactly and then divide your number by this and repeat on your new number, until you get 1 as your new number.

Share this post


Link to post
Share on other sites
quote:
Original post by furby100
Factoring is NP-complete, which is relevant to you in that one can be fairly certain that it has to be done in exponential time or above. What I do is square root the number to get the maximum value of any prime factor. Then take all the primes under this square root, find the first one that divides it exactly and then divide your number by this and repeat on your new number, until you get 1 as your new number.

I''m skeptical, too.

Some Indian guys discovered a algorithm for factoring integers efficiently (in polynomial time). Unfortunately, I can''t find the article right now (am at school). I have it at home and will post it soon. If factoring was NP-complete, wouldn''t they get the $1 million for proving P=NP?

Share this post


Link to post
Share on other sites
quote:
Original post by GaulerTheGoat
Some Indian guys discovered a algorithm for factoring integers efficiently (in polynomial time).


Nope. What was recently proved is that primality testing can be done in polynomial time.

quote:
If factoring was NP-complete, wouldn''t they get the $1 million for proving P=NP?

If factoring were NP-complete and they have an algorithm that factors in polynomial time, yes. The former is not known and the latter is false.

Please, stop posting if you don''t know what you are talking about.

Share this post


Link to post
Share on other sites
Just to clear something up, factoring a number 100% is NOT NP-Complete, NP-Complete problems refer to problems that involve a yes/no decision (ie. primality testing). It might be NP-Hard which involves non-decision problems, but I don''t know if that has been proven/disproven yet.

Share this post


Link to post
Share on other sites
quote:
Original post by alvaro
Nope. What was recently proved is that primality testing can be done in polynomial time.

You're right. Homepage of Manindra Agrawal if anybody wants to check it out.

quote:
Original post by alvaro
Please, stop posting if you don't know what you are talking about.

I've been a little lazy lately on checking my facts before I post them. I could use a reminder to do better every once in a while. I've posted a lot of good stuff here, too though, so I hope you're not talking about my record in general.

[edited by - GaulerTheGoat on October 9, 2003 8:37:25 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by GaulerTheGoat
I''ve posted a lot of good stuff here, too though, so I hope you''re not talking about my record in general.



No, I was talking about this particular thread. I''m sorry if I sounded two harsh.

Share this post


Link to post
Share on other sites
quote:
Original post by alvaro
Please, stop posting if you don't know what you are talking about.


Aww, you hurted my feelings. That's just one sentence at the top of my post.

[edited by - furby100 on October 11, 2003 4:25:36 PM]

Share this post


Link to post
Share on other sites
>>Actually, you CAN factor in polynomial time...
>>...you just >>need a quantum computer.

Aren''t quantum computers somewhat stochastic (ie. have a source of indefinity in them)? If that''s the case, these algorithms aren''t too much of joy (though you can test if the candidate, possibly erroreous, factors are the real factors by just multiplying them or by doing a modulo operation).

- Mikko Kauppila

Share this post


Link to post
Share on other sites
In theory, no. However because of their quantum nature, it is hard to isolate the computer from the rest of the world, resulting in imprecissions creeping in. This happens to some extent in "normal" computers too, however it''s much less pronounced. Some work is being done on both error-correction for quantum computers and improving the isolation/tolorence of quantum computers, however we''re still quite a few years from getting a workable quantum computer, from what I''ve heard.

The best a quantum computer has done so far, IIRC, is factor 15 into 5 and 3 -- and (also from what I''ve heard, although from a different source) is that the technology used to do this can''t be easily extended to much larger numbers.

Share this post


Link to post
Share on other sites
The goal of quantum computers is to be able to run some non-deterministic alorithms.
Since NP-hard problems are in P for non-deterministic computers, a full blown quantum computer should be able to solve problems in NP.
Quantum computers are not turing machines, so their associated complexity theory is different from the one we usually consider.

I don''t know the state of the art of quantum computing, but it coming to reality will be a MAJOR breakthrough in science (just like quantum theory was). This is going to be interesting...

Share this post


Link to post
Share on other sites
quote:
Original post by Garfong
Oh, and I think quantum computers can also solve NP-complete problems in polynomial time... I''m not completely sure, but pretty sure...


Yes, they are Non-deterministic machines. And NP state for Nondeterminisctic Polynomial, so...


Share this post


Link to post
Share on other sites