Prime Factors !!!!!!
Moderator: Board moderators

 Experienced poster
 Posts: 202
 Joined: Fri Mar 22, 2002 2:00 am
 Location: Chittagong. CSE  CUET
 Contact:
Prime Factors !!!!!!
Can anyone send me the fastest code for generating prime factors of integers?
We are all in a circular way, no advances, only moving and moving!

 Learning poster
 Posts: 60
 Joined: Tue Aug 13, 2002 2:39 am
 Location: Mexico
Interested too.
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
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
Miguel & Marina
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
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
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
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 machinelike 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 Pollardrho algorithm or Fermat's method usually work well, both with an expected running time of O(N^(1/4)). I think Pollardrho has a much better constant factor.
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 Pollardrho algorithm or Fermat's method usually work well, both with an expected running time of O(N^(1/4)). I think Pollardrho has a much better constant factor.

 Experienced poster
 Posts: 202
 Joined: Fri Mar 22, 2002 2:00 am
 Location: Chittagong. CSE  CUET
 Contact:
Can you give me any ref. site for these algorithms or any good C/C++ codes ???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 Pollardrho algorithm or Fermat's method usually work well, both with an expected running time of O(N^(1/4)). I think Pollardrho has a much better constant factor.
We are all in a circular way, no advances, only moving and moving!
Pollardrho 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 Pollardrho algrithm (in almostC)
[c]x = y = uniformly chosen random number in 0..N1;
d = 1;
while (d == 1) {
x = f(x);
y = f(f(y));
d = gcd(y  x, N);
}
[/c]
When the whileloop terminates, d will be a nontrivial factor of N. Of course, if there are no trivial factors, the whileloop will never terminate, so you probably want to check that N is not prime first.
Let f(x)=x^2+1 (mod N). Here is the Pollardrho algrithm (in almostC)
[c]x = y = uniformly chosen random number in 0..N1;
d = 1;
while (d == 1) {
x = f(x);
y = f(f(y));
d = gcd(y  x, N);
}
[/c]
When the whileloop terminates, d will be a nontrivial factor of N. Of course, if there are no trivial factors, the whileloop 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 n1 and doing similar spsp tests.
2. Move on to some other methods:
a/ pollards rho method (sequence method).
b/ pollards n1 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 0817637435
3764337435
published by Birkhauser
also quite good is
Ribenboim: The little book of big primes
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 n1 and doing similar spsp tests.
2. Move on to some other methods:
a/ pollards rho method (sequence method).
b/ pollards n1 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 0817637435
3764337435
published by Birkhauser
also quite good is
Ribenboim: The little book of big primes
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
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