1
// SPDX-License-Identifier: UNLICENSED
2
pragma solidity ^0.8.13;
3

4
import {IPuzzle} from "./interfaces/IPuzzle.sol";
5

6
//
7
//
8
//    888b    888                        888                            888    888          d8b          888
9
//    8888b   888                        888                            888    888          Y8P          888
10
//    88888b  888                        888                            888    888                       888
11
//    888Y88b 888 888  888 88888b.d88b.  88888b.   .d88b.  888d888      8888888888  .d88b.  888 .d8888b  888888
12
//    888 Y88b888 888  888 888 "888 "88b 888 "88b d8P  Y8b 888P"        888    888 d8P  Y8b 888 88K      888
13
//    888  Y88888 888  888 888  888  888 888  888 88888888 888          888    888 88888888 888 "Y8888b. 888
14
//    888   Y8888 Y88b 888 888  888  888 888 d88P Y8b.     888          888    888 Y8b.     888      X88 Y88b.
15
//    888    Y888  "Y88888 888  888  888 88888P"   "Y8888  888          888    888  "Y8888  888  88888P'  "Y888
16
//
17
//
18
//       ||====================================================================||
19
//       ||//$\\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//$\\||
20
//       ||(100)==================| POINTS RESERVE NOTE |=================(100)||
21
//       ||\\$//        ~         '------========-------'                 \\$//||
22
//       ||<< /        /$\              // ____ \\                         \ >>||
23
//       ||>>|  12    //L\\            // ///..) \\         L38036133B   12 |<<||
24
//       ||<<|        \\ //           || <||  >\  ||                        |>>||
25
//       ||>>|         \$/            ||  $$ --/  ||      One Hundred Pts   |<<||
26
//    ||====================================================================||>||
27
//    ||//$\\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\//$\\||<||
28
//    ||(100)==================| POINTS RESERVE NOTE |=================(100)||>||
29
//    ||\\$//        ~         '------========-------'                 \\$//||\||
30
//    ||<< /        /$\              // ____ \\                         \ >>||)||
31
//    ||>>|  12    //L\\            // ///..) \\         L38036133B   12 |<<||/||
32
//    ||<<|        \\ //           || <||  >\  ||                        |>>||=||
33
//    ||>>|         \$/            ||  $$ --/  ||      One Hundred Pts   |<<||
34
//    ||<<|      L38036133B        *\\  |\_/  //* series                 |>>||
35
//    ||>>|  12                     *\\/___\_//*   1989                  |<<||
36
//    ||<<\      Treasurer    ____/Blast Franklin\_____     Secretary 12 />>||
37
//    ||//$\                  ~| FEDERATION OF POINTS |~                /$\\||
38
//    ||(100)==================   ONE HUNDRED POINTS  =================(100)||
39
//    ||\\$//\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\\$//||
40
//    ||====================================================================||
41
//
42
//
43
// @dev You are <REDACTED>, the infamous digital points thief, renowned for
44
// dozens of successful heists totaling 513,450,000,000 in stolen points.
45
//
46
// You have been hired by a mysterious benefactor to steal from a safe, your usual gig.
47
//
48
// Only this safe is not locked with a key, but with a number. 
49
// You must find a number which defies the laws of mathematics itself.
50
//
51
// This number is both a prime and composite number at the same time...
52
// 
53
// If you're able to do that, legend has it that the safe contains a treasure worth more than
54
// all your precious little points combined... a Curta Flag NFT!
55
contract NumberHeist is IPuzzle {
56

57
    bytes32 constant VALID_FACTORIALS_HASH = 0x024260b3e934c04b47e60ebbf3a5974c8008d1494ac24bfb1358daf47e752953;
58
    uint256 constant SOLUTION = 0x8fbcb4375b910093bcf636b6b2f26b26eda2a29ef5a8ee7de44b5743c3bf9a28; // Not so easy...
59

60
    modifier restoreMemory() {
61
        _;
62
        assembly {
63
            mstore(0x40, 0x80) // NooOoOOoooOooOoooOOOoooOOooOoOoooOOOoooOoOOo my memory...
64
        }
65
    }
66

67
    mapping(address => bool) public solved;
68

69
    function name() external pure returns (string memory) {
70
        return "NumberHeist";
71
    }
72

73
    function generate(address _seed) external pure returns (uint256 ret) {
74
        assembly {
75
            ret := _seed
76
        }
77
    }
78

79
    function verify(uint256 _start, uint256 _solution) external view returns (bool) {
80
        require(_solution == SOLUTION);
81
        return solved[address(uint160(_start))];
82
    }
83

84
    // The safe is locked with three layers of security against such tampering.
85
    // However, it's nothing you haven't dealt with before. 
86
    // Begin the heist!
87
    function heist(uint256 n, uint256 circleCuttingWitness, uint256 factor1, uint256 factor2) external returns (bool heistSuccess) {
88
        require(1 < n && n <= 32);
89
        require(factor1 > 1 && factor2 > 1);
90
        require(factor1 < n && factor2 < n);
91

92
        bytes memory magicTome = _initializePuzzle();
93

94
        // ---- Check Prime By Wilson's ----
95
        if (!_checkWilsons(n)) {
96
            return false;
97
        }
98

99
        // ---- Check Prime By Circle Cutting ----
100
        if (!_isPrimeByCircleCutting(magicTome, n, circleCuttingWitness)) {
101
            return false;
102
        }
103

104
        // ---- Check Not Composite By Filson's ----
105
        if (!_filsonsCompositenessCheck(n)) {
106
            return false;
107
        }
108

109
        // This number has passed 3 layers of prime security checks...
110
        // But will it defy the laws of mathematics?
111
        if(n == factor1 * factor2) {
112
            solved[msg.sender] = true;
113
            heistSuccess = true;
114
        }
115
    }
116

117

118
    //////////////////////////////////////////////////////////////////////////////////////
119
    /// WILSON'S
120
    //////////////////////////////////////////////////////////////////////////////////////
121

122
    // We will use the famous result from Wilson's Theorem to test for primality:
123
    //
124
    //  (n-1)! ≡ -1 (mod n) <=> n is prime
125
    function _checkWilsons(uint256 n) internal restoreMemory returns (bool) {
126
        // Caller provides the precomputed factorials... because why not?
127
        // Largest factorial necessary for wilson's is (n-1)!, therefore we need 0!..31!
128

129
        // Three entries: [ x! ∀ x <= 12, x! ∀ 12 < x <= 20, x! ∀ 20 < x <= 31 ]
130
        // First entry factorials fit into 4 byte denominations
131
        // Second entry factorials fit into 8 byte denominations
132
        // Third entry factorials fit into 16 byte denominations
133
        (bool success, bytes memory data) = msg.sender.call("");
134
        require(success);
135

136
        // Nothing to see here...
137
        assembly {
138
            mstore(0x40, 0x360)
139
        }
140

141
        bytes[3] memory precomputedFactorials = abi.decode(data, (bytes[3]));
142

143
        // hash the precomputedFactorials to ensure they are correct
144
        require(keccak256(abi.encodePacked(precomputedFactorials[0], precomputedFactorials[1], precomputedFactorials[2])) == VALID_FACTORIALS_HASH, "Not Valid Factorials");
145

146
        // Declare Pointers
147
        bytes memory f0 = precomputedFactorials[0];
148
        bytes memory f1 = precomputedFactorials[1];
149
        bytes memory f2 = precomputedFactorials[2];
150

151
        uint256 modResult;
152

153
        // Verify Wilson's
154
        assembly {
155
            let nMinusOneFactorial
156

157
            if lt(n, 14) {
158
                let factorialsStart := add(f0, 0x08)
159
                let factorialSpot := mload(add(factorialsStart, mul(sub(n, 1), 0x08)))
160
                nMinusOneFactorial := and(factorialSpot, 0xFFFFFFFFFFFFFFFF)
161
            }
162
            if and(gt(n, 13), lt(n, 22)) {
163
                let factorialsStart := add(f1, 0x0c)
164
                let factorialSpot := mload(add(factorialsStart, mul(sub(n, 14), 0x0c)))
165
                nMinusOneFactorial := and(factorialSpot, 0xFFFFFFFFFFFFFFFFFFFFFFFF)
166
            }
167
            if gt(n, 21) {
168
                let factorialsStart := add(f2, 0x10)
169
                let factorialSpot := mload(add(factorialsStart, mul(sub(n, 22), 0x10)))
170
                nMinusOneFactorial := and(factorialSpot, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF)
171
            }
172

173
            modResult := addmod(nMinusOneFactorial, 1, n)
174
        }
175

176
        return modResult == 0;
177
    }
178

179

180
    //////////////////////////////////////////////////////////////////////////////////////
181
    /// CIRCLE CUTTING
182
    //////////////////////////////////////////////////////////////////////////////////////
183

184
    function _initializePuzzle() internal pure returns (bytes memory magicTome) {
185
        // What could this be?
186
        assembly {
187
            magicTome := 0x760
188
            let tomePtr := add(magicTome, 0x20)
189
            let tomeSize := 0x100
190
            mstore(
191
                tomePtr,
192
                hex"0000000000000007000000000000000500000000000000150000000000000011"
193
            )
194
            mstore(
195
                add(tomePtr, 0x20),
196
                hex"0000000000000155000000000000001d00000000000015550000000000000101"
197
            )
198
            mstore(
199
                add(tomePtr, 0x40),
200
                hex"000000000000104100000000000001dd00000000001555550000000000000131"
201
            )
202
            mstore(
203
                add(tomePtr, 0x60),
204
                hex"00000000015555550000000000001ddd000000000001c74d0000000000010001"
205
            )
206
            mstore(
207
                add(tomePtr, 0x80),
208
                hex"000000015555555500000000000010c100000015555555550000000000013131"
209
            )
210
            mstore(
211
                add(tomePtr, 0xA0),
212
                hex"0000000001C7134D00000000001DDDDD00001555555555550000000000010301"
213
            )
214
            mstore(
215
                add(tomePtr, 0xC0),
216
                hex"00000100401004010000000001DDDDDD00000010000400010000000001313131"
217
            )
218
            mstore(
219
                add(tomePtr, 0xE0),
220
                hex"01555555555555550000000000014FC515555555555555550000000000000000"
221
            )
222
            mstore(magicTome, tomeSize)
223
        }
224
    }
225

226
    // cyclo-
227
    // ˈsīklō - Greek
228
    //      1. circular
229
    //      2. relating to a circle
230
    //
231
    // tomic
232
    // ˈtɑmɪk - Greek
233
    //      1. of or relating to cutting, division, sections, etc.
234
    //
235
    // Let Φ𝑛 be the nth cyclotomic polynomial, then we propose ∃ 𝑎 s.t.:
236
    //
237
    //      𝑝 is prime <=> Φ𝑝−1(𝑎) ≡ 0 (mod 𝑝)
238
    //
239
    // Can this be true...?
240
    function _isPrimeByCircleCutting(bytes memory cyclotomics, uint256 n, uint256 witness) internal returns (bool) {
241
        if (cyclotomics.length != 0x100) {
242
            revert("Invalid cyclotomics length");
243
        }
244
        // Get the right cyclotomic from the magic tome
245
        bytes8 cyclotomic = _readCyclotomic(cyclotomics, n-1);
246
        int256 result = _evaluateCyclotomic(cyclotomic, witness);
247

248
        return result % int256(n) == 0;
249
    }
250

251
    function _readCyclotomic(bytes memory cyclotomics, uint256 n) internal pure returns (bytes8 cyclotomic) {
252
        assembly {
253
            let cyclo_size := 0x08
254
            cyclotomic := and(mload(add(add(cyclotomics, 0x20), mul(sub(n, 1), cyclo_size))), 0xFFFFFFFFFFFFFFFF000000000000000000000000000000000000000000000000)
255
        }
256
    }
257

258
    function _evaluateCyclotomic(bytes8 cyclotomic, uint256 x) internal returns (int256 res) {
259
        for (uint256 i = 63; i > 1; i-=2) {
260
            uint8 cycloByte = uint8(cyclotomic[i / 8]);
261

262
            uint adjustment = (7 - (i % 8));
263

264
            uint8 sign = uint8(cycloByte & (1 << (adjustment + 1)));
265
            uint8 bit = uint8(cycloByte & (1 << adjustment));
266

267
            if (bit != 0) {
268
                int256 val = int256(x**((63-i)/2));
269
                if (sign != 0) {
270
                    res -= val;
271
                } else if (sign == 0){
272
                    res += val;
273
                } else {
274
                    revert("Invalid sign");
275
                }
276
            }
277
        }
278
    }
279

280

281
    //////////////////////////////////////////////////////////////////////////////////////
282
    /// FILSON'S
283
    //////////////////////////////////////////////////////////////////////////////////////
284

285
    // As a corollary to Wilson's we derive Filson's:
286
    //
287
    //  (n-1)! ≡ 0 (mod n) <=> n is composite
288
    //
289
    // This interesting result is based on the following observation when n is composite:
290
    //
291
    //  ∃ x0, x1 ∈ {1,2,..n-1} s.t. x0 * x1 = a * n for some a ∈ Zn+
292
    //
293
    // Proving this is left as an exercise for the reader...
294
    function _filsonsCompositenessCheck(uint256 n) internal pure returns (bool) {
295
        return factorial(n-1) % n != 0;
296
    }
297

298
    // Use an independent method to compute factorials for Filson's,
299
    // just in case the pre-computed method is vulnerable ;)
300
    function factorial(uint n) public pure returns (uint) {
301
        if (n == 0) {
302
            return 1;
303
        }
304
        uint result = 1;
305
        for (uint i = 1; i <= n; i++) {
306
            result *= i;
307
        }
308
        return result;
309
    }
310

311
}