Mr. Krabs has been tinkering with the restaurant thermometer to see what makes his staff the most productive. He's been tracking the data in his journal, but some "Lagrange" guy just called saying Mr. Krabs already has all the info he needs. Can you help Mr. Krabs predict how his staff will fare?
We're given a "journal" file that looks like this:
p = 137
DAY(0) = 81
DAY(1) = 67
DAY(2) = 110
DAY(3) = 116
DAY(4) = 49
DAY(5) = 111
DAY(6) = 74
DAY(7) = 53
DAY(8) = 93
DAY(9) = 83
DAY(10) = 55
DAY(11) = 122
DAY(12) = 67
DAY(13) = 47
DAY(14) = 85
DAY(15) = 91
DAY(16) = 88
DAY(17) = 84
DAY(18) = 63
DAY(19) = 96
DAY(20) = 59
DAY(21) = 87
DAY(22) = 46
DAY(23) = 99
DAY(24) = 93
DAY(25) = 126
DAY(26) = 62
DAY(27) = 65
DAY(28) = 76
DAY(29) = 55
DAY(30) = 48
DAY(31) = 116
DAY(32) = 79
DAY(33) = 106
DAY(34) = 45
DAY(35) = 54
DAY(36) = 102
DAY(37) = 100
DAY(38) = 65
DAY(39) = 93
DAY(40) = 122
DAY(41) = 84
DAY(42) = 118
DAY(43) = 64
DAY(44) = 103
DAY(45) = 76
DAY(46) = 65
DAY(47) = 109
DAY(48) = 90
DAY(49) = 99
DAY(50) = 69
DAY(51) = 50
DAY(52) = 64
DAY(53) = 61
DAY(54) = 115
DAY(55) = 111
DAY(56) = 64
DAY(57) = 80
DAY(58) = 60
DAY(59) = 68
DAY(60) = 105
DAY(61) = 113
DAY(62) = 84
DAY(63) = 119
DAY(64) = 55
DAY(65) = 77
DAY(66) = 124
DAY(67) = 55
DAY(68) = 115
DAY(69) = 21
DAY(70) = 112
DAY(71) = 41
DAY(72) = 88
DAY(73) = 136
DAY(74) = 66
DAY(75) = 43
DAY(76) = 48
DAY(77) = 55
DAY(78) = 60
DAY(79) = 41
DAY(80) = 43
DAY(81) = 103
DAY(82) = 118
DAY(83) = 19
DAY(84) = 99
DAY(85) = 34
DAY(86) = 118
DAY(87) = 73
DAY(88) = 97
DAY(89) = 74
DAY(90) = 7
DAY(91) = 78
DAY(92) = 60
DAY(93) = 48
DAY(94) = 123
DAY(95) = 125
DAY(96) = 119
DAY(97) = 0
DAY(98) = 36
DAY(99) = 123
DAY(100) = 22
----------------------------------------
DAY(101) = ???
DAY(102) = ???
DAY(103) = ???
DAY(104) = ???
DAY(105) = ???
DAY(106) = ???
DAY(107) = ???
DAY(108) = ???
DAY(109) = ???
DAY(110) = ???
DAY(111) = ???
DAY(112) = ???
DAY(113) = ???
DAY(114) = ???
DAY(115) = ???
DAY(116) = ???
DAY(117) = ???
DAY(118) = ???
DAY(119) = ???
DAY(120) = ???
DAY(121) = ???
DAY(122) = ???
DAY(123) = ???
DAY(124) = ???
DAY(125) = ???
DAY(126) = ???
DAY(127) = ???
DAY(128) = ???
DAY(129) = ???
DAY(130) = ???
DAY(131) = ???
DAY(132) = ???
Based on the challenge title, description, and file contents, it seems pretty clear that we're given 100 data points for a given polynomial function, with the task being to reconstruct this polynomial using Lagrange Interpolation.
Furthermore, the given p value at the start of the file is a hint that this polynomial over the finite field Zp (i.e. the finite field formed by the integers mod p).
First, we can parse the point data to a more copy-and-pasteable Python tuple format:
str.split('\n').map(l => {
const matches = l.match(/DAY\((\d+)\) = (\d+)/);
return `(${matches[1]}, ${matches[2]})`;
}).join(', ')(0, 81), (1, 67), (2, 110), (3, 116), (4, 49), (5, 111), (6, 74), (7, 53), (8, 93), (9, 83), (10, 55), (11, 122), (12, 67), (13, 47), (14, 85), (15, 91), (16, 88), (17, 84), (18, 63), (19, 96), (20, 59), (21, 87), (22, 46), (23, 99), (24, 93), (25, 126), (26, 62), (27, 65), (28, 76), (29, 55), (30, 48), (31, 116), (32, 79), (33, 106), (34, 45), (35, 54), (36, 102), (37, 100), (38, 65), (39, 93), (40, 122), (41, 84), (42, 118), (43, 64), (44, 103), (45, 76), (46, 65), (47, 109), (48, 90), (49, 99), (50, 69), (51, 50), (52, 64), (53, 61), (54, 115), (55, 111), (56, 64), (57, 80), (58, 60), (59, 68), (60, 105), (61, 113), (62, 84), (63, 119), (64, 55), (65, 77), (66, 124), (67, 55), (68, 115), (69, 21), (70, 112), (71, 41), (72, 88), (73, 136), (74, 66), (75, 43), (76, 48), (77, 55), (78, 60), (79, 41), (80, 43), (81, 103), (82, 118), (83, 19), (84, 99), (85, 34), (86, 118), (87, 73), (88, 97), (89, 74), (90, 7), (91, 78), (92, 60), (93, 48), (94, 123), (95, 125), (96, 119), (97, 0), (98, 36), (99, 123), (100, 22)
Then, we can use some modified Sage code from Professor Maji to reconstruct the degree-100 polynomial from our given points in Zp. We can then use this polynomial to calculate the missing points at the bottom of the journal file and reconstruct the characters of the flag.
reset()
def lagrange_interpolation(coords, p):
t = len(coords)
Zp = Integers(p)
R.<X> = Zp[]
x_tup, y_tup = zip(*coords)
polys = []
for i in [0, .., t-1]:
polys.append(1)
for j in [0, .., t-1]:
if (j == i):
polys[i] = polys[i] * y_tup[i]
else:
polys[i] = polys[i] * (X - x_tup[j]) / (x_tup[i] - x_tup[j])
PprimeX = 0
for i in [0, .., t-1]:
PprimeX = PprimeX + polys[i]
return PprimeX
coords = [(0, 81), (1, 67), (2, 110), (3, 116), (4, 49), (5, 111), (6, 74), (7, 53), (8, 93), (9, 83), (10, 55), (11, 122), (12, 67), (13, 47), (14, 85), (15, 91), (16, 88), (17, 84), (18, 63), (19, 96), (20, 59), (21, 87), (22, 46), (23, 99), (24, 93), (25, 126), (26, 62), (27, 65), (28, 76), (29, 55), (30, 48), (31, 116), (32, 79), (33, 106), (34, 45), (35, 54), (36, 102), (37, 100), (38, 65), (39, 93), (40, 122), (41, 84), (42, 118), (43, 64), (44, 103), (45, 76), (46, 65), (47, 109), (48, 90), (49, 99), (50, 69), (51, 50), (52, 64), (53, 61), (54, 115), (55, 111), (56, 64), (57, 80), (58, 60), (59, 68), (60, 105), (61, 113), (62, 84), (63, 119), (64, 55), (65, 77), (66, 124), (67, 55), (68, 115), (69, 21), (70, 112), (71, 41), (72, 88), (73, 136), (74, 66), (75, 43), (76, 48), (77, 55), (78, 60), (79, 41), (80, 43), (81, 103), (82, 118), (83, 19), (84, 99), (85, 34), (86, 118), (87, 73), (88, 97), (89, 74), (90, 7), (91, 78), (92, 60), (93, 48), (94, 123), (95, 125), (96, 119), (97, 0), (98, 36), (99, 123), (100, 22)]
f = lagrange_interpolation(coords, 137)
flag = ''
for i in [101, .. 132]:
y = f(i)
c = chr(y)
print(i, ':', y, c)
flag += c
print(flag)Running this in CoCalc, we get the flag:
101 : 85 U
102 : 77 M
103 : 65 A
104 : 83 S
105 : 83 S
106 : 123 {
107 : 49 1
108 : 110 n
109 : 116 t
110 : 51 3
111 : 114 r
112 : 112 p
113 : 114 r
114 : 51 3
115 : 116 t
116 : 95 _
117 : 110 n
118 : 48 0
119 : 114 r
120 : 95 _
121 : 49 1
122 : 110 n
123 : 116 t
124 : 51 3
125 : 114 r
126 : 112 p
127 : 48 0
128 : 108 l
129 : 64 @
130 : 116 t
131 : 51 3
132 : 125 }
UMASS{1nt3rpr3t_n0r_1nt3rp0l@t3}