hippo9 wrote:On the same topic, I'd assume that would be true also for any affine cipher's (although that might be harder to ensure) because they are also just monoalphabetic substitutions.
megrimlockawesom wrote:can someone explain to me multiplicative inverse with euclidean algorithm? I have been able to get most of the affine cipher except for this bit.
UTF-8 U+6211 U+662F wrote:megrimlockawesom wrote:can someone explain to me multiplicative inverse with euclidean algorithm? I have been able to get most of the affine cipher except for this bit.
Sure!
Suppose you want to find the multiplicative inverse of 8 modulus 27.
(Little math side note: this is a solution for x in the Diophantine equation )
We proceed by using the regular Euclidean algorithm:
Divide 27 by 8.
Divide 8 by 3.
Divide 5 by 3.
Divide 3 by 2.
Now that we have a 1 at the end, we can proceed to the extended Euclidean algorithm. First, rearrange the equations.
Equation 1:
Equation 2:
Equation 3:
Equation 4:
Now.. we can substitute equation 3 into equation 4:
And then equation 2:
And then equation 1:
Rearrange a little...
Now, we have solved the Diophantine equation.
Here's the trick: we set the equation modulus 27.
So, the multiplicative inverse of 8 mod 27 is 17.
This won't take nearly as long once you get used to it.
Name wrote:UTF-8 U+6211 U+662F wrote:megrimlockawesom wrote:can someone explain to me multiplicative inverse with euclidean algorithm? I have been able to get most of the affine cipher except for this bit.
Sure!
Suppose you want to find the multiplicative inverse of 8 modulus 27.
(Little math side note: this is a solution for x in the Diophantine equation )
We proceed by using the regular Euclidean algorithm:
Divide 27 by 8.
Divide 8 by 3.
Divide 5 by 3.
Divide 3 by 2.
Now that we have a 1 at the end, we can proceed to the extended Euclidean algorithm. First, rearrange the equations.
Equation 1:
Equation 2:
Equation 3:
Equation 4:
Now.. we can substitute equation 3 into equation 4:
And then equation 2:
And then equation 1:
Rearrange a little...
Now, we have solved the Diophantine equation.
Here's the trick: we set the equation modulus 27.
So, the multiplicative inverse of 8 mod 27 is 17.
This won't take nearly as long once you get used to it.
Well honestly I have no idea what you did so here's what I do
(Also generally it's mod 26 not 27)
Let's use 5 as a example
5x = 1mod26
Add 26 to one until it's divisable by 5
1, 27, 53, 79, 105
105 is divisable by 5
105/5 is 21
21 is the mod inverse of 5
Even using UTFs example- 8x=1mod27
1, 28, 55, 82, 109, 136
136/8 is 17
l0lit wrote:Not a math question,
What do you guys think would be a good score on the timed question? Last year, I believe the nationals winner was sub-2 minutes, but it was a short cipher. Of course, thank goodness it is no longer weighted so heavily.
drsparc wrote:I'm having trouble finding a true 4-function calculator. Most of the simple ones also include percent and/or square root keys. Does anyone know if those are OK for this event?
drsparc wrote:I'm having trouble finding a true 4-function calculator. Most of the simple ones also include percent and/or square root keys. Does anyone know if those are OK for this event?
Longivitis wrote:drsparc wrote:I'm having trouble finding a true 4-function calculator. Most of the simple ones also include percent and/or square root keys. Does anyone know if those are OK for this event?
As long as it doesn't have trig functions you should be set.
nicholasmaurer wrote:Longivitis wrote:drsparc wrote:I'm having trouble finding a true 4-function calculator. Most of the simple ones also include percent and/or square root keys. Does anyone know if those are OK for this event?
As long as it doesn't have trig functions you should be set.
Per the Calculator Policy, square root functionality is permitted. If the calculator includes trigonometric functions, etc. it would not be allowed. Any calculator with modulus capabilities would not be permitted.
someone1580 wrote:Do you guys have any tips or tricks on any of the codes in this event? For some reason in my area, they changed Game On B to Codebusters B.
Users browsing this forum: No registered users and 0 guests