Mixing
How can we solve $x^a = b ; mod ; n$ equation for big n, a,
$begingroup$
I would like to have a method to solve an equation of the type: $x^a = b ; mod ; n$, knowing that n can be decomposed into a product of prime numbers $n = n_1 times n_2 times ... times n_k$
I already know how to do it for small numbers, like if n is a prime number:
in this case, I am looking for $e$, such that $ae = 1 ; mod ; (n-1)$. Like that, I can transform my equation into $x = b^e ; mod ; n$.
But here the numbers are too big to compute this in a single time. So maybe there is a method to solve it I am not aware of.
In my exercise, I have :
n = 264356242932330620591879762011459333409
b = 259252555055790712660181286804144327401
a = 151089236568313654499150506467499
modular-arithmetic arithmetic
asked Jan 22 at 17:40
gommygommy
133
$endgroup$
add a comment |
$begingroup$
I would like to have a method to solve an equation of the type: $x^a = b ; mod ; n$, knowing that n can be decomposed into a product of prime numbers $n = n_1 times n_2 times ... times n_k$
I already know how to do it for small numbers, like if n is a prime number:
in this case, I am looking for $e$, such that $ae = 1 ; mod ; (n-1)$. Like that, I can transform my equation into $x = b^e ; mod ; n$.
But here the numbers are too big to compute this in a single time. So maybe there is a method to solve it I am not aware of.
In my exercise, I have :
n = 264356242932330620591879762011459333409
b = 259252555055790712660181286804144327401
a = 151089236568313654499150506467499
modular-arithmetic arithmetic
asked Jan 22 at 17:40
gommygommy
133
$endgroup$
$begingroup$
Is it $x^a$ or $a^x$?
$endgroup$
– kcborys
Jan 22 at 17:42
$begingroup$
$x^a$ sorry I gonna edit
$endgroup$
– gommy
Jan 22 at 17:42
$begingroup$
Welcome to stackexchange. This looks like cryptography homework. You are more likely to get help rather than downvotes and votes to close if you edit the question to show us what you tried and where you are stuck. Can you do the problem with smaller number?
$endgroup$
– Ethan Bolker
Jan 22 at 17:45
$begingroup$
@Moo : No I am trying to find x. a, b and n are given
$endgroup$
– gommy
Jan 22 at 17:54
add a comment |
$begingroup$
I would like to have a method to solve an equation of the type: $x^a = b ; mod ; n$, knowing that n can be decomposed into a product of prime numbers $n = n_1 times n_2 times ... times n_k$
I already know how to do it for small numbers, like if n is a prime number:
in this case, I am looking for $e$, such that $ae = 1 ; mod ; (n-1)$. Like that, I can transform my equation into $x = b^e ; mod ; n$.
But here the numbers are too big to compute this in a single time. So maybe there is a method to solve it I am not aware of.
In my exercise, I have :
n = 264356242932330620591879762011459333409
b = 259252555055790712660181286804144327401
a = 151089236568313654499150506467499
modular-arithmetic arithmetic
asked Jan 22 at 17:40
gommygommy
133
$endgroup$
I would like to have a method to solve an equation of the type: $x^a = b ; mod ; n$, knowing that n can be decomposed into a product of prime numbers $n = n_1 times n_2 times ... times n_k$
I already know how to do it for small numbers, like if n is a prime number:
in this case, I am looking for $e$, such that $ae = 1 ; mod ; (n-1)$. Like that, I can transform my equation into $x = b^e ; mod ; n$.
But here the numbers are too big to compute this in a single time. So maybe there is a method to solve it I am not aware of.
In my exercise, I have :
n = 264356242932330620591879762011459333409
b = 259252555055790712660181286804144327401
a = 151089236568313654499150506467499
modular-arithmetic arithmetic
modular-arithmetic arithmetic
asked Jan 22 at 17:40
gommygommy
133
asked Jan 22 at 17:40
gommygommy
133
edited Jan 22 at 17:53
gommy
asked Jan 22 at 17:40
gommygommy
133
asked Jan 22 at 17:40
gommygommy
133
asked Jan 22 at 17:40
gommygommy
133
133
$begingroup$
Is it $x^a$ or $a^x$?
$endgroup$
– kcborys
Jan 22 at 17:42
$begingroup$
$x^a$ sorry I gonna edit
$endgroup$
– gommy
Jan 22 at 17:42
$begingroup$
Welcome to stackexchange. This looks like cryptography homework. You are more likely to get help rather than downvotes and votes to close if you edit the question to show us what you tried and where you are stuck. Can you do the problem with smaller number?
$endgroup$
– Ethan Bolker
Jan 22 at 17:45
$begingroup$
@Moo : No I am trying to find x. a, b and n are given
$endgroup$
– gommy
Jan 22 at 17:54
add a comment |
$begingroup$
Is it $x^a$ or $a^x$?
$endgroup$
– kcborys
Jan 22 at 17:42
$begingroup$
$x^a$ sorry I gonna edit
$endgroup$
– gommy
Jan 22 at 17:42
$begingroup$
Welcome to stackexchange. This looks like cryptography homework. You are more likely to get help rather than downvotes and votes to close if you edit the question to show us what you tried and where you are stuck. Can you do the problem with smaller number?
$endgroup$
– Ethan Bolker
Jan 22 at 17:45
$begingroup$
@Moo : No I am trying to find x. a, b and n are given
$endgroup$
– gommy
Jan 22 at 17:54
$begingroup$
Is it $x^a$ or $a^x$?
$endgroup$
– kcborys
Jan 22 at 17:42
$begingroup$
Is it $x^a$ or $a^x$?
$endgroup$
– kcborys
Jan 22 at 17:42
$begingroup$
$x^a$ sorry I gonna edit
$endgroup$
– gommy
Jan 22 at 17:42
$begingroup$
$x^a$ sorry I gonna edit
$endgroup$
– gommy
Jan 22 at 17:42
$begingroup$
Welcome to stackexchange. This looks like cryptography homework. You are more likely to get help rather than downvotes and votes to close if you edit the question to show us what you tried and where you are stuck. Can you do the problem with smaller number?
$endgroup$
– Ethan Bolker
Jan 22 at 17:45
$begingroup$
Welcome to stackexchange. This looks like cryptography homework. You are more likely to get help rather than downvotes and votes to close if you edit the question to show us what you tried and where you are stuck. Can you do the problem with smaller number?
$endgroup$
– Ethan Bolker
Jan 22 at 17:45
$begingroup$
@Moo : No I am trying to find x. a, b and n are given
$endgroup$
– gommy
Jan 22 at 17:54
$begingroup$
@Moo : No I am trying to find x. a, b and n are given
$endgroup$
– gommy
Jan 22 at 17:54
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The Euclidean algorithm proves that $gcd(b,n)=1$.
Since you know the prime factorization of $n$, you know $phi(n)$.
The Euclidean algorithm proves that $gcd(a,phi(n))=1$.
The extended Euclidean algorithm then gives $c$ such that $ac equiv 1 bmod phi(n)$ and so $x equiv b^c$.
These computations are probably not easy when done by hand. But WA handles it fine.
answered Jan 22 at 17:53
lhflhf
166k10171398
$endgroup$
$begingroup$
Thank you for your answer @Ihf, I will try it right now
$endgroup$
– gommy
Jan 22 at 18:05
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: "69"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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');
});
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%2fmath.stackexchange.com%2fquestions%2f3083447%2fhow-can-we-solve-xa-b-mod-n-equation-for-big-n-a%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The Euclidean algorithm proves that $gcd(b,n)=1$.
Since you know the prime factorization of $n$, you know $phi(n)$.
The Euclidean algorithm proves that $gcd(a,phi(n))=1$.
The extended Euclidean algorithm then gives $c$ such that $ac equiv 1 bmod phi(n)$ and so $x equiv b^c$.
These computations are probably not easy when done by hand. But WA handles it fine.
answered Jan 22 at 17:53
lhflhf
166k10171398
$endgroup$
$begingroup$
Thank you for your answer @Ihf, I will try it right now
$endgroup$
– gommy
Jan 22 at 18:05
add a comment |
$begingroup$
The Euclidean algorithm proves that $gcd(b,n)=1$.
Since you know the prime factorization of $n$, you know $phi(n)$.
The Euclidean algorithm proves that $gcd(a,phi(n))=1$.
The extended Euclidean algorithm then gives $c$ such that $ac equiv 1 bmod phi(n)$ and so $x equiv b^c$.
These computations are probably not easy when done by hand. But WA handles it fine.
answered Jan 22 at 17:53
lhflhf
166k10171398
$endgroup$
$begingroup$
Thank you for your answer @Ihf, I will try it right now
$endgroup$
– gommy
Jan 22 at 18:05
add a comment |
$begingroup$
The Euclidean algorithm proves that $gcd(b,n)=1$.
Since you know the prime factorization of $n$, you know $phi(n)$.
The Euclidean algorithm proves that $gcd(a,phi(n))=1$.
The extended Euclidean algorithm then gives $c$ such that $ac equiv 1 bmod phi(n)$ and so $x equiv b^c$.
These computations are probably not easy when done by hand. But WA handles it fine.
answered Jan 22 at 17:53
lhflhf
166k10171398
$endgroup$
The Euclidean algorithm proves that $gcd(b,n)=1$.
Since you know the prime factorization of $n$, you know $phi(n)$.
The Euclidean algorithm proves that $gcd(a,phi(n))=1$.
The extended Euclidean algorithm then gives $c$ such that $ac equiv 1 bmod phi(n)$ and so $x equiv b^c$.
These computations are probably not easy when done by hand. But WA handles it fine.
answered Jan 22 at 17:53
lhflhf
166k10171398
answered Jan 22 at 17:53
lhflhf
166k10171398
answered Jan 22 at 17:53
lhflhf
166k10171398
answered Jan 22 at 17:53
lhflhf
166k10171398
166k10171398
$begingroup$
Thank you for your answer @Ihf, I will try it right now
$endgroup$
– gommy
Jan 22 at 18:05
add a comment |
$begingroup$
Thank you for your answer @Ihf, I will try it right now
$endgroup$
– gommy
Jan 22 at 18:05
$begingroup$
Thank you for your answer @Ihf, I will try it right now
$endgroup$
– gommy
Jan 22 at 18:05
$begingroup$
Thank you for your answer @Ihf, I will try it right now
$endgroup$
– gommy
Jan 22 at 18:05
add a comment |
Thanks for contributing an answer to Mathematics 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');
});
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%2fmath.stackexchange.com%2fquestions%2f3083447%2fhow-can-we-solve-xa-b-mod-n-equation-for-big-n-a%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');
});
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');
});
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');
});
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
$begingroup$
Is it $x^a$ or $a^x$?
$endgroup$
– kcborys
Jan 22 at 17:42
$begingroup$
$x^a$ sorry I gonna edit
$endgroup$
– gommy
Jan 22 at 17:42
$begingroup$
Welcome to stackexchange. This looks like cryptography homework. You are more likely to get help rather than downvotes and votes to close if you edit the question to show us what you tried and where you are stuck. Can you do the problem with smaller number?
$endgroup$
– Ethan Bolker
Jan 22 at 17:45
$begingroup$
@Moo : No I am trying to find x. a, b and n are given
$endgroup$
– gommy
Jan 22 at 17:54