Mixing
Splitting the mod value
$begingroup$
I have $a^x bmod M$ and I am running algorithm based on
$$ (a^2)bmod M = (abmod M) * (abmod M) bmod M.$$
The problem is that if $M$ is longer than half of digits of long long int (for example 14 digits long when long long int is max 19 digits), it can happen that $alt M$ but $a^2$ will overflow.
$a$ is for example 13 digit number
Is there a way how to decompose/divide the $x$ to smaller numbers and do multiple runs with those instead so I will always avoid this? In other words is there some formula for splitting the mod value and compute it separately and then somehow get the result from these subresults?
Edit: Time complexity is an issue so I don't think I can change the algorithm.
modular-arithmetic
edited Jan 8 at 18:49
Arturo Magidin
262k34586910
asked Jan 8 at 18:24
eXPRESSeXPRESS
337
$endgroup$
add a comment |
$begingroup$
I have $a^x bmod M$ and I am running algorithm based on
$$ (a^2)bmod M = (abmod M) * (abmod M) bmod M.$$
The problem is that if $M$ is longer than half of digits of long long int (for example 14 digits long when long long int is max 19 digits), it can happen that $alt M$ but $a^2$ will overflow.
$a$ is for example 13 digit number
Is there a way how to decompose/divide the $x$ to smaller numbers and do multiple runs with those instead so I will always avoid this? In other words is there some formula for splitting the mod value and compute it separately and then somehow get the result from these subresults?
Edit: Time complexity is an issue so I don't think I can change the algorithm.
modular-arithmetic
edited Jan 8 at 18:49
Arturo Magidin
262k34586910
asked Jan 8 at 18:24
eXPRESSeXPRESS
337
$endgroup$
$begingroup$
If time complexity is not an issue, you can always add $a$ by itself $a$-times and take mod at every step.
$endgroup$
– EuxhenH
Jan 8 at 18:30
$begingroup$
@EuxhenH You are right but time complexity is crucial for me, I will edit my question to reflect that.
$endgroup$
– eXPRESS
Jan 8 at 18:34
$begingroup$
All I can think of is finding the factors of $a$ and then applying your algorithm to every factor (i.e., raise to power), and then multiplying them all together. But this is problematic when $a$ is a huge prime.
$endgroup$
– EuxhenH
Jan 8 at 18:43
$begingroup$
@EuxhenH Yeah that is definitely right way to go but way too slow if applied or even checked for every step. I actually do that when entering the algorithm and a is more than half digits of long long int but as algorithm progresses and M is bigger than half of digits I usually run into this problem pretty quickly and repeatedly. Thanks for suggestion though, if computational time is not the issue, it is definitely a solution (expect huge prime factors which would overflow anyway as you mentioned).
$endgroup$
– eXPRESS
Jan 8 at 20:29
add a comment |
$begingroup$
I have $a^x bmod M$ and I am running algorithm based on
$$ (a^2)bmod M = (abmod M) * (abmod M) bmod M.$$
The problem is that if $M$ is longer than half of digits of long long int (for example 14 digits long when long long int is max 19 digits), it can happen that $alt M$ but $a^2$ will overflow.
$a$ is for example 13 digit number
Is there a way how to decompose/divide the $x$ to smaller numbers and do multiple runs with those instead so I will always avoid this? In other words is there some formula for splitting the mod value and compute it separately and then somehow get the result from these subresults?
Edit: Time complexity is an issue so I don't think I can change the algorithm.
modular-arithmetic
edited Jan 8 at 18:49
Arturo Magidin
262k34586910
asked Jan 8 at 18:24
eXPRESSeXPRESS
337
$endgroup$
I have $a^x bmod M$ and I am running algorithm based on
$$ (a^2)bmod M = (abmod M) * (abmod M) bmod M.$$
The problem is that if $M$ is longer than half of digits of long long int (for example 14 digits long when long long int is max 19 digits), it can happen that $alt M$ but $a^2$ will overflow.
$a$ is for example 13 digit number
Is there a way how to decompose/divide the $x$ to smaller numbers and do multiple runs with those instead so I will always avoid this? In other words is there some formula for splitting the mod value and compute it separately and then somehow get the result from these subresults?
Edit: Time complexity is an issue so I don't think I can change the algorithm.
modular-arithmetic
modular-arithmetic
edited Jan 8 at 18:49
Arturo Magidin
262k34586910
asked Jan 8 at 18:24
eXPRESSeXPRESS
337
edited Jan 8 at 18:49
Arturo Magidin
262k34586910
asked Jan 8 at 18:24
eXPRESSeXPRESS
337
edited Jan 8 at 18:49
Arturo Magidin
262k34586910
edited Jan 8 at 18:49
Arturo Magidin
262k34586910
edited Jan 8 at 18:49
Arturo Magidin
262k34586910
262k34586910
asked Jan 8 at 18:24
eXPRESSeXPRESS
337
asked Jan 8 at 18:24
eXPRESSeXPRESS
337
asked Jan 8 at 18:24
eXPRESSeXPRESS
337
337
$begingroup$
If time complexity is not an issue, you can always add $a$ by itself $a$-times and take mod at every step.
$endgroup$
– EuxhenH
Jan 8 at 18:30
$begingroup$
@EuxhenH You are right but time complexity is crucial for me, I will edit my question to reflect that.
$endgroup$
– eXPRESS
Jan 8 at 18:34
$begingroup$
All I can think of is finding the factors of $a$ and then applying your algorithm to every factor (i.e., raise to power), and then multiplying them all together. But this is problematic when $a$ is a huge prime.
$endgroup$
– EuxhenH
Jan 8 at 18:43
$begingroup$
@EuxhenH Yeah that is definitely right way to go but way too slow if applied or even checked for every step. I actually do that when entering the algorithm and a is more than half digits of long long int but as algorithm progresses and M is bigger than half of digits I usually run into this problem pretty quickly and repeatedly. Thanks for suggestion though, if computational time is not the issue, it is definitely a solution (expect huge prime factors which would overflow anyway as you mentioned).
$endgroup$
– eXPRESS
Jan 8 at 20:29
add a comment |
$begingroup$
If time complexity is not an issue, you can always add $a$ by itself $a$-times and take mod at every step.
$endgroup$
– EuxhenH
Jan 8 at 18:30
$begingroup$
@EuxhenH You are right but time complexity is crucial for me, I will edit my question to reflect that.
$endgroup$
– eXPRESS
Jan 8 at 18:34
$begingroup$
All I can think of is finding the factors of $a$ and then applying your algorithm to every factor (i.e., raise to power), and then multiplying them all together. But this is problematic when $a$ is a huge prime.
$endgroup$
– EuxhenH
Jan 8 at 18:43
$begingroup$
@EuxhenH Yeah that is definitely right way to go but way too slow if applied or even checked for every step. I actually do that when entering the algorithm and a is more than half digits of long long int but as algorithm progresses and M is bigger than half of digits I usually run into this problem pretty quickly and repeatedly. Thanks for suggestion though, if computational time is not the issue, it is definitely a solution (expect huge prime factors which would overflow anyway as you mentioned).
$endgroup$
– eXPRESS
Jan 8 at 20:29
$begingroup$
If time complexity is not an issue, you can always add $a$ by itself $a$-times and take mod at every step.
$endgroup$
– EuxhenH
Jan 8 at 18:30
$begingroup$
If time complexity is not an issue, you can always add $a$ by itself $a$-times and take mod at every step.
$endgroup$
– EuxhenH
Jan 8 at 18:30
$begingroup$
@EuxhenH You are right but time complexity is crucial for me, I will edit my question to reflect that.
$endgroup$
– eXPRESS
Jan 8 at 18:34
$begingroup$
@EuxhenH You are right but time complexity is crucial for me, I will edit my question to reflect that.
$endgroup$
– eXPRESS
Jan 8 at 18:34
$begingroup$
All I can think of is finding the factors of $a$ and then applying your algorithm to every factor (i.e., raise to power), and then multiplying them all together. But this is problematic when $a$ is a huge prime.
$endgroup$
– EuxhenH
Jan 8 at 18:43
$begingroup$
All I can think of is finding the factors of $a$ and then applying your algorithm to every factor (i.e., raise to power), and then multiplying them all together. But this is problematic when $a$ is a huge prime.
$endgroup$
– EuxhenH
Jan 8 at 18:43
$begingroup$
@EuxhenH Yeah that is definitely right way to go but way too slow if applied or even checked for every step. I actually do that when entering the algorithm and a is more than half digits of long long int but as algorithm progresses and M is bigger than half of digits I usually run into this problem pretty quickly and repeatedly. Thanks for suggestion though, if computational time is not the issue, it is definitely a solution (expect huge prime factors which would overflow anyway as you mentioned).
$endgroup$
– eXPRESS
Jan 8 at 20:29
$begingroup$
@EuxhenH Yeah that is definitely right way to go but way too slow if applied or even checked for every step. I actually do that when entering the algorithm and a is more than half digits of long long int but as algorithm progresses and M is bigger than half of digits I usually run into this problem pretty quickly and repeatedly. Thanks for suggestion though, if computational time is not the issue, it is definitely a solution (expect huge prime factors which would overflow anyway as you mentioned).
$endgroup$
– eXPRESS
Jan 8 at 20:29
add a comment |
0
active
oldest
votes
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%2f3066543%2fsplitting-the-mod-value%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3066543%2fsplitting-the-mod-value%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$
If time complexity is not an issue, you can always add $a$ by itself $a$-times and take mod at every step.
$endgroup$
– EuxhenH
Jan 8 at 18:30
$begingroup$
@EuxhenH You are right but time complexity is crucial for me, I will edit my question to reflect that.
$endgroup$
– eXPRESS
Jan 8 at 18:34
$begingroup$
All I can think of is finding the factors of $a$ and then applying your algorithm to every factor (i.e., raise to power), and then multiplying them all together. But this is problematic when $a$ is a huge prime.
$endgroup$
– EuxhenH
Jan 8 at 18:43
$begingroup$
@EuxhenH Yeah that is definitely right way to go but way too slow if applied or even checked for every step. I actually do that when entering the algorithm and a is more than half digits of long long int but as algorithm progresses and M is bigger than half of digits I usually run into this problem pretty quickly and repeatedly. Thanks for suggestion though, if computational time is not the issue, it is definitely a solution (expect huge prime factors which would overflow anyway as you mentioned).
$endgroup$
– eXPRESS
Jan 8 at 20:29