OJ Board

Can anyone send me the fastest code for generating prime factors of integers?

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

I have heard about

Eratosthenes method for generating primes.

But I need to get the prime factors of a integer.

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

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.

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

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

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 ]. 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.

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 ]. 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 ???

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.

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

This book is not available in CUET so, if you have any ref. site add. you can give those to me for further study...

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