RSA: Danger of using p to create qRSA key pair generation using PRNG with same seedReducing key shares in Damgård-Dupont threshold RSAVerify a RSA signature using only RSA encryptionIs it possible to create “non overlapping” RNGs?RSA encryption using multiplicationRSA encryption using euclidean alorithmHow many random bits are required to create one RSA key?Manually encrypt using RSA X509 in .NETGenerate shared secrets using RSABreaking RSA using known root
Uncaught TypeError: 'set' on proxy: trap returned falsish for property Name
Are astronomers waiting to see something in an image from a gravitational lens that they've already seen in an adjacent image?
Are the number of citations and number of published articles the most important criteria for a tenure promotion?
Has there ever been an airliner design involving reducing generator load by installing solar panels?
Does detail obscure or enhance action?
Theorems that impeded progress
Why "Having chlorophyll without photosynthesis is actually very dangerous" and "like living with a bomb"?
How to source a part of a file
Why can't I see bouncing of switch on oscilloscope screen?
Why do I get two different answers for this counting problem?
How does Bumblebee speak English as soon as he arrives on Earth in the Bumblebee movie?
RSA: Danger of using p to create q
High voltage LED indicator 40-1000 VDC without additional power supply
Client team has low performances and low technical skills: we always fix their work and now they stop collaborate with us. How to solve?
Do I have a twin with permutated remainders?
Arrow those variables!
Can a Cauchy sequence converge for one metric while not converging for another?
Approximately how much travel time was saved by the opening of the Suez Canal in 1869?
How to move a thin line with the black arrow in Illustrator?
If human space travel is limited by the G force vulnerability, is there a way to counter G forces?
Is it inappropriate for a student to attend their mentor's dissertation defense?
Which country benefited the most from UN Security Council vetoes?
Can a monk's single staff be considered dual wielded, as per the Dual Wielder feat?
Rock identification in KY
RSA: Danger of using p to create q
RSA key pair generation using PRNG with same seedReducing key shares in Damgård-Dupont threshold RSAVerify a RSA signature using only RSA encryptionIs it possible to create “non overlapping” RNGs?RSA encryption using multiplicationRSA encryption using euclidean alorithmHow many random bits are required to create one RSA key?Manually encrypt using RSA X509 in .NETGenerate shared secrets using RSABreaking RSA using known root
$begingroup$
Assume my prime generation is as follows:
Pick a number $q$ between 1000 and 9999. $p=abcd$.
Make sure p is prime
Construct $p$ such by taking the last 2 digits of $q$ and the first 2 digits of q, i.e. $q=cdab$
Make sure q is prime.
Is the resulting $n$ more easily factorable?
My gut feeling says yes but I can't see why? I thought about Coppersmith but in this case, we don't have any common bit between $p$ and $q$ that are also at the same place. Is there a weakness?
rsa random-number-generator
asked 5 hours ago
S. L.S. L.
926
$endgroup$
add a comment |
$begingroup$
Assume my prime generation is as follows:
Pick a number $q$ between 1000 and 9999. $p=abcd$.
Make sure p is prime
Construct $p$ such by taking the last 2 digits of $q$ and the first 2 digits of q, i.e. $q=cdab$
Make sure q is prime.
Is the resulting $n$ more easily factorable?
My gut feeling says yes but I can't see why? I thought about Coppersmith but in this case, we don't have any common bit between $p$ and $q$ that are also at the same place. Is there a weakness?
rsa random-number-generator
asked 5 hours ago
S. L.S. L.
926
$endgroup$
4
$begingroup$
I noticed that there is no "check if $p$ is prime" or "check if $q$ is prime" listed anywhere in these steps (particularly after step 2). Are we to assume that this check is not done?
$endgroup$
– Ella Rose♦
4 hours ago
add a comment |
$begingroup$
Assume my prime generation is as follows:
Pick a number $q$ between 1000 and 9999. $p=abcd$.
Make sure p is prime
Construct $p$ such by taking the last 2 digits of $q$ and the first 2 digits of q, i.e. $q=cdab$
Make sure q is prime.
Is the resulting $n$ more easily factorable?
My gut feeling says yes but I can't see why? I thought about Coppersmith but in this case, we don't have any common bit between $p$ and $q$ that are also at the same place. Is there a weakness?
rsa random-number-generator
asked 5 hours ago
S. L.S. L.
926
$endgroup$
Assume my prime generation is as follows:
Pick a number $q$ between 1000 and 9999. $p=abcd$.
Make sure p is prime
Construct $p$ such by taking the last 2 digits of $q$ and the first 2 digits of q, i.e. $q=cdab$
Make sure q is prime.
Is the resulting $n$ more easily factorable?
My gut feeling says yes but I can't see why? I thought about Coppersmith but in this case, we don't have any common bit between $p$ and $q$ that are also at the same place. Is there a weakness?
rsa random-number-generator
rsa random-number-generator
asked 5 hours ago
S. L.S. L.
926
asked 5 hours ago
S. L.S. L.
926
edited 2 hours ago
S. L.
asked 5 hours ago
S. L.S. L.
926
asked 5 hours ago
S. L.S. L.
926
asked 5 hours ago
S. L.S. L.
926
926
4
$begingroup$
I noticed that there is no "check if $p$ is prime" or "check if $q$ is prime" listed anywhere in these steps (particularly after step 2). Are we to assume that this check is not done?
$endgroup$
– Ella Rose♦
4 hours ago
add a comment |
4
$begingroup$
I noticed that there is no "check if $p$ is prime" or "check if $q$ is prime" listed anywhere in these steps (particularly after step 2). Are we to assume that this check is not done?
$endgroup$
– Ella Rose♦
4 hours ago
4
4
$begingroup$
I noticed that there is no "check if $p$ is prime" or "check if $q$ is prime" listed anywhere in these steps (particularly after step 2). Are we to assume that this check is not done?
$endgroup$
– Ella Rose♦
4 hours ago
$begingroup$
I noticed that there is no "check if $p$ is prime" or "check if $q$ is prime" listed anywhere in these steps (particularly after step 2). Are we to assume that this check is not done?
$endgroup$
– Ella Rose♦
4 hours ago
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
You don't need anything fancy like Coppersmith, just simple algebra. The idea is to translate the equations we have involving the digits of $p$ and $q$ in base $B$ ($B = 100$ in your example) into equations involving the digits of $n$ in base $B$, which we know. You have $p = x B + y$ and $q = y B + x$, with $0 lt x, y lt B$. Then $n = x y B^2 + (x^2 + y^2) B + x y$.
The rightmost digit of $n$ in base $B$ is $(x y) bmod B$. Since $x,y le B-1$, $(x^2 + y^2) B + x y le 2 (B-1)^2 B + (B-1)^2 lt 2 (B-1)^2 (B+1) = 2 (B-1) (B^2-1) lt 2 B^3$. Hence the $B^3$ digit of $n$ is the $B$ digit of $x y$ plus $z$ where $0 le z lt 2$, i.e. $z in 0, 1$. So by reading the digits of $n$ in base $B$, we get the digits of $x y$ in base $B$, up to two possibilities, giving just two possibilities for $x y$ itself: $x y in W_0, W_1$.
Injecting this knowledge into the equation above gives us $x^2 + y^2 = (n - W_z (B^2 + 1)) / B$. And of course knowing both $x^2 + y^2$ and $x y$ gives $x$ and $y$.
answered 4 hours ago
GillesGilles
8,33732756
$endgroup$
$begingroup$
Thanks for the explanation! I get most of it but wouldn't $n= xyB^2 + Bx^2 + By^2 + xy$? Do the other equations hold?
$endgroup$
– S. L.
3 hours ago
$begingroup$
@S.L. Woops, different equation, but same principle.
$endgroup$
– Gilles
1 hour ago
add a comment |
$begingroup$
Here's how to recover $x, y$ in a way that's easier than factoring $n$ (I'll use the notation $x, y$ rather than your notation $ab, cd$):
We have $n = xyB^2 + (x^2+y^2)B + xy$
First, compute $n bmod B$, that gives you $xy bmod B$
Then, compute $lfloor (n - B^2(xy bmod B)) / B^3 rfloor$; this gives you $xy / B + epsilon$, where $0 le epsilon le 2$
Pasting those two together will give you a total of three possibilities of $xy$.
Then, for each possibility, compute $(n - xyB^2 - xy) / B + 2xy$ and $(n - xyB^2 - xy) / B - 2xy$; if the guess of $epsilon$ is correct, these will be $(x+y)^2$ and $(x-y)^2$; take squareroots, and extract $x, y$ directly.
(Thanks for Giles for pointing out this last part)
answered 2 hours ago
ponchoponcho
93.8k2146244
$endgroup$
$begingroup$
Yeah, right, the $B^3$ digit of $n$ gives the other digit of $x y$. And there's no need to factor anything: once you know $x y$, you know $x^2 + y^2$.
$endgroup$
– Gilles
1 hour ago
$begingroup$
@Gilles: yup, you're right; I'll update the answer
$endgroup$
– poncho
1 hour ago
$begingroup$
I don't get this part: Then, compute $⌊(n−B^2(xymod B))/B^3⌋$ this gives you $xy/B+ϵ$, where $0≤ϵ≤2$. I have $xymod B$ but not $xy$?
$endgroup$
– S. L.
1 hour ago
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "281"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f68562%2frsa-danger-of-using-p-to-create-q%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
You don't need anything fancy like Coppersmith, just simple algebra. The idea is to translate the equations we have involving the digits of $p$ and $q$ in base $B$ ($B = 100$ in your example) into equations involving the digits of $n$ in base $B$, which we know. You have $p = x B + y$ and $q = y B + x$, with $0 lt x, y lt B$. Then $n = x y B^2 + (x^2 + y^2) B + x y$.
The rightmost digit of $n$ in base $B$ is $(x y) bmod B$. Since $x,y le B-1$, $(x^2 + y^2) B + x y le 2 (B-1)^2 B + (B-1)^2 lt 2 (B-1)^2 (B+1) = 2 (B-1) (B^2-1) lt 2 B^3$. Hence the $B^3$ digit of $n$ is the $B$ digit of $x y$ plus $z$ where $0 le z lt 2$, i.e. $z in 0, 1$. So by reading the digits of $n$ in base $B$, we get the digits of $x y$ in base $B$, up to two possibilities, giving just two possibilities for $x y$ itself: $x y in W_0, W_1$.
Injecting this knowledge into the equation above gives us $x^2 + y^2 = (n - W_z (B^2 + 1)) / B$. And of course knowing both $x^2 + y^2$ and $x y$ gives $x$ and $y$.
answered 4 hours ago
GillesGilles
8,33732756
$endgroup$
$begingroup$
Thanks for the explanation! I get most of it but wouldn't $n= xyB^2 + Bx^2 + By^2 + xy$? Do the other equations hold?
$endgroup$
– S. L.
3 hours ago
$begingroup$
@S.L. Woops, different equation, but same principle.
$endgroup$
– Gilles
1 hour ago
add a comment |
$begingroup$
You don't need anything fancy like Coppersmith, just simple algebra. The idea is to translate the equations we have involving the digits of $p$ and $q$ in base $B$ ($B = 100$ in your example) into equations involving the digits of $n$ in base $B$, which we know. You have $p = x B + y$ and $q = y B + x$, with $0 lt x, y lt B$. Then $n = x y B^2 + (x^2 + y^2) B + x y$.
The rightmost digit of $n$ in base $B$ is $(x y) bmod B$. Since $x,y le B-1$, $(x^2 + y^2) B + x y le 2 (B-1)^2 B + (B-1)^2 lt 2 (B-1)^2 (B+1) = 2 (B-1) (B^2-1) lt 2 B^3$. Hence the $B^3$ digit of $n$ is the $B$ digit of $x y$ plus $z$ where $0 le z lt 2$, i.e. $z in 0, 1$. So by reading the digits of $n$ in base $B$, we get the digits of $x y$ in base $B$, up to two possibilities, giving just two possibilities for $x y$ itself: $x y in W_0, W_1$.
Injecting this knowledge into the equation above gives us $x^2 + y^2 = (n - W_z (B^2 + 1)) / B$. And of course knowing both $x^2 + y^2$ and $x y$ gives $x$ and $y$.
answered 4 hours ago
GillesGilles
8,33732756
$endgroup$
$begingroup$
Thanks for the explanation! I get most of it but wouldn't $n= xyB^2 + Bx^2 + By^2 + xy$? Do the other equations hold?
$endgroup$
– S. L.
3 hours ago
$begingroup$
@S.L. Woops, different equation, but same principle.
$endgroup$
– Gilles
1 hour ago
add a comment |
$begingroup$
You don't need anything fancy like Coppersmith, just simple algebra. The idea is to translate the equations we have involving the digits of $p$ and $q$ in base $B$ ($B = 100$ in your example) into equations involving the digits of $n$ in base $B$, which we know. You have $p = x B + y$ and $q = y B + x$, with $0 lt x, y lt B$. Then $n = x y B^2 + (x^2 + y^2) B + x y$.
The rightmost digit of $n$ in base $B$ is $(x y) bmod B$. Since $x,y le B-1$, $(x^2 + y^2) B + x y le 2 (B-1)^2 B + (B-1)^2 lt 2 (B-1)^2 (B+1) = 2 (B-1) (B^2-1) lt 2 B^3$. Hence the $B^3$ digit of $n$ is the $B$ digit of $x y$ plus $z$ where $0 le z lt 2$, i.e. $z in 0, 1$. So by reading the digits of $n$ in base $B$, we get the digits of $x y$ in base $B$, up to two possibilities, giving just two possibilities for $x y$ itself: $x y in W_0, W_1$.
Injecting this knowledge into the equation above gives us $x^2 + y^2 = (n - W_z (B^2 + 1)) / B$. And of course knowing both $x^2 + y^2$ and $x y$ gives $x$ and $y$.
answered 4 hours ago
GillesGilles
8,33732756
$endgroup$
You don't need anything fancy like Coppersmith, just simple algebra. The idea is to translate the equations we have involving the digits of $p$ and $q$ in base $B$ ($B = 100$ in your example) into equations involving the digits of $n$ in base $B$, which we know. You have $p = x B + y$ and $q = y B + x$, with $0 lt x, y lt B$. Then $n = x y B^2 + (x^2 + y^2) B + x y$.
The rightmost digit of $n$ in base $B$ is $(x y) bmod B$. Since $x,y le B-1$, $(x^2 + y^2) B + x y le 2 (B-1)^2 B + (B-1)^2 lt 2 (B-1)^2 (B+1) = 2 (B-1) (B^2-1) lt 2 B^3$. Hence the $B^3$ digit of $n$ is the $B$ digit of $x y$ plus $z$ where $0 le z lt 2$, i.e. $z in 0, 1$. So by reading the digits of $n$ in base $B$, we get the digits of $x y$ in base $B$, up to two possibilities, giving just two possibilities for $x y$ itself: $x y in W_0, W_1$.
Injecting this knowledge into the equation above gives us $x^2 + y^2 = (n - W_z (B^2 + 1)) / B$. And of course knowing both $x^2 + y^2$ and $x y$ gives $x$ and $y$.
answered 4 hours ago
GillesGilles
8,33732756
edited 1 hour ago
answered 4 hours ago
GillesGilles
8,33732756
answered 4 hours ago
GillesGilles
8,33732756
answered 4 hours ago
GillesGilles
8,33732756
8,33732756
$begingroup$
Thanks for the explanation! I get most of it but wouldn't $n= xyB^2 + Bx^2 + By^2 + xy$? Do the other equations hold?
$endgroup$
– S. L.
3 hours ago
$begingroup$
@S.L. Woops, different equation, but same principle.
$endgroup$
– Gilles
1 hour ago
add a comment |
$begingroup$
Thanks for the explanation! I get most of it but wouldn't $n= xyB^2 + Bx^2 + By^2 + xy$? Do the other equations hold?
$endgroup$
– S. L.
3 hours ago
$begingroup$
@S.L. Woops, different equation, but same principle.
$endgroup$
– Gilles
1 hour ago
$begingroup$
Thanks for the explanation! I get most of it but wouldn't $n= xyB^2 + Bx^2 + By^2 + xy$? Do the other equations hold?
$endgroup$
– S. L.
3 hours ago
$begingroup$
Thanks for the explanation! I get most of it but wouldn't $n= xyB^2 + Bx^2 + By^2 + xy$? Do the other equations hold?
$endgroup$
– S. L.
3 hours ago
$begingroup$
@S.L. Woops, different equation, but same principle.
$endgroup$
– Gilles
1 hour ago
$begingroup$
@S.L. Woops, different equation, but same principle.
$endgroup$
– Gilles
1 hour ago
add a comment |
$begingroup$
Here's how to recover $x, y$ in a way that's easier than factoring $n$ (I'll use the notation $x, y$ rather than your notation $ab, cd$):
We have $n = xyB^2 + (x^2+y^2)B + xy$
First, compute $n bmod B$, that gives you $xy bmod B$
Then, compute $lfloor (n - B^2(xy bmod B)) / B^3 rfloor$; this gives you $xy / B + epsilon$, where $0 le epsilon le 2$
Pasting those two together will give you a total of three possibilities of $xy$.
Then, for each possibility, compute $(n - xyB^2 - xy) / B + 2xy$ and $(n - xyB^2 - xy) / B - 2xy$; if the guess of $epsilon$ is correct, these will be $(x+y)^2$ and $(x-y)^2$; take squareroots, and extract $x, y$ directly.
(Thanks for Giles for pointing out this last part)
answered 2 hours ago
ponchoponcho
93.8k2146244
$endgroup$
$begingroup$
Yeah, right, the $B^3$ digit of $n$ gives the other digit of $x y$. And there's no need to factor anything: once you know $x y$, you know $x^2 + y^2$.
$endgroup$
– Gilles
1 hour ago
$begingroup$
@Gilles: yup, you're right; I'll update the answer
$endgroup$
– poncho
1 hour ago
$begingroup$
I don't get this part: Then, compute $⌊(n−B^2(xymod B))/B^3⌋$ this gives you $xy/B+ϵ$, where $0≤ϵ≤2$. I have $xymod B$ but not $xy$?
$endgroup$
– S. L.
1 hour ago
add a comment |
$begingroup$
Here's how to recover $x, y$ in a way that's easier than factoring $n$ (I'll use the notation $x, y$ rather than your notation $ab, cd$):
We have $n = xyB^2 + (x^2+y^2)B + xy$
First, compute $n bmod B$, that gives you $xy bmod B$
Then, compute $lfloor (n - B^2(xy bmod B)) / B^3 rfloor$; this gives you $xy / B + epsilon$, where $0 le epsilon le 2$
Pasting those two together will give you a total of three possibilities of $xy$.
Then, for each possibility, compute $(n - xyB^2 - xy) / B + 2xy$ and $(n - xyB^2 - xy) / B - 2xy$; if the guess of $epsilon$ is correct, these will be $(x+y)^2$ and $(x-y)^2$; take squareroots, and extract $x, y$ directly.
(Thanks for Giles for pointing out this last part)
answered 2 hours ago
ponchoponcho
93.8k2146244
$endgroup$
$begingroup$
Yeah, right, the $B^3$ digit of $n$ gives the other digit of $x y$. And there's no need to factor anything: once you know $x y$, you know $x^2 + y^2$.
$endgroup$
– Gilles
1 hour ago
$begingroup$
@Gilles: yup, you're right; I'll update the answer
$endgroup$
– poncho
1 hour ago
$begingroup$
I don't get this part: Then, compute $⌊(n−B^2(xymod B))/B^3⌋$ this gives you $xy/B+ϵ$, where $0≤ϵ≤2$. I have $xymod B$ but not $xy$?
$endgroup$
– S. L.
1 hour ago
add a comment |
$begingroup$
Here's how to recover $x, y$ in a way that's easier than factoring $n$ (I'll use the notation $x, y$ rather than your notation $ab, cd$):
We have $n = xyB^2 + (x^2+y^2)B + xy$
First, compute $n bmod B$, that gives you $xy bmod B$
Then, compute $lfloor (n - B^2(xy bmod B)) / B^3 rfloor$; this gives you $xy / B + epsilon$, where $0 le epsilon le 2$
Pasting those two together will give you a total of three possibilities of $xy$.
Then, for each possibility, compute $(n - xyB^2 - xy) / B + 2xy$ and $(n - xyB^2 - xy) / B - 2xy$; if the guess of $epsilon$ is correct, these will be $(x+y)^2$ and $(x-y)^2$; take squareroots, and extract $x, y$ directly.
(Thanks for Giles for pointing out this last part)
answered 2 hours ago
ponchoponcho
93.8k2146244
$endgroup$
Here's how to recover $x, y$ in a way that's easier than factoring $n$ (I'll use the notation $x, y$ rather than your notation $ab, cd$):
We have $n = xyB^2 + (x^2+y^2)B + xy$
First, compute $n bmod B$, that gives you $xy bmod B$
Then, compute $lfloor (n - B^2(xy bmod B)) / B^3 rfloor$; this gives you $xy / B + epsilon$, where $0 le epsilon le 2$
Pasting those two together will give you a total of three possibilities of $xy$.
Then, for each possibility, compute $(n - xyB^2 - xy) / B + 2xy$ and $(n - xyB^2 - xy) / B - 2xy$; if the guess of $epsilon$ is correct, these will be $(x+y)^2$ and $(x-y)^2$; take squareroots, and extract $x, y$ directly.
(Thanks for Giles for pointing out this last part)
answered 2 hours ago
ponchoponcho
93.8k2146244
edited 1 hour ago
answered 2 hours ago
ponchoponcho
93.8k2146244
answered 2 hours ago
ponchoponcho
93.8k2146244
answered 2 hours ago
ponchoponcho
93.8k2146244
93.8k2146244
$begingroup$
Yeah, right, the $B^3$ digit of $n$ gives the other digit of $x y$. And there's no need to factor anything: once you know $x y$, you know $x^2 + y^2$.
$endgroup$
– Gilles
1 hour ago
$begingroup$
@Gilles: yup, you're right; I'll update the answer
$endgroup$
– poncho
1 hour ago
$begingroup$
I don't get this part: Then, compute $⌊(n−B^2(xymod B))/B^3⌋$ this gives you $xy/B+ϵ$, where $0≤ϵ≤2$. I have $xymod B$ but not $xy$?
$endgroup$
– S. L.
1 hour ago
add a comment |
$begingroup$
Yeah, right, the $B^3$ digit of $n$ gives the other digit of $x y$. And there's no need to factor anything: once you know $x y$, you know $x^2 + y^2$.
$endgroup$
– Gilles
1 hour ago
$begingroup$
@Gilles: yup, you're right; I'll update the answer
$endgroup$
– poncho
1 hour ago
$begingroup$
I don't get this part: Then, compute $⌊(n−B^2(xymod B))/B^3⌋$ this gives you $xy/B+ϵ$, where $0≤ϵ≤2$. I have $xymod B$ but not $xy$?
$endgroup$
– S. L.
1 hour ago
$begingroup$
Yeah, right, the $B^3$ digit of $n$ gives the other digit of $x y$. And there's no need to factor anything: once you know $x y$, you know $x^2 + y^2$.
$endgroup$
– Gilles
1 hour ago
$begingroup$
Yeah, right, the $B^3$ digit of $n$ gives the other digit of $x y$. And there's no need to factor anything: once you know $x y$, you know $x^2 + y^2$.
$endgroup$
– Gilles
1 hour ago
$begingroup$
@Gilles: yup, you're right; I'll update the answer
$endgroup$
– poncho
1 hour ago
$begingroup$
@Gilles: yup, you're right; I'll update the answer
$endgroup$
– poncho
1 hour ago
$begingroup$
I don't get this part: Then, compute $⌊(n−B^2(xymod B))/B^3⌋$ this gives you $xy/B+ϵ$, where $0≤ϵ≤2$. I have $xymod B$ but not $xy$?
$endgroup$
– S. L.
1 hour ago
$begingroup$
I don't get this part: Then, compute $⌊(n−B^2(xymod B))/B^3⌋$ this gives you $xy/B+ϵ$, where $0≤ϵ≤2$. I have $xymod B$ but not $xy$?
$endgroup$
– S. L.
1 hour ago
add a comment |
Thanks for contributing an answer to Cryptography Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f68562%2frsa-danger-of-using-p-to-create-q%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
4
$begingroup$
I noticed that there is no "check if $p$ is prime" or "check if $q$ is prime" listed anywhere in these steps (particularly after step 2). Are we to assume that this check is not done?
$endgroup$
– Ella Rose♦
4 hours ago