Page 4 of 18

### Re: Codebusters C

Posted: October 18th, 2018, 4:18 pm
On the same topic, I'd assume that would be true also for any affine ciphers (although that might be harder to ensure) because they are also just monoalphabetic substitutions.

### Re: Codebusters C

Posted: October 18th, 2018, 5:06 pm
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.
Rule g only states aristocrats, patristocrats, and xenocrypts
Affine is a math based cipher, and the point of it is to know the math, not to treat it as a monoaplhabetic. There's no reason why a letter shouldn't encrypt onto itself.

### Re: Codebusters C

Posted: October 19th, 2018, 3:48 am
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.

### Re: Codebusters C

Posted: October 19th, 2018, 4:34 pm
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 $8x+27y=1$)

We proceed by using the regular Euclidean algorithm:
Divide 27 by 8.
$27 = 3(8) + 3$
Divide 8 by 3.
$8 = 1(3) + 5$
Divide 5 by 3.
$5 = 1(3) + 2$
Divide 3 by 2.
$3 = 1(2) + 1$
Now that we have a 1 at the end, we can proceed to the extended Euclidean algorithm. First, rearrange the equations.
Equation 1: $3 = 27 - 3(8)$
Equation 2: $5 = 8 - 1(3)$
Equation 3: $2 = 5 - 1(3)$
Equation 4: $1 = 3 - 1(2)$
Now.. we can substitute equation 3 into equation 4:
$1 = 3 - 1(5 - 1(3)) = 2(3) - 5$
And then equation 2:
$1 = 2(3) - (8 - 1(3)) = 3(3) - 8$
And then equation 1:
$1 = 3(27-3(8)) - 8 = 3(27) - 10(8)$
Rearrange a little...
$8(-10)+27(3)=1$
Now, we have solved the Diophantine equation.
Here's the trick: we set the equation modulus 27.
$8(-10)+27(3)\equiv1\ (\textrm{mod}\ 27)$
$8(-10)\equiv1\ (\textrm{mod}\ 27)$
$8^{-1}\equiv-10\ (\textrm{mod}\ 27)$
$8^{-1}\equiv17\ (\textrm{mod}\ 27)$
So, the multiplicative inverse of 8 mod 27 is 17.
This won't take nearly as long once you get used to it.

### Re: Codebusters C

Posted: October 19th, 2018, 8:13 pm
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 $8x+27y=1$)

We proceed by using the regular Euclidean algorithm:
Divide 27 by 8.
$27 = 3(8) + 3$
Divide 8 by 3.
$8 = 1(3) + 5$
Divide 5 by 3.
$5 = 1(3) + 2$
Divide 3 by 2.
$3 = 1(2) + 1$
Now that we have a 1 at the end, we can proceed to the extended Euclidean algorithm. First, rearrange the equations.
Equation 1: $3 = 27 - 3(8)$
Equation 2: $5 = 8 - 1(3)$
Equation 3: $2 = 5 - 1(3)$
Equation 4: $1 = 3 - 1(2)$
Now.. we can substitute equation 3 into equation 4:
$1 = 3 - 1(5 - 1(3)) = 2(3) - 5$
And then equation 2:
$1 = 2(3) - (8 - 1(3)) = 3(3) - 8$
And then equation 1:
$1 = 3(27-3(8)) - 8 = 3(27) - 10(8)$
Rearrange a little...
$8(-10)+27(3)=1$
Now, we have solved the Diophantine equation.
Here's the trick: we set the equation modulus 27.
$8(-10)+27(3)\equiv1\ (\textrm{mod}\ 27)$
$8(-10)\equiv1\ (\textrm{mod}\ 27)$
$8^{-1}\equiv-10\ (\textrm{mod}\ 27)$
$8^{-1}\equiv17\ (\textrm{mod}\ 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

### Re: Codebusters C

Posted: October 20th, 2018, 10:01 am
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 $8x+27y=1$)

We proceed by using the regular Euclidean algorithm:
Divide 27 by 8.
$27 = 3(8) + 3$
Divide 8 by 3.
$8 = 1(3) + 5$
Divide 5 by 3.
$5 = 1(3) + 2$
Divide 3 by 2.
$3 = 1(2) + 1$
Now that we have a 1 at the end, we can proceed to the extended Euclidean algorithm. First, rearrange the equations.
Equation 1: $3 = 27 - 3(8)$
Equation 2: $5 = 8 - 1(3)$
Equation 3: $2 = 5 - 1(3)$
Equation 4: $1 = 3 - 1(2)$
Now.. we can substitute equation 3 into equation 4:
$1 = 3 - 1(5 - 1(3)) = 2(3) - 5$
And then equation 2:
$1 = 2(3) - (8 - 1(3)) = 3(3) - 8$
And then equation 1:
$1 = 3(27-3(8)) - 8 = 3(27) - 10(8)$
Rearrange a little...
$8(-10)+27(3)=1$
Now, we have solved the Diophantine equation.
Here's the trick: we set the equation modulus 27.
$8(-10)+27(3)\equiv1\ (\textrm{mod}\ 27)$
$8(-10)\equiv1\ (\textrm{mod}\ 27)$
$8^{-1}\equiv-10\ (\textrm{mod}\ 27)$
$8^{-1}\equiv17\ (\textrm{mod}\ 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
That works well with relatively small numbers, but it's very tedious with larger numbers, especially with 4-function calculators. The extended Euclidean algorithm works for much larger numbers, and you can verify that you didn't make any mistakes along the way just by testing your latest equation.

### Re: Codebusters C

Posted: October 31st, 2018, 6:55 pm
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.

### Re: Codebusters C

Posted: October 31st, 2018, 8:19 pm
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.
Nationals winner here. We were at 1 minute 51 seconds.

There are pros and cons to heavier weighting for the timed question. On one hand, emphasizing solving the problem quickly means you have to have a firm grasp on what you’re doing in order to do well, so it selects strongly for the best-prepared teams. On the other hand, small mistakes that take time to fix incur huge penalties, and scores on the various test portions can be wildly out of proportion — if I’m not mistaken, my team’s time bonus was greater than the number of available points on the test by a factor of 2 to 3.

### Re: Codebusters C

Posted: November 9th, 2018, 7:15 pm
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?

### Re: Codebusters C

Posted: November 10th, 2018, 4:19 pm
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?
I know that including a sqrt key harms nothing.
I have a feeling that a percent key would be OK.