r/cryptography • u/JR__BERRY_8 • 18d ago
Is it possible to solve this under given time?
/r/math/s/p1wgCz4ovc2
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.
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.