## Codebusters C

hippo9
Member
Posts: 242
Joined: March 12th, 2018, 9:35 am
Division: C
State: IN

### Re: Codebusters C

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.
Last edited by hippo9 on October 18th, 2018, 6:04 pm, edited 1 time in total.
"If we knew what we were doing, it wouldn’t be called research." - Albert Einstein

2018: Battery Buggy, Road Scholar, Roller Coaster
2019: Chemistry Lab, Codebusters, Disease Detectives, Fossils, Geologic Mapping, Sounds of Music

Name
Member
Posts: 274
Joined: January 21st, 2018, 4:41 pm
Division: C
State: NY
Location: Syosset

### Re: Codebusters C

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.

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.
SW 16-17 Syosset 18-21. Previous main events: Microbe, Invasive, Herp, Matsci, Fermi
Hoping to do Astro, Code, Ornith, and maybe Compound next year
2018-19 highlights

megrimlockawesom
Member
Posts: 57
Joined: October 14th, 2017, 5:44 pm
Division: C
State: NC

### Re: Codebusters C

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.
Ok this is epic
Events 2018: Battery Buggy (3rd at Nats), Rollercoaster (18th at Nats), Ping Pong (1st at states)
Events 2019: Codebusters, Ping Pong Parachute, Thermodynamics

I like Overwatch, Marvel, and food

Bottom Text

UTF-8 U+6211 U+662F
Exalted Member
Posts: 1463
Joined: January 18th, 2015, 7:42 am
Division: C
State: PA

### Re: Codebusters C

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 $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.

Name
Member
Posts: 274
Joined: January 21st, 2018, 4:41 pm
Division: C
State: NY
Location: Syosset

### Re: Codebusters C

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 $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
SW 16-17 Syosset 18-21. Previous main events: Microbe, Invasive, Herp, Matsci, Fermi
Hoping to do Astro, Code, Ornith, and maybe Compound next year
2018-19 highlights

UTF-8 U+6211 U+662F
Exalted Member
Posts: 1463
Joined: January 18th, 2015, 7:42 am
Division: C
State: PA

### Re: Codebusters C

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 $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.

l0lit
Member
Posts: 16
Joined: July 30th, 2018, 12:20 pm
Division: C
State: IN

### Re: Codebusters C

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.
List of compiled Science Olympiad tests here
* Others coming soon...

mjcox2000
Member
Posts: 120
Joined: May 9th, 2014, 3:34 am
State: VA

### Re: Codebusters C

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.

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.
MIT ‘23
TJHSST ‘19
Longfellow MS
Nationals medals

drsparc
Member
Posts: 3
Joined: November 2nd, 2014, 1:17 pm
Division: C
State: CA

### Re: Codebusters C

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?

Jacobi
Exalted Member
Posts: 137
Joined: September 4th, 2018, 7:47 am
State: -

### Re: Codebusters C

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?

I know that including a sqrt key harms nothing.
I have a feeling that a percent key would be OK.

Longivitis
Member
Posts: 18
Joined: February 17th, 2018, 7:19 am
State: TX

### Re: Codebusters C

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.
UT '23

Medal Count: 8
Chemistry Lab, Codebusters, Game On, Science Word, Towers, We've Got Your Number

nicholasmaurer
Coach
Posts: 354
Joined: May 19th, 2017, 10:55 am
State: OH
Location: Solon, OH

### Re: Codebusters C

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.
Assistant Coach and Alumni ('14) - Solon High School Science Olympiad
Tournament Director - Northeast Ohio Regional Tournament

Opinions expressed on this site are not official; the only place for official rules changes and FAQs is soinc.org.

UTF-8 U+6211 U+662F
Exalted Member
Posts: 1463
Joined: January 18th, 2015, 7:42 am
Division: C
State: PA

### Re: Codebusters C

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.

(Of course it's fairly easy to calculate the modulus anyway by just dividing, subtracting the integer part, and then multiplying again, e.g. 7/3 = 2.333333; 0.333333 * 3 = 1)

someone1580
Member
Posts: 7
Joined: September 29th, 2018, 12:15 pm
Division: C
State: CA

### Codebusters C

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.

Jacobi
Exalted Member
Posts: 137
Joined: September 4th, 2018, 7:47 am
State: -

### Re: Codebusters C

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.

Too many. See the Codebusters Wiki for information.

### Who is online

Users browsing this forum: No registered users and 1 guest