Jump to content
  • Advertisement
Sign in to follow this  
Nice Coder

Integer factorization, the fast way?

This topic is 5130 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Ok, i've been building a small integer factorizer. It is currenly very slow. It takes 2.8 seconds to factorize 102,812,541,257 into 53 * 6,199 * 312,931. It is currently using a few things, First, it checks the common divisors (2,3,5,7 and 11). if it is divisible by those, then it has the factors almost instantly. Then it sqrt's the number. if it is < 200 then it does a trial division search (all numbers < 200, takes < 1 second) And finally, if it is > 200, then it uses a modified sieve of Eratosthenes. Basically, it checks n. if n isn't a factor, then 2n, 3n, 4n, 5n, on. will not be a factor, so you can rule them off your list. It is quite slow for big numbers, but spends most of its time removing all the common factors (2, 3, 5,7 and 11) and i don't know how to get rid of them beforehand. My question is: What is a method, which is faster then my sieve, and which is not too hard (without explanation, some things i just don't understand yet...), to understand or code. From, Nice coder

Share this post


Link to post
Share on other sites
Advertisement
That is actually the sieve of Eratosthenese[edit can't spell]..;)

To make it as fast as possible, implement an Extended Euclidean Algorithm. That is about as fast as you'll find. It's also what is used for a vast majority of encryption/decryption techniques, so you know it is fast.

You will have to adapt it to your situation, though.

Here's a link for javascript implementation:
http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

Here's a link with a more algorithmic-orientation:
http://www-math.cudenver.edu/~wcherowi/courses/m5410/exeucalg.html

Hope this helps ya.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by Alex Swinney
That is actually the sieve of Eratosthenese[edit can't spell]..;)

To make it as fast as possible, implement an Extended Euclidean Algorithm. That is about as fast as you'll find. It's also what is used for a vast majority of encryption/decryption techniques, so you know it is fast.

You will have to adapt it to your situation, though.

Here's a link for javascript implementation:
http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

Here's a link with a more algorithmic-orientation:
http://www-math.cudenver.edu/~wcherowi/courses/m5410/exeucalg.html

Hope this helps ya.


Thanks, it does help me a bit :)

I'm limited to 100 trillion (15 digits before vb stuffs up the numbering system.) so, any algorith which isn't too slow should work.

What i was wondering about, tho is how to use that to get the factors...

I also wouldn't mind dumping the seive, for something a bit more elegent (my sieve is a little hacky... well, maybe more then a little).

From,
Nice coder

Share this post


Link to post
Share on other sites
You can get rid of them by taking their product and checking +/-1 and +/- all the primes greater than the highest prime in the product and less than half the product. To eliminate all multiples of the first five primes takes a list of 184 primes. So for example say your product was 2 then you check 2n+1, for 2*3 you check 6n+/-1, for 2*3*5 you check 30n+/-{1,7,11,13}, for 2*3*5*7 you check 210n+/-{1,11,13,...,97,101,103).

Share this post


Link to post
Share on other sites
Quote:
Original post by LilBudyWizer
You can get rid of them by taking their product and checking +/-1 and +/- all the primes greater than the highest prime in the product and less than half the product. To eliminate all multiples of the first five primes takes a list of 184 primes. So for example say your product was 2 then you check 2n+1, for 2*3 you check 6n+/-1, for 2*3*5 you check 30n+/-{1,7,11,13}, for 2*3*5*7 you check 210n+/-{1,11,13,...,97,101,103).


Thank you!

Now if only i could find a way to implement one of the faster approaches... (so that i wouldn' need to do this at all)

From,
Nice coder



Share this post


Link to post
Share on other sites
This should do the trick.

#include <stdlib.h>
#include <iostream.h>

int main()
{

__int64 number, j, k;
short int again;

system("cls");
cout << "\n\n\t\t\t Prime Finder\n\n";
cout << "\n\n\t\t\t By: Jared Stewart.\n\n\n\n\n\t\t ";
system("PAUSE");
system("cls");

do
{
system("cls");
cout << "Please enter a number to get the prime factors: ";

cin >> number;

j = 2;

system("cls");
cout << "The prime factors are: ";

do
{
if (number == 2)
break;

if (number % j == 0 ) //check if its a factor
{
cout << j << " ";
number = number/j; //make the number to check smaller
}
else
j++;
} while (j < 3);

for (j =3; j <= sqrt(number); )

{

if (number % j == 0 ) //check if its a factor
{
cout << j << " ";
number = number/j; //make the number to check smaller
}
else
j+=2;
}

cout << number;
cout << "\n\n";
cout << "To test a new number, press 1. To quit, press 2.\n\n\n";
cin >> again;
} while (again ==1);
}

Share this post


Link to post
Share on other sites
Quote:
Original post by Jareds411
This should do the trick.


Trial division,
very slow!

ok, i got rid of my sieve (its slower then trial division!).

And i replaced it with very simple trial division


Dim sn As Double
Dim i As Double
Dim j As Double
Dim fin As Double
Dim t As Double
Dim k As Double
Dim out(1) As Double
sn = Int(Sqr(n)) + 1
fin = Int(sn / 2) + 1
i = 12
j = sn + 1
Do
j = j - 1
i = i + 1
k = number / i
t = number / j
If Int(k) = k Then
out(0) = k
out(1) = i
factorize = out
Exit Function
End If
If Int(t) = t Then
out(0) = t
out(1) = j
factorize = out
Exit Function
End If
DoEvents
Loop Until j < fin
out(0) = 1
out(1) = number
factorize = out


Very simple, not very effective (but it still finds factors that are close to 13 and close to sqr(n), quite fast.

Is there any faster way?
From,
Nice coder

Share this post


Link to post
Share on other sites
!!!!!

Thats a little... (ok way) over my head.

Ok, Now a few question about that link...

First, what is p?

Second, How Do you solve the congruencies on the factor base?

What is Dixons factorization?
What is Gausian elemination?

The quadratic prime sieve is nice...
But the factorization sieve is very complicated.

From,
Nice coder

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!