Mixing
Bad numbers for Pollard-Rho algorithm
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Are there some pattern of "bad" numbers for Pollard-Rho algorithm (e.g., numbers for which the algorithm often fails)?
I read a comment here (https://stackoverflow.com/questions/48196783/does-pollard-rho-not-work-for-certain-numbers) saying "it often fails on even numbers and perfect powers". Is this true?
Also, I notice a lot of implementations check even numbers separately. Are there any mathematical reasons? Or is it just a simple heuristic?
number-theory algorithms factoring
asked Jul 18 at 17:21
Enzo Nakamura
605
add a comment |Â
up vote
1
down vote
favorite
Are there some pattern of "bad" numbers for Pollard-Rho algorithm (e.g., numbers for which the algorithm often fails)?
I read a comment here (https://stackoverflow.com/questions/48196783/does-pollard-rho-not-work-for-certain-numbers) saying "it often fails on even numbers and perfect powers". Is this true?
Also, I notice a lot of implementations check even numbers separately. Are there any mathematical reasons? Or is it just a simple heuristic?
number-theory algorithms factoring
asked Jul 18 at 17:21
Enzo Nakamura
605
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Are there some pattern of "bad" numbers for Pollard-Rho algorithm (e.g., numbers for which the algorithm often fails)?
I read a comment here (https://stackoverflow.com/questions/48196783/does-pollard-rho-not-work-for-certain-numbers) saying "it often fails on even numbers and perfect powers". Is this true?
Also, I notice a lot of implementations check even numbers separately. Are there any mathematical reasons? Or is it just a simple heuristic?
number-theory algorithms factoring
asked Jul 18 at 17:21
Enzo Nakamura
605
Are there some pattern of "bad" numbers for Pollard-Rho algorithm (e.g., numbers for which the algorithm often fails)?
I read a comment here (https://stackoverflow.com/questions/48196783/does-pollard-rho-not-work-for-certain-numbers) saying "it often fails on even numbers and perfect powers". Is this true?
Also, I notice a lot of implementations check even numbers separately. Are there any mathematical reasons? Or is it just a simple heuristic?
number-theory algorithms factoring
asked Jul 18 at 17:21
Enzo Nakamura
605
asked Jul 18 at 17:21
Enzo Nakamura
605
asked Jul 18 at 17:21
Enzo Nakamura
605
asked Jul 18 at 17:21
Enzo Nakamura
605
605
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
5
down vote
accepted
It depends on your choice of polynomial.
You can't extract even factor using Pollard-Rho algorithm because of your choice of $f(x)=x^2+1$. For any integer $x$ then $f(f(x))-f(x)$ is always odd. Indeed, we have $f(f(x))-f(x)=(x^2+1)^2-x^2$ where $x^2+1$ and $x$ have different parity. Say, if you want to take out factor $2$ of $n$, you can choose $f(x)=x^2+2$ (although it's better if you don't use this method but instead removing all factors of $2$ before applying Pollard-Rho).
There are some odd prime factors you cannot find from your choice of polynomial $f(x)=x^2+1$. The algorithm fails to find prime divisor $p$ of $n$ when $p nmid f(f(x))-f(x)$ for any $x$. In particular, this is equivalent to $p nmid [(2x-1)^2+3][(2x+1)^2+3]$. According to Law of quadratic reciprocity, all primes $p$ so $pequiv 5 pmod6$ satisfies this condition. This follows the algorithm fails to factor primes $p equiv 5 pmod6$ out of $n$.
answered Jul 19 at 3:12
Tengu
2,3391920
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
accepted
It depends on your choice of polynomial.
You can't extract even factor using Pollard-Rho algorithm because of your choice of $f(x)=x^2+1$. For any integer $x$ then $f(f(x))-f(x)$ is always odd. Indeed, we have $f(f(x))-f(x)=(x^2+1)^2-x^2$ where $x^2+1$ and $x$ have different parity. Say, if you want to take out factor $2$ of $n$, you can choose $f(x)=x^2+2$ (although it's better if you don't use this method but instead removing all factors of $2$ before applying Pollard-Rho).
There are some odd prime factors you cannot find from your choice of polynomial $f(x)=x^2+1$. The algorithm fails to find prime divisor $p$ of $n$ when $p nmid f(f(x))-f(x)$ for any $x$. In particular, this is equivalent to $p nmid [(2x-1)^2+3][(2x+1)^2+3]$. According to Law of quadratic reciprocity, all primes $p$ so $pequiv 5 pmod6$ satisfies this condition. This follows the algorithm fails to factor primes $p equiv 5 pmod6$ out of $n$.
answered Jul 19 at 3:12
Tengu
2,3391920
add a comment |Â
up vote
5
down vote
accepted
It depends on your choice of polynomial.
You can't extract even factor using Pollard-Rho algorithm because of your choice of $f(x)=x^2+1$. For any integer $x$ then $f(f(x))-f(x)$ is always odd. Indeed, we have $f(f(x))-f(x)=(x^2+1)^2-x^2$ where $x^2+1$ and $x$ have different parity. Say, if you want to take out factor $2$ of $n$, you can choose $f(x)=x^2+2$ (although it's better if you don't use this method but instead removing all factors of $2$ before applying Pollard-Rho).
There are some odd prime factors you cannot find from your choice of polynomial $f(x)=x^2+1$. The algorithm fails to find prime divisor $p$ of $n$ when $p nmid f(f(x))-f(x)$ for any $x$. In particular, this is equivalent to $p nmid [(2x-1)^2+3][(2x+1)^2+3]$. According to Law of quadratic reciprocity, all primes $p$ so $pequiv 5 pmod6$ satisfies this condition. This follows the algorithm fails to factor primes $p equiv 5 pmod6$ out of $n$.
answered Jul 19 at 3:12
Tengu
2,3391920
add a comment |Â
up vote
5
down vote
accepted
up vote
5
down vote
accepted
It depends on your choice of polynomial.
You can't extract even factor using Pollard-Rho algorithm because of your choice of $f(x)=x^2+1$. For any integer $x$ then $f(f(x))-f(x)$ is always odd. Indeed, we have $f(f(x))-f(x)=(x^2+1)^2-x^2$ where $x^2+1$ and $x$ have different parity. Say, if you want to take out factor $2$ of $n$, you can choose $f(x)=x^2+2$ (although it's better if you don't use this method but instead removing all factors of $2$ before applying Pollard-Rho).
There are some odd prime factors you cannot find from your choice of polynomial $f(x)=x^2+1$. The algorithm fails to find prime divisor $p$ of $n$ when $p nmid f(f(x))-f(x)$ for any $x$. In particular, this is equivalent to $p nmid [(2x-1)^2+3][(2x+1)^2+3]$. According to Law of quadratic reciprocity, all primes $p$ so $pequiv 5 pmod6$ satisfies this condition. This follows the algorithm fails to factor primes $p equiv 5 pmod6$ out of $n$.
answered Jul 19 at 3:12
Tengu
2,3391920
It depends on your choice of polynomial.
You can't extract even factor using Pollard-Rho algorithm because of your choice of $f(x)=x^2+1$. For any integer $x$ then $f(f(x))-f(x)$ is always odd. Indeed, we have $f(f(x))-f(x)=(x^2+1)^2-x^2$ where $x^2+1$ and $x$ have different parity. Say, if you want to take out factor $2$ of $n$, you can choose $f(x)=x^2+2$ (although it's better if you don't use this method but instead removing all factors of $2$ before applying Pollard-Rho).
There are some odd prime factors you cannot find from your choice of polynomial $f(x)=x^2+1$. The algorithm fails to find prime divisor $p$ of $n$ when $p nmid f(f(x))-f(x)$ for any $x$. In particular, this is equivalent to $p nmid [(2x-1)^2+3][(2x+1)^2+3]$. According to Law of quadratic reciprocity, all primes $p$ so $pequiv 5 pmod6$ satisfies this condition. This follows the algorithm fails to factor primes $p equiv 5 pmod6$ out of $n$.
answered Jul 19 at 3:12
Tengu
2,3391920
answered Jul 19 at 3:12
Tengu
2,3391920
answered Jul 19 at 3:12
Tengu
2,3391920
answered Jul 19 at 3:12
Tengu
2,3391920
2,3391920
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2855796%2fbad-numbers-for-pollard-rho-algorithm%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password