Understanding affine cypher / Euclidean math The Next CEO of Stack OverflowDiscrete Math -...
Why do professional authors make "consistency" mistakes? And how to avoid them?
Make solar eclipses exceedingly rare, but still have new moons
Inappropriate reference requests from Journal reviewers
How to start emacs in "nothing" mode (`fundamental-mode`)
How do we know the LHC results are robust?
How do I transpose the 1st and -1th levels of an arbitrarily nested array?
Why didn't Khan get resurrected in the Genesis Explosion?
How to solve a differential equation with a term to a power?
Why does standard notation not preserve intervals (visually)
How does the mv command work with external drives?
Can we say or write : "No, it'sn't"?
How do I avoid eval and parse?
Does it take more energy to get to Venus or to Mars?
Is there a way to save my career from absolute disaster?
sp_blitzCache results Memory grants
Real integral using residue theorem - why doesn't this work?
What was the first Unix version to run on a microcomputer?
Are there any limitations on attacking while grappling?
Why do we use the plural of movies in this phrase "We went to the movies last night."?
How do I make a variable always equal to the result of some calculations?
If the heap is initialized for security, then why is the stack uninitialized?
Can you replace a racial trait cantrip when leveling up?
Example of a Mathematician/Physicist whose Other Publications during their PhD eclipsed their PhD Thesis
What benefits would be gained by using human laborers instead of drones in deep sea mining?
Understanding affine cypher / Euclidean math
The Next CEO of Stack OverflowDiscrete Math - Bézout CoefficientsUnderstanding mathematical induction for divisibilityFinding an affine combination of a point on a triangleLenstra's Elliptic Curve AlgorithmUnderstanding Bézout's identity's proof as given on wikipedea.Proof that $sum_{n=1}^infty n $ is -1/12Affine space $-$ Understanding basic exampleWhy is Zero not composite?Affine cypher. Find function and plaintextTwo sequence relations are equivalent.
$begingroup$
$$e(x) = (ax + b)$$
$$d(y) = a^{-1}(y-b)$$
I need to prove that $$e(x)=d(y)$$ iff $$(a^2)=1$$ and $$b(a+1)=0,$$
so I tried working with $d(ex)$ to show they can be equivalent:
$$ax + b = a^{-1}(ax + b - b).$$
Next step will be
$$ax^2 + ba = ax$$
and that's where I'm stuck
I saw a solution doing
$$ ax+ b = a-1(x - b) $$ but I don't understand why this is valid. Shouldn't I replace the $y$ in $$d(y) = a^{-1}(y-b)$$ with the body of $$e(x)$$ after all $$x = d(e(x))$$ right?
And another question - how can I find all involutory keys in $mathbb N$?
elementary-number-theory cryptography affine-geometry
edited Mar 16 at 18:26
Robert Howard
2,2783935
asked Mar 16 at 17:52
igxigx
1165
$endgroup$
add a comment |
$begingroup$
$$e(x) = (ax + b)$$
$$d(y) = a^{-1}(y-b)$$
I need to prove that $$e(x)=d(y)$$ iff $$(a^2)=1$$ and $$b(a+1)=0,$$
so I tried working with $d(ex)$ to show they can be equivalent:
$$ax + b = a^{-1}(ax + b - b).$$
Next step will be
$$ax^2 + ba = ax$$
and that's where I'm stuck
I saw a solution doing
$$ ax+ b = a-1(x - b) $$ but I don't understand why this is valid. Shouldn't I replace the $y$ in $$d(y) = a^{-1}(y-b)$$ with the body of $$e(x)$$ after all $$x = d(e(x))$$ right?
And another question - how can I find all involutory keys in $mathbb N$?
elementary-number-theory cryptography affine-geometry
edited Mar 16 at 18:26
Robert Howard
2,2783935
asked Mar 16 at 17:52
igxigx
1165
$endgroup$
1
$begingroup$
In $mathbb{N}$ the cipher is only invertible if $a in {-1,1}$. This limits the number of possible ciphers.
$endgroup$
– Henno Brandsma
Mar 17 at 16:12
add a comment |
$begingroup$
$$e(x) = (ax + b)$$
$$d(y) = a^{-1}(y-b)$$
I need to prove that $$e(x)=d(y)$$ iff $$(a^2)=1$$ and $$b(a+1)=0,$$
so I tried working with $d(ex)$ to show they can be equivalent:
$$ax + b = a^{-1}(ax + b - b).$$
Next step will be
$$ax^2 + ba = ax$$
and that's where I'm stuck
I saw a solution doing
$$ ax+ b = a-1(x - b) $$ but I don't understand why this is valid. Shouldn't I replace the $y$ in $$d(y) = a^{-1}(y-b)$$ with the body of $$e(x)$$ after all $$x = d(e(x))$$ right?
And another question - how can I find all involutory keys in $mathbb N$?
elementary-number-theory cryptography affine-geometry
edited Mar 16 at 18:26
Robert Howard
2,2783935
asked Mar 16 at 17:52
igxigx
1165
$endgroup$
$$e(x) = (ax + b)$$
$$d(y) = a^{-1}(y-b)$$
I need to prove that $$e(x)=d(y)$$ iff $$(a^2)=1$$ and $$b(a+1)=0,$$
so I tried working with $d(ex)$ to show they can be equivalent:
$$ax + b = a^{-1}(ax + b - b).$$
Next step will be
$$ax^2 + ba = ax$$
and that's where I'm stuck
I saw a solution doing
$$ ax+ b = a-1(x - b) $$ but I don't understand why this is valid. Shouldn't I replace the $y$ in $$d(y) = a^{-1}(y-b)$$ with the body of $$e(x)$$ after all $$x = d(e(x))$$ right?
And another question - how can I find all involutory keys in $mathbb N$?
elementary-number-theory cryptography affine-geometry
elementary-number-theory cryptography affine-geometry
edited Mar 16 at 18:26
Robert Howard
2,2783935
asked Mar 16 at 17:52
igxigx
1165
edited Mar 16 at 18:26
Robert Howard
2,2783935
asked Mar 16 at 17:52
igxigx
1165
edited Mar 16 at 18:26
Robert Howard
2,2783935
edited Mar 16 at 18:26
Robert Howard
2,2783935
edited Mar 16 at 18:26
Robert Howard
2,2783935
2,2783935
asked Mar 16 at 17:52
igxigx
1165
asked Mar 16 at 17:52
igxigx
1165
asked Mar 16 at 17:52
igxigx
1165
1165
1
$begingroup$
In $mathbb{N}$ the cipher is only invertible if $a in {-1,1}$. This limits the number of possible ciphers.
$endgroup$
– Henno Brandsma
Mar 17 at 16:12
add a comment |
1
$begingroup$
In $mathbb{N}$ the cipher is only invertible if $a in {-1,1}$. This limits the number of possible ciphers.
$endgroup$
– Henno Brandsma
Mar 17 at 16:12
1
1
$begingroup$
In $mathbb{N}$ the cipher is only invertible if $a in {-1,1}$. This limits the number of possible ciphers.
$endgroup$
– Henno Brandsma
Mar 17 at 16:12
$begingroup$
In $mathbb{N}$ the cipher is only invertible if $a in {-1,1}$. This limits the number of possible ciphers.
$endgroup$
– Henno Brandsma
Mar 17 at 16:12
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
If we have that the encryption equals the decryption function, we have that for each $x$ in the ring we're working on ($mathbb{Z}_{26}$ or some other.) we have
$$e(e(x))=x$$ or equivalently
$$forall x: a(ax+b)+b = a^2x+ab+b= x$$
which implies (check that two affine functions are equal everywhere iff they're two coefficients are) that
$$a^2 =1 text{ and } a(1+b)=0$$
Now the argument will depend somewhat on the ring to determine the squares of $1$(there could be just $2$, $1$ and $-1$ or more); modulo $26$ or a prime, there are indeed just these two. And then $b=-1$ is "forced" by the last equation, as $a$ cannot be a zero-divisor. So in the most common cases we'll have two solutions.
answered Mar 17 at 22:10
Henno BrandsmaHenno Brandsma
114k348124
$endgroup$
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%2f3150632%2funderstanding-affine-cypher-euclidean-math%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$
If we have that the encryption equals the decryption function, we have that for each $x$ in the ring we're working on ($mathbb{Z}_{26}$ or some other.) we have
$$e(e(x))=x$$ or equivalently
$$forall x: a(ax+b)+b = a^2x+ab+b= x$$
which implies (check that two affine functions are equal everywhere iff they're two coefficients are) that
$$a^2 =1 text{ and } a(1+b)=0$$
Now the argument will depend somewhat on the ring to determine the squares of $1$(there could be just $2$, $1$ and $-1$ or more); modulo $26$ or a prime, there are indeed just these two. And then $b=-1$ is "forced" by the last equation, as $a$ cannot be a zero-divisor. So in the most common cases we'll have two solutions.
answered Mar 17 at 22:10
Henno BrandsmaHenno Brandsma
114k348124
$endgroup$
add a comment |
$begingroup$
If we have that the encryption equals the decryption function, we have that for each $x$ in the ring we're working on ($mathbb{Z}_{26}$ or some other.) we have
$$e(e(x))=x$$ or equivalently
$$forall x: a(ax+b)+b = a^2x+ab+b= x$$
which implies (check that two affine functions are equal everywhere iff they're two coefficients are) that
$$a^2 =1 text{ and } a(1+b)=0$$
Now the argument will depend somewhat on the ring to determine the squares of $1$(there could be just $2$, $1$ and $-1$ or more); modulo $26$ or a prime, there are indeed just these two. And then $b=-1$ is "forced" by the last equation, as $a$ cannot be a zero-divisor. So in the most common cases we'll have two solutions.
answered Mar 17 at 22:10
Henno BrandsmaHenno Brandsma
114k348124
$endgroup$
add a comment |
$begingroup$
If we have that the encryption equals the decryption function, we have that for each $x$ in the ring we're working on ($mathbb{Z}_{26}$ or some other.) we have
$$e(e(x))=x$$ or equivalently
$$forall x: a(ax+b)+b = a^2x+ab+b= x$$
which implies (check that two affine functions are equal everywhere iff they're two coefficients are) that
$$a^2 =1 text{ and } a(1+b)=0$$
Now the argument will depend somewhat on the ring to determine the squares of $1$(there could be just $2$, $1$ and $-1$ or more); modulo $26$ or a prime, there are indeed just these two. And then $b=-1$ is "forced" by the last equation, as $a$ cannot be a zero-divisor. So in the most common cases we'll have two solutions.
answered Mar 17 at 22:10
Henno BrandsmaHenno Brandsma
114k348124
$endgroup$
If we have that the encryption equals the decryption function, we have that for each $x$ in the ring we're working on ($mathbb{Z}_{26}$ or some other.) we have
$$e(e(x))=x$$ or equivalently
$$forall x: a(ax+b)+b = a^2x+ab+b= x$$
which implies (check that two affine functions are equal everywhere iff they're two coefficients are) that
$$a^2 =1 text{ and } a(1+b)=0$$
Now the argument will depend somewhat on the ring to determine the squares of $1$(there could be just $2$, $1$ and $-1$ or more); modulo $26$ or a prime, there are indeed just these two. And then $b=-1$ is "forced" by the last equation, as $a$ cannot be a zero-divisor. So in the most common cases we'll have two solutions.
answered Mar 17 at 22:10
Henno BrandsmaHenno Brandsma
114k348124
answered Mar 17 at 22:10
Henno BrandsmaHenno Brandsma
114k348124
answered Mar 17 at 22:10
Henno BrandsmaHenno Brandsma
114k348124
answered Mar 17 at 22:10
Henno BrandsmaHenno Brandsma
114k348124
114k348124
add a comment |
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%2f3150632%2funderstanding-affine-cypher-euclidean-math%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
1
$begingroup$
In $mathbb{N}$ the cipher is only invertible if $a in {-1,1}$. This limits the number of possible ciphers.
$endgroup$
– Henno Brandsma
Mar 17 at 16:12