Codebusters C
-
- Member
- Posts: 271
- Joined: March 12th, 2018, 9:35 am
- Division: C
- State: IN
- Has thanked: 1 time
- Been thanked: 6 times
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.
2018: Battery Buggy, Road Scholar, Roller Coaster
2019: Chem Lab, Code, Disease, Fossils, Geo Maps, Sounds
2020 and 2021: Astro, Chem Lab, Code, Fossils, Geo Maps, Sounds
When you miss nats twice by a combined two points
2019: Chem Lab, Code, Disease, Fossils, Geo Maps, Sounds
2020 and 2021: Astro, Chem Lab, Code, Fossils, Geo Maps, Sounds
When you miss nats twice by a combined two points
- Name
- Member
- Posts: 434
- Joined: January 21st, 2018, 4:41 pm
- Division: C
- State: NY
- Pronouns: He/Him/His
- Has thanked: 49 times
- Been thanked: 46 times
Re: Codebusters C
Rule g only states aristocrats, patristocrats, and xenocryptshippo9 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.
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.
South Woods MS, Syosset HS '21
BirdSO TD/ES
Past Events: Microbe, Invasive, Matsci, Fermi, Astro, Code, Fossils
BirdSO TD/ES
Past Events: Microbe, Invasive, Matsci, Fermi, Astro, Code, Fossils
1st place MIT Codebusters 2019-2020 1st place NYS Fermi Questions (2019), Astronomy and Codebusters (2021) Science Olympiad Founder's Scholarship winner
- megrimlockawesom
- Member
- Posts: 94
- Joined: October 14th, 2017, 5:44 pm
- Division: C
- State: NC
- Has thanked: 0
- Been thanked: 2 times
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 (2nd at Regionals OVERALL), Thermodynamics
Events 2020: Sounds of Music, Designer Genes, Ping Pong Parachute
Events 2018: Battery Buggy (3rd at Nats), Rollercoaster (18th at Nats), Ping Pong (1st at states)
Events 2019: Codebusters, Ping Pong Parachute (2nd at Regionals OVERALL), Thermodynamics
Events 2020: Sounds of Music, Designer Genes, Ping Pong Parachute
-
- Exalted Member
- Posts: 1597
- Joined: January 18th, 2015, 7:42 am
- Division: C
- State: PA
- Has thanked: 6 times
- Been thanked: 15 times
Re: Codebusters C
Sure!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.
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
- Member
- Posts: 434
- Joined: January 21st, 2018, 4:41 pm
- Division: C
- State: NY
- Pronouns: He/Him/His
- Has thanked: 49 times
- Been thanked: 46 times
Re: Codebusters C
UTF-8 U+6211 U+662F wrote:Sure!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.
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
South Woods MS, Syosset HS '21
BirdSO TD/ES
Past Events: Microbe, Invasive, Matsci, Fermi, Astro, Code, Fossils
BirdSO TD/ES
Past Events: Microbe, Invasive, Matsci, Fermi, Astro, Code, Fossils
1st place MIT Codebusters 2019-2020 1st place NYS Fermi Questions (2019), Astronomy and Codebusters (2021) Science Olympiad Founder's Scholarship winner
-
- Exalted Member
- Posts: 1597
- Joined: January 18th, 2015, 7:42 am
- Division: C
- State: PA
- Has thanked: 6 times
- Been thanked: 15 times
Re: Codebusters C
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.Name wrote:UTF-8 U+6211 U+662F wrote:Sure!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.
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
For more information about the extended Euclidean algorithm, see http://www-math.ucdenver.edu/~wcherowi/ ... ucalg.html
- l0lit
- Member
- Posts: 48
- Joined: July 30th, 2018, 12:20 pm
- Division: C
- State: FL
- Has thanked: 0
- Been thanked: 12 times
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.
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.
Any opinions stated on this site are not official, the only official information can be found at soinc.org
University of South Florida '25
Carmel SciOly Alumni, Captain 2019-21
Tests written
University of South Florida '25
Carmel SciOly Alumni, Captain 2019-21
Tests written
-
- Member
- Posts: 121
- Joined: May 9th, 2014, 3:34 am
- Division: Grad
- State: VA
- Has thanked: 0
- Been thanked: 0
Re: Codebusters C
Nationals winner here. We were at 1 minute 51 seconds.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.
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
See my user page for nationals medals and event supervising experience.
TJHSST ‘19
Longfellow MS
See my user page for nationals medals and event supervising experience.
- drsparc
- Member
- Posts: 5
- Joined: November 2nd, 2014, 1:17 pm
- Division: C
- State: CA
- Has thanked: 1 time
- Been thanked: 0
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?
-
- Exalted Member
- Posts: 137
- Joined: September 4th, 2018, 7:47 am
- Has thanked: 0
- Been thanked: 0
Re: Codebusters C
I know that including a sqrt key harms nothing.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 have a feeling that a percent key would be OK.
Who is online
Users browsing this forum: No registered users and 1 guest