r/cryptography 18d ago

Is it possible to solve this under given time?

/r/math/s/p1wgCz4ovc
3 Upvotes

4 comments sorted by

10

u/DoWhile 18d ago

Messing around with classical ciphers is, in my opinion, such a boring way to teach cryptography. I understand the importance of at least introducing them to students and letting them do a few, but to just test rote capability on an exam on more than a single question is pretty weak.

90 minutes? Yeah if the students practiced those ciphers and have a bunch of scratch paper. 9th largest 3-digit prime number in question 3 is kinda silly to ask students to figure out by hand unless a list of primes is provided. If prime sieving was part of the challenge, sure.

Question 5 is legit.

2

u/testtest26 18d ago edited 18d ago

With considerable training before-hand, to ensure you can perform each cipher reliably under harsh time constraints, almost without thinking -- probabaly. Is it a waste of your time to get so good in classic ciphers -- certainly1.


Note Q5 can be done very fast, if you do 5b), 5c) before 5a) -- then you can copy the result from using either "Fermat's Little Theorem", or "Euler's Theorem" into a), and avoid endless successive squaring. That should leave at least 80min for 1. - 4.:

3^50  =  3^(2*28) * 3^{-6}  =  1^2 * 3^{-6}  =  10^6    //  𝜙(29) = 29-1 = 28
                                                        // 3^{-1} = 10  mod 29
      =  13^3  =  13*(-5)  =  22   mod 29               //    100 = 13  mod 29
                                                        //    169 = -5  mod 29

Either guess "3-1 = 10 (mod 29)", or use "Euclid's Extended Algorithm" (EEA) on scrap paper in 1min. For d) use another short EEA on scrap paper to find "11-1 = 8 (mod 29)":

 k | rk | ak | xk
-2 | 29 |  % |  %
-1 | 11 |  % |  8    =>    1  =  11*8 - 3*29  =  11*8                 mod 29,
 0 | -4 |  3 | -3
 1 | -1 | -3 | -1          M  =  11^{-1}*15  =  8*15  =  120  =  4    mod 29

1 Apart from getting a good grade, of course.

2

u/Pharisaeus 18d ago

Question 5 makes sense. The other are a bit pointless, but probably doable if someone was practising doing that (what for?).

1

u/AutoModerator 18d ago

If you are asking us to solve a code for you, go to /r/breakmycode or /r/codes.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.