Mixing
Upper bounds on difference of RSA primes
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
I was wondering whether given a concrete $N = p cdot q$ whether we can find a upper bound on $Delta = | p - q|$ as function of $N$ e.g, $N^delta$, and thus test whether a given $N$ is vulnerable to Fermat-Factoring?
rsa factoring number-theory
edited 2 hours ago
SEJPM♦
27.6k451130
asked 4 hours ago
Marc Ilunga
262
add a comment |Â
up vote
3
down vote
favorite
I was wondering whether given a concrete $N = p cdot q$ whether we can find a upper bound on $Delta = | p - q|$ as function of $N$ e.g, $N^delta$, and thus test whether a given $N$ is vulnerable to Fermat-Factoring?
rsa factoring number-theory
edited 2 hours ago
SEJPM♦
27.6k451130
asked 4 hours ago
Marc Ilunga
262
Marc, are trying to say; in case of security, what are the bound of the difference $ a < |p-q| < b$
– kelalaka
4 hours ago
@kelalaka, Yes I am wondering if it is possible to detect unsafe primes for RSA. "IF" it ever happens and in a way that It can be factored using Fermat's method.
– Marc Ilunga
3 hours ago
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
I was wondering whether given a concrete $N = p cdot q$ whether we can find a upper bound on $Delta = | p - q|$ as function of $N$ e.g, $N^delta$, and thus test whether a given $N$ is vulnerable to Fermat-Factoring?
rsa factoring number-theory
edited 2 hours ago
SEJPM♦
27.6k451130
asked 4 hours ago
Marc Ilunga
262
I was wondering whether given a concrete $N = p cdot q$ whether we can find a upper bound on $Delta = | p - q|$ as function of $N$ e.g, $N^delta$, and thus test whether a given $N$ is vulnerable to Fermat-Factoring?
rsa factoring number-theory
rsa factoring number-theory
edited 2 hours ago
SEJPM♦
27.6k451130
asked 4 hours ago
Marc Ilunga
262
edited 2 hours ago
SEJPM♦
27.6k451130
asked 4 hours ago
Marc Ilunga
262
edited 2 hours ago
SEJPM♦
27.6k451130
edited 2 hours ago
SEJPM♦
27.6k451130
edited 2 hours ago
SEJPM♦
27.6k451130
27.6k451130
asked 4 hours ago
Marc Ilunga
262
asked 4 hours ago
Marc Ilunga
262
asked 4 hours ago
Marc Ilunga
262
262
Marc, are trying to say; in case of security, what are the bound of the difference $ a < |p-q| < b$
– kelalaka
4 hours ago
@kelalaka, Yes I am wondering if it is possible to detect unsafe primes for RSA. "IF" it ever happens and in a way that It can be factored using Fermat's method.
– Marc Ilunga
3 hours ago
add a comment |Â
Marc, are trying to say; in case of security, what are the bound of the difference $ a < |p-q| < b$
– kelalaka
4 hours ago
@kelalaka, Yes I am wondering if it is possible to detect unsafe primes for RSA. "IF" it ever happens and in a way that It can be factored using Fermat's method.
– Marc Ilunga
3 hours ago
Marc, are trying to say; in case of security, what are the bound of the difference $ a < |p-q| < b$
– kelalaka
4 hours ago
Marc, are trying to say; in case of security, what are the bound of the difference $ a < |p-q| < b$
– kelalaka
4 hours ago
@kelalaka, Yes I am wondering if it is possible to detect unsafe primes for RSA. "IF" it ever happens and in a way that It can be factored using Fermat's method.
– Marc Ilunga
3 hours ago
@kelalaka, Yes I am wondering if it is possible to detect unsafe primes for RSA. "IF" it ever happens and in a way that It can be factored using Fermat's method.
– Marc Ilunga
3 hours ago
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
4
down vote
Given that $p$ and $q$ are prime, they must be at least $2$, so $|p-q| le frac 12N - 2$. I'm pretty sure that's the only hard upper bound one can give.
Of course, typically $p$ and $q$ are chosen at random from among primes having the same bitlength in binary, meaning that the expected value of $|p-q|$ is roughly proportional to $N^frac12$.
answered 4 hours ago
Ilmari Karonen
33k264131
Thanks for your answer, the hidden intent behind the question was also with regard to Fermat factoring methods and variants. Although It seems the way we generate primes for RSA is safe, I was wondering if there is a way to detect if a number is "Fermat"-factorable. In which case $|p - q| < N^1/4$ should be enough. P.S: This has probably low probability of happening but I am curious. ;)
– Marc Ilunga
3 hours ago
1
With $N$ at hand, trial division allows a small improvement :-)
– fgrieu
2 hours ago
1
Even if we could find "a way to detect if a number is Fermat-factorable", we'd need to insure that $6,N$ can't be factored into $(2,p)(3,q)$ by Fermat's method. And same for $a,b,N$ with a wide choice of $a$ and $b$ coprime...
– fgrieu
2 hours ago
Illmari, could you write the reason for the bound into the question?
– kelalaka
25 mins ago
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
Given that $p$ and $q$ are prime, they must be at least $2$, so $|p-q| le frac 12N - 2$. I'm pretty sure that's the only hard upper bound one can give.
Of course, typically $p$ and $q$ are chosen at random from among primes having the same bitlength in binary, meaning that the expected value of $|p-q|$ is roughly proportional to $N^frac12$.
answered 4 hours ago
Ilmari Karonen
33k264131
Thanks for your answer, the hidden intent behind the question was also with regard to Fermat factoring methods and variants. Although It seems the way we generate primes for RSA is safe, I was wondering if there is a way to detect if a number is "Fermat"-factorable. In which case $|p - q| < N^1/4$ should be enough. P.S: This has probably low probability of happening but I am curious. ;)
– Marc Ilunga
3 hours ago
1
With $N$ at hand, trial division allows a small improvement :-)
– fgrieu
2 hours ago
1
Even if we could find "a way to detect if a number is Fermat-factorable", we'd need to insure that $6,N$ can't be factored into $(2,p)(3,q)$ by Fermat's method. And same for $a,b,N$ with a wide choice of $a$ and $b$ coprime...
– fgrieu
2 hours ago
Illmari, could you write the reason for the bound into the question?
– kelalaka
25 mins ago
add a comment |Â
up vote
4
down vote
Given that $p$ and $q$ are prime, they must be at least $2$, so $|p-q| le frac 12N - 2$. I'm pretty sure that's the only hard upper bound one can give.
Of course, typically $p$ and $q$ are chosen at random from among primes having the same bitlength in binary, meaning that the expected value of $|p-q|$ is roughly proportional to $N^frac12$.
answered 4 hours ago
Ilmari Karonen
33k264131
Thanks for your answer, the hidden intent behind the question was also with regard to Fermat factoring methods and variants. Although It seems the way we generate primes for RSA is safe, I was wondering if there is a way to detect if a number is "Fermat"-factorable. In which case $|p - q| < N^1/4$ should be enough. P.S: This has probably low probability of happening but I am curious. ;)
– Marc Ilunga
3 hours ago
1
With $N$ at hand, trial division allows a small improvement :-)
– fgrieu
2 hours ago
1
Even if we could find "a way to detect if a number is Fermat-factorable", we'd need to insure that $6,N$ can't be factored into $(2,p)(3,q)$ by Fermat's method. And same for $a,b,N$ with a wide choice of $a$ and $b$ coprime...
– fgrieu
2 hours ago
Illmari, could you write the reason for the bound into the question?
– kelalaka
25 mins ago
add a comment |Â
up vote
4
down vote
up vote
4
down vote
Given that $p$ and $q$ are prime, they must be at least $2$, so $|p-q| le frac 12N - 2$. I'm pretty sure that's the only hard upper bound one can give.
Of course, typically $p$ and $q$ are chosen at random from among primes having the same bitlength in binary, meaning that the expected value of $|p-q|$ is roughly proportional to $N^frac12$.
answered 4 hours ago
Ilmari Karonen
33k264131
Given that $p$ and $q$ are prime, they must be at least $2$, so $|p-q| le frac 12N - 2$. I'm pretty sure that's the only hard upper bound one can give.
Of course, typically $p$ and $q$ are chosen at random from among primes having the same bitlength in binary, meaning that the expected value of $|p-q|$ is roughly proportional to $N^frac12$.
answered 4 hours ago
Ilmari Karonen
33k264131
answered 4 hours ago
Ilmari Karonen
33k264131
answered 4 hours ago
Ilmari Karonen
33k264131
answered 4 hours ago
Ilmari Karonen
33k264131
33k264131
Thanks for your answer, the hidden intent behind the question was also with regard to Fermat factoring methods and variants. Although It seems the way we generate primes for RSA is safe, I was wondering if there is a way to detect if a number is "Fermat"-factorable. In which case $|p - q| < N^1/4$ should be enough. P.S: This has probably low probability of happening but I am curious. ;)
– Marc Ilunga
3 hours ago
1
With $N$ at hand, trial division allows a small improvement :-)
– fgrieu
2 hours ago
1
Even if we could find "a way to detect if a number is Fermat-factorable", we'd need to insure that $6,N$ can't be factored into $(2,p)(3,q)$ by Fermat's method. And same for $a,b,N$ with a wide choice of $a$ and $b$ coprime...
– fgrieu
2 hours ago
Illmari, could you write the reason for the bound into the question?
– kelalaka
25 mins ago
add a comment |Â
Thanks for your answer, the hidden intent behind the question was also with regard to Fermat factoring methods and variants. Although It seems the way we generate primes for RSA is safe, I was wondering if there is a way to detect if a number is "Fermat"-factorable. In which case $|p - q| < N^1/4$ should be enough. P.S: This has probably low probability of happening but I am curious. ;)
– Marc Ilunga
3 hours ago
1
With $N$ at hand, trial division allows a small improvement :-)
– fgrieu
2 hours ago
1
Even if we could find "a way to detect if a number is Fermat-factorable", we'd need to insure that $6,N$ can't be factored into $(2,p)(3,q)$ by Fermat's method. And same for $a,b,N$ with a wide choice of $a$ and $b$ coprime...
– fgrieu
2 hours ago
Illmari, could you write the reason for the bound into the question?
– kelalaka
25 mins ago
Thanks for your answer, the hidden intent behind the question was also with regard to Fermat factoring methods and variants. Although It seems the way we generate primes for RSA is safe, I was wondering if there is a way to detect if a number is "Fermat"-factorable. In which case $|p - q| < N^1/4$ should be enough. P.S: This has probably low probability of happening but I am curious. ;)
– Marc Ilunga
3 hours ago
Thanks for your answer, the hidden intent behind the question was also with regard to Fermat factoring methods and variants. Although It seems the way we generate primes for RSA is safe, I was wondering if there is a way to detect if a number is "Fermat"-factorable. In which case $|p - q| < N^1/4$ should be enough. P.S: This has probably low probability of happening but I am curious. ;)
– Marc Ilunga
3 hours ago
1
1
With $N$ at hand, trial division allows a small improvement :-)
– fgrieu
2 hours ago
With $N$ at hand, trial division allows a small improvement :-)
– fgrieu
2 hours ago
1
1
Even if we could find "a way to detect if a number is Fermat-factorable", we'd need to insure that $6,N$ can't be factored into $(2,p)(3,q)$ by Fermat's method. And same for $a,b,N$ with a wide choice of $a$ and $b$ coprime...
– fgrieu
2 hours ago
Even if we could find "a way to detect if a number is Fermat-factorable", we'd need to insure that $6,N$ can't be factored into $(2,p)(3,q)$ by Fermat's method. And same for $a,b,N$ with a wide choice of $a$ and $b$ coprime...
– fgrieu
2 hours ago
Illmari, could you write the reason for the bound into the question?
– kelalaka
25 mins ago
Illmari, could you write the reason for the bound into the question?
– kelalaka
25 mins ago
add a comment |Â
Â
draft saved
draft discarded
Â
draft saved
draft discarded
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%2fcrypto.stackexchange.com%2fquestions%2f63789%2fupper-bounds-on-difference-of-rsa-primes%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
Marc, are trying to say; in case of security, what are the bound of the difference $ a < |p-q| < b$
– kelalaka
4 hours ago
@kelalaka, Yes I am wondering if it is possible to detect unsafe primes for RSA. "IF" it ever happens and in a way that It can be factored using Fermat's method.
– Marc Ilunga
3 hours ago