Prime Factors !!!!!!

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Prime Factors !!!!!!

Post by Moni »

Can anyone send me the fastest code for generating prime factors of integers? :roll:
ImageWe are all in a circular way, no advances, only moving and moving!

Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

Interested too.

Post by Miguel Angel »

The best that i know is
O (sqrt(N) / log (sqrt(N)))
[which is divide with all the primes betwen 1 and sqrt(N)]
I know there'r exist exact methods to find primes of a composite number when it's a product of two distinct primes, such a Pollard Algorithm and they are very fast, but i don't know more :)
:D Miguel & Marina :D

Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Post by Moni »

I have heard about
Eratosthenes method for generating primes.
But I need to get the prime factors of a integer.
ImageWe are all in a circular way, no advances, only moving and moving!

Shahab
New poster
Posts: 24
Joined: Sun Nov 10, 2002 2:17 pm

Post by Shahab »

Hi everybody,

Some monthes ago, I read about factoring integers in quantom computers, and I found a random method of factoring numbers(not only to primes) used in this algorithm, but it wasn't related to quantom computers. The time order of this method was very connected to the number of prime factors of the original number.

I will send you the url if I found that article again.

Sincerely yours,
Shahab Tasharrofi

Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Post by Moni »

Yes, Shahab!
I will like to see that article. But what I need is a good algorithm apart from trivial methods for finding prime factors of an integer.
ImageWe are all in a circular way, no advances, only moving and moving!

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

I believe the best you can do right now is that, otherwise it would destroy crypo right now..

Shahab
New poster
Posts: 24
Joined: Sun Nov 10, 2002 2:17 pm

Post by Shahab »

I found that article,

you can find it at http://www.research.att.com/~shor/papers/QCjournal.ps ,in this paper there is a random method for factoring numbers, and it is not just for quantum computers.

And Larry, you must read it too, i think. Becuase the Peter Shor ( Writer of this article ) claims that this method will destroy the RSA methos of encryption.

You will find more refernces at this paper.

Sincerely yours,
Shahab Tasharrofi

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per »

Shahab, even though the idea used by Shor in his factorization algorithm for quantum computers is not directly related to quantum computing (as it's math!), it is not really possible to implement it efficiently on our common Turing machine-like computers. Shor's paper has been around for almost 10 years, and RSA is still going strong. The largest number they've been able to factor with a quantum computer to this date is 15.

The best known factorization algorithm for our common computers is the number field sieve, which has an expected running time of O(e^( 1.9223 * (ln N)^(1/3) * (ln ln N)^(2/3) )) [yes, it is ugly :wink:]. For "normal" purposes however, the Pollard-rho algorithm or Fermat's method usually work well, both with an expected running time of O(N^(1/4)). I think Pollard-rho has a much better constant factor.

Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Post by Moni »

Per wrote: The best known factorization algorithm for our common computers is the number field sieve, which has an expected running time of O(e^( 1.9223 * (ln N)^(1/3) * (ln ln N)^(2/3) )) [yes, it is ugly :wink:]. For "normal" purposes however, the Pollard-rho algorithm or Fermat's method usually work well, both with an expected running time of O(N^(1/4)). I think Pollard-rho has a much better constant factor.
Can you give me any ref. site for these algorithms or any good C/C++ codes ??? :roll:
ImageWe are all in a circular way, no advances, only moving and moving!

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per »

Pollard-rho is quite simple, though it's very hard to see why it'll give good performance.

Let f(x)=x^2+1 (mod N). Here is the Pollard-rho algrithm (in almost-C)

[c]x = y = uniformly chosen random number in 0..N-1;
d = 1;
while (d == 1) {
x = f(x);
y = f(f(y));
d = gcd(y - x, N);
}
[/c]

When the while-loop terminates, d will be a nontrivial factor of N. Of course, if there are no trivial factors, the while-loop will never terminate, so you probably want to check that N is not prime first.

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum »

To the original poster:

1. Use trial division, if possible to the cube root of the number you are interested in. If not possible then to some easily reached number N. You can now work out how many factors the remainder has at most, assuming it is composite. (To test for compositeness implement some quick psp/spsp tests and then try to prove primality using something more complex like factoring n-1 and doing similar spsp tests.
2. Move on to some other methods:
a/ pollards rho method (sequence method).
b/ pollards n-1 method
c/ lucas sequences (n+1 hopefully)
3. Now move on to something a bit more complicated if you still havent found the factors
a/ squfof
b/ cfrac
c/ quadratic sieve
4/ assuming the factors are now 15 digits plus:
a/ elliptic curve
5/ presumably you now have a difficult factorisation and require more complex algorithms to attack it
a/ mpqs/nfs/gnfs

Of course if your original number had some specific properties, like it is a fibonacci number, or it is a mersenne number then you can take more shortcuts.

For reference:
Hans Riesel: Prime Numbers and Computer Methods for Factorisation. ISBN 0-8176-3743-5
3-7643-3743-5
published by Birkhauser

also quite good is
Ribenboim: The little book of big primes

Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Post by Moni »

This book is not available in CUET so, if you have any ref. site add. you can give those to me for further study... :)
ImageWe are all in a circular way, no advances, only moving and moving!

Shantanu
New poster
Posts: 8
Joined: Sun Oct 20, 2002 6:44 am

Post by Shantanu »

There is a method to find the prime factors and the power risen
by them to produce any number n.
Just see that.

m=summation of(floor(n/(p^i))) where p is a prime and i is 1,2...
until n/(p^i) become 0.

By this way u can find m such that p^m is a factor of n and m is the
highest power raised by p which is a factor of n. And you can
find all the p <= n such as p^m is a factor of n.

i think this may help u if i make u understand what
i am saying, b'cause i often can't make people understand
specially something like this.

u can check Knuth's book for more explanation.

Thanks

Post Reply

Return to “Algorithms”