/* Magma output for J. Patarin's HFE Challenge 1 (80 equations in 80 variables over GF(2). Run on a 750MHz Sunfire v880 (using 14.4GB of memory) in 22.1 hours. Solved by Allan Steel, August, October 2004. (First solved by Jean-Charles Faugere in May 2002.) */ Magma V2.11-9 Thu Oct 21 2004 14:08:47 on verne [Seed = 1] Type ? for help. Type -D to quit. > time Groebner(I: HFE); ******************** FAUGERE F4 ALGORITHM ******************** Coefficient ring: GF(2) Rank: 80 Order: Graded Reverse Lexicographical (sparse monomial) Reduced exponents (solution over GF(2)) Dynamic method Initial length: 160 Inhomogeneous Matrix kind: Packed GF(2) Datum size: 0 No rewrite rules ******* STEP 1 Basis length: 80, queue length: 244, step degree: 2, num pairs: 73 Basis mon data (KB): 32.453, average length: 0.406 0 field pair(s) 146 unsorted pair polynomial(s) 79 distinct pair polynomial(s), 0.000 1666981 columns Before ech memory: 45.0MB Base buf nrows: 512 Buf words: 8, max_reds_base: 256, width[pos]: 8, ratio: 3.125 At: 79, 0 reduced, 0 reductors, 0.000, memory: 287.2MB 1.150 + 0.019 + 0.009 = 2.960 [73] Num reductees: 73, reductors: 7, num total rows: 80 After ech memory: 273.9MB Queue insertion time: 0.010 Number of linears: 0 Step 1 time: 2.970, [2.968], mat/total: 2.960/3.050 [3.042], mem: 273.9MB ******* STEP 2 Basis length: 153, queue length: 903, step degree: 3, num pairs: 903 Basis mon data (KB): 61.445, average length: 0.402 160 field pair(s) 1354 unsorted pair polynomial(s) 1083 distinct pair polynomial(s), 0.049 1666981 columns Before ech memory: 273.9MB Base buf nrows: 512 Buf words: 8, max_reds_base: 256, width[pos]: 8, ratio: 3.125 At: 1083, 0 reduced, 0 reductors, 0.000, memory: 287.2MB At: 367, 512 reduced, 5608 reductors, 7.840, memory: 320.5MB 12.150 + 0.019 + 4.179 = 17.399 [757] Num reductees: 764, reductors: 5723, num total rows: 6487 After ech memory: 309.3MB Queue insertion time: 0.670 Number of linears: 0 Step 2 time: 18.119, [18.125], mat/total: 20.360/21.170 [21.167], mem: 309.3MB ******* STEP 3 Basis length: 910, queue length: 15773, step degree: 4, num pairs: 15773 Basis mon data (KB): 7785.977, average length: 8.556 2271 field pair(s) 29275 unsorted pair polynomial(s) 22019 distinct pair polynomial(s), 18.980 1666981 columns Before ech memory: 309.3MB Base buf nrows: 512 Buf words: 8, max_reds_base: 256, width[pos]: 8, ratio: 3.125 At: 22019, 0 reduced, 0 reductors, 0.000, memory: 324.4MB At: 21369, 512 reduced, 25721 reductors, 546.009, memory: 2025.6MB At: 20719, 1024 reduced, 36053 reductors, 990.390, memory: 2790.4MB At: 20136, 1536 reduced, 222182 reductors, 1842.750, memory: 4969.0MB At: 19594, 2048 reduced, 222455 reductors, 2277.909, memory: 5078.5MB At: 19032, 2560 reduced, 222505 reductors, 2735.090, memory: 5189.2MB At: 18390, 3072 reduced, 222635 reductors, 3212.150, memory: 5317.8MB At: 17640, 3584 reduced, 222873 reductors, 3712.320, memory: 5470.5MB At: 16914, 4096 reduced, 223087 reductors, 4237.140, memory: 5617.8MB At: 16204, 4608 reduced, 223285 reductors, 4783.930, memory: 5761.5MB At: 15481, 5120 reduced, 223496 reductors, 5353.590, memory: 5908.0MB At: 14760, 5632 reduced, 223705 reductors, 5945.590, memory: 6054.1MB At: 14030, 6144 reduced, 223923 reductors, 6561.430, memory: 6202.2MB At: 13277, 6656 reduced, 224164 reductors, 7201.560, memory: 6355.3MB At: 12547, 7168 reduced, 224382 reductors, 7867.380, memory: 6503.3MB At: 11827, 7680 reduced, 224590 reductors, 8552.929, memory: 6649.0MB At: 11118, 8192 reduced, 224787 reductors, 9220.119, memory: 6767.1MB At: 10382, 8704 reduced, 225011 reductors, 9772.949, memory: 6817.5MB At: 9604, 9216 reduced, 225277 reductors, 10330.309, memory: 6877.0MB At: 8894, 9728 reduced, 225475 reductors, 10882.709, memory: 6921.5MB At: 8177, 10240 reduced, 225680 reductors, 11436.299, memory: 6967.4MB At: 7441, 10752 reduced, 225904 reductors, 11989.459, memory: 7017.7MB At: 6671, 11264 reduced, 226162 reductors, 12548.459, memory: 7075.5MB At: 5955, 11776 reduced, 226366 reductors, 13103.879, memory: 7121.3MB At: 5220, 12288 reduced, 226589 reductors, 13658.599, memory: 7171.3MB At: 4448, 12800 reduced, 226849 reductors, 14215.929, memory: 7229.6MB At: 3717, 13312 reduced, 227068 reductors, 14770.559, memory: 7278.7MB At: 2965, 13824 reduced, 227308 reductors, 15326.359, memory: 7332.5MB At: 2212, 14336 reduced, 227549 reductors, 15887.229, memory: 7386.6MB At: 1442, 14848 reduced, 227807 reductors, 16448.759, memory: 7444.4MB At: 665, 15360 reduced, 228072 reductors, 17009.180, memory: 7503.7MB 17572.869 + 0.060 + 0.000 = 17573.990 [8214] [Skip pass 2] Num reductees: 15773, reductors: 228324, num total rows: 244097 After ech memory: 7210.0MB Queue insertion time: 127.479 Number of linears: 0 Step 3 time: 17720.450, [17752.416], mat/total: 17594.350/17741.619 [17773.583], mem: 7210.0MB ******* STEP 4 Basis length: 9124, queue length: 37496, step degree: 4, num pairs: 5280 Basis mon data (KB): 1528007.688, average length: 167.471 480 field pair(s) 10080 unsorted pair polynomial(s) 8483 distinct pair polynomial(s), 3.880 1666981 columns Before ech memory: 7210.0MB Base buf nrows: 512 Buf words: 8, max_reds_base: 256, width[pos]: 8, ratio: 3.125 At: 8483, 0 reduced, 0 reductors, 0.000, memory: 7560.2MB At: 7459, 512 reduced, 12881 reductors, 1279.840, memory: 7560.2MB At: 6435, 1024 reduced, 15234 reductors, 2084.409, memory: 7560.2MB At: 5534, 1536 reduced, 19640 reductors, 2770.360, memory: 7560.2MB At: 4686, 2048 reduced, 57944 reductors, 3693.860, memory: 7560.2MB At: 3977, 2560 reduced, 236956 reductors, 4752.470, memory: 8593.7MB At: 3243, 3072 reduced, 237178 reductors, 5535.319, memory: 8741.3MB At: 2506, 3584 reduced, 237403 reductors, 6341.849, memory: 8889.6MB At: 1768, 4096 reduced, 237629 reductors, 7173.080, memory: 9038.1MB At: 1031, 4608 reduced, 237854 reductors, 8025.889, memory: 9186.4MB At: 266, 5120 reduced, 238107 reductors, 8762.400, memory: 9254.3MB 9468.209 + 0.049 + 0.000 = 9469.339 [5280] [Skip pass 2] Num reductees: 5280, reductors: 238213, num total rows: 243493 After ech memory: 8849.8MB Queue insertion time: 284.820 Number of linears: 0 Step 4 time: 9758.040, [9777.694], mat/total: 27063.690/27499.659 [27551.277], mem: 8849.8MB ******* STEP 5 Basis length: 14404, queue length: 72536, step degree: 4, num pairs: 21760 Basis mon data (KB): 2398039.305, average length: 166.484 1920 field pair(s) 41600 unsorted pair polynomial(s) 32503 distinct pair polynomial(s), 15.769 1666981 columns Before ech memory: 8849.8MB Base buf nrows: 512 Buf words: 8, max_reds_base: 256, width[pos]: 8, ratio: 3.125 At: 32503, 0 reduced, 0 reductors, 0.000, memory: 9279.7MB At: 31479, 512 reduced, 32512 reductors, 1294.469, memory: 9279.7MB At: 30455, 1024 reduced, 34624 reductors, 2003.639, memory: 9279.7MB At: 29431, 1536 reduced, 44191 reductors, 2847.529, memory: 9279.7MB At: 28407, 2048 reduced, 45723 reductors, 3678.500, memory: 9279.7MB At: 27383, 2560 reduced, 46235 reductors, 4447.199, memory: 9279.7MB At: 26359, 3072 reduced, 47441 reductors, 5329.379, memory: 9279.7MB At: 25370, 3584 reduced, 48314 reductors, 6217.080, memory: 9279.7MB At: 24360, 4096 reduced, 48972 reductors, 7118.720, memory: 9279.7MB At: 23623, 4608 reduced, 49197 reductors, 7955.569, memory: 9279.7MB At: 22759, 5120 reduced, 79247 reductors, 9088.509, memory: 9329.1MB At: 21994, 5632 reduced, 265661 reductors, 10441.930, memory: 11599.9MB At: 21263, 6144 reduced, 265880 reductors, 11490.479, memory: 11743.2MB At: 20678, 6656 reduced, 265953 reductors, 12564.930, memory: 11854.1MB At: 20001, 7168 reduced, 266118 reductors, 13667.360, memory: 11985.6MB At: 19399, 7680 reduced, 266208 reductors, 14788.959, memory: 12100.0MB At: 18715, 8192 reduced, 266380 reductors, 15926.069, memory: 12232.9MB At: 18041, 8704 reduced, 266542 reductors, 17071.909, memory: 12363.5MB At: 17347, 9216 reduced, 266724 reductors, 18237.979, memory: 12498.5MB At: 16657, 9728 reduced, 266902 reductors, 19426.769, memory: 12632.7MB At: 15969, 10240 reduced, 267078 reductors, 20641.279, memory: 12766.4MB At: 15370, 10752 reduced, 267165 reductors, 21876.979, memory: 12880.1MB At: 14794, 11264 reduced, 267229 reductors, 23114.029, memory: 12988.8MB At: 14134, 11776 reduced, 267377 reductors, 24369.509, memory: 13116.1MB At: 13403, 12288 reduced, 267596 reductors, 25648.639, memory: 13259.3MB At: 12683, 12800 reduced, 267804 reductors, 26949.519, memory: 13400.0MB At: 11933, 13312 reduced, 268042 reductors, 28270.049, memory: 13547.3MB At: 11231, 13824 reduced, 268232 reductors, 29637.659, memory: 13683.6MB At: 10545, 14336 reduced, 268406 reductors, 31019.430, memory: 13816.6MB At: 9857, 14848 reduced, 268582 reductors, 32406.220, memory: 13949.8MB At: 9147, 15360 reduced, 268780 reductors, 33817.379, memory: 14088.0MB At: 8438, 15872 reduced, 268977 reductors, 35251.389, memory: 14225.9MB At: 7729, 16384 reduced, 269174 reductors, 36705.529, memory: 14363.9MB At: 7019, 16896 reduced, 269372 reductors, 38183.029, memory: 14502.0MB At: 6301, 17408 reduced, 269578 reductors, 39679.330, memory: 14641.9MB At: 5574, 17920 reduced, 269793 reductors, 41104.949, memory: 14728.4MB At: 4831, 18432 reduced, 270024 reductors, 42474.250, memory: 14785.4MB At: 4087, 18944 reduced, 270256 reductors, 43849.669, memory: 14842.3MB At: 3359, 19456 reduced, 270472 reductors, 45221.880, memory: 14895.6MB At: 2631, 19968 reduced, 270688 reductors, 46595.940, memory: 14947.1MB At: 1903, 20480 reduced, 270904 reductors, 47964.069, memory: 14995.7MB At: 1158, 20992 reduced, 271137 reductors, 49339.869, memory: 15047.9MB At: 399, 21504 reduced, 271384 reductors, 50717.830, memory: 15103.0MB Linear found 52097.270 + 0.059 + 0.000 = 52098.400 [75] [Skip pass 2] Num reductees: 21760, reductors: 271527, num total rows: 293287 After ech memory: 14433.9MB Row 0 is linear Queue insertion time: 9.229 Number of linears: 75 Step 5 time: 52123.399, [52236.350], mat/total: 79162.090/79623.059 [79787.627], mem: 14433.9MB STOP at 75 linears Reduce 14479 final polynomial(s) by 14479 14404 redundant polynomial(s) removed; time: 4.520 Final number of polynomials: 75 Number of pairs: 38812 Total pair setup time: 38.680 Total symbolic reduction time: 0.000 Total column sort time: 0.000 Total row sort time: 0.000 Total matrix time: 79162.090 Total new polys time: 0.080 Total queue update time: 422.130 Total Faugere F4 time: 79627.669, real time: 79792.229 Found 75 linear(s); restart with extended basis ******************** FAUGERE F4 ALGORITHM ******************** Coefficient ring: GF(2) Rank: 80 Order: Graded Reverse Lexicographical (bit vector) Reduced exponents (solution over GF(2)) Initial length: 235 Inhomogeneous Matrix kind: Packed GF(2) Datum size: 0 No rewrite rules ******* STEP 1 Basis length: 155, queue length: 251, step degree: 2, num pairs: 80 Basis total mons: 130212, average length: 840.077 0 field pair(s) Number of pair polynomials: 80, at 3241 column(s), 1.039 Average length for reductees: 1482.55 [80], reductors: 7.59 [3225] Symbolic reduction time: 0.090, column sort time: 0.009 80 + 3225 = 3305 rows / 3241 columns, 1.3357% / 1.9669% (43.291/r) Before ech memory: 14433.9MB Row sort time: 0.009 0.029 + 0.000 + 0.000 = 0.029 [12] After ech memory: 14433.9MB Queue insertion time: 0.010 Step 1 time: 1.190, [1.183], mat/total: 0.040/1.250 [1.242], mem: 14433.9MB ******* STEP 2 Basis length: 167, queue length: 215, step degree: 2, num pairs: 7 Basis total mons: 130237, average length: 779.862 0 field pair(s) Number of pair polynomials: 7, at 13 column(s), 0.000 Average length for reductees: 3.43 [7], reductors: 1.80 [10] Symbolic reduction time: 0.000, column sort time: 0.000 7 + 10 = 17 rows / 13 columns, 19.005% / 32.656% (2.4706/r) Before ech memory: 14433.9MB Row sort time: 0.000 0.000 + 0.000 + 0.000 = 0.000 [0] After ech memory: 14433.9MB Queue insertion time: 0.000 Step 2 time: 0.000, [0.001], mat/total: 0.040/1.250 [1.243], mem: 14433.9MB ******* STEP 3 Basis length: 167, queue length: 208, step degree: 3, num pairs: 208 Basis total mons: 130237, average length: 779.862 6 field pair(s) Number of pair polynomials: 20, at 20 column(s), 0.000 Average length for reductees: 2.15 [20], reductors: 1.56 [18] Symbolic reduction time: 0.000, column sort time: 0.000 20 + 18 = 38 rows / 20 columns, 9.3421% / 19.632% (1.8684/r) Before ech memory: 14433.9MB Row sort time: 0.000 0.000 + 0.000 + 0.000 = 0.000 [0] After ech memory: 14433.9MB Queue insertion time: 0.000 Step 3 time: 0.000, [0.001], mat/total: 0.040/1.250 [1.244], mem: 14433.9MB Reduce 167 final polynomial(s) by 167 87 redundant polynomial(s) removed; time: 0.000 Interreduce 80 (out of 167) polynomial(s) Symbolic reduction time: 0.000 80 + 0 = 80 rows / 84 columns, 4.6577% / 14.319% (3.9125/r) Row sort time: 0.000 0.000 + 0.000 + 0.000 = 0.000 [80] Interreduction time: 0.000 Final number of polynomials: 80 Number of pairs: 104, number of field pairs: 6, total: 110 Total pair setup time: 1.040 Total symbolic reduction time: 0.090 Total column sort time: 0.010 Total row sort time: 0.010 Total matrix time: 0.040 Total new polys time: 0.010 Total queue update time: 0.000 Total Faugere F4 time: 1.279, real time: 1.277 Time: 79630.090 > I; Ideal of Polynomial ring of rank 80 over GF(2) Graded Reverse Lexicographical Order Variables: x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23, x24, x25, x26, x27, x28, x29, x30, x31, x32, x33, x34, x35, x36, x37, x38, x39, x40, x41, x42, x43, x44, x45, x46, x47, x48, x49, x50, x51, x52, x53, x54, x55, x56, x57, x58, x59, x60, x61, x62, x63, x64, x65, x66, x67, x68, x69, x70, x71, x72, x73, x74, x75, x76, x77, x78, x79, x80 Dimension 0 Groebner basis: [ x74^2 + x74, x74*x77 + x74, x77^2 + x77, x74*x79 + x74, x77*x79 + x77, x79^2 + x79, x1, x2 + 1, x3 + 1, x4 + x74 + x77 + 1, x5 + x79 + 1, x6 + x79, x7 + x74 + x77 + x79 + 1, x8 + x77 + 1, x9 + x74 + 1, x10 + x79 + 1, x11 + x74 + x79 + 1, x12 + x74 + x79 + 1, x13 + 1, x14 + x74 + x77, x15 + x77 + x79 + 1, x16 + x74 + x77, x17 + x77 + x79 + 1, x18 + x74 + x79, x19 + x77 + x79, x20 + x77 + x79 + 1, x21 + x77 + x79, x22 + x77 + x79 + 1, x23 + x74 + x77 + x79 + 1, x24 + x77 + x79 + 1, x25 + x74 + x77 + x79, x26 + x74 + 1, x27 + x74 + x77 + x79 + 1, x28 + x79 + 1, x29 + x74 + x79 + 1, x30 + x74, x31 + x74, x32 + 1, x33 + x79 + 1, x34 + x77, x35 + x74 + x77 + x79, x36 + x77, x37 + x74 + x77 + x79 + 1, x38 + x74 + x77 + x79, x39 + x74 + 1, x40 + x74 + x77 + x79 + 1, x41 + x77 + 1, x42 + x77, x43 + x74 + 1, x44, x45 + x74 + 1, x46 + x77 + x79 + 1, x47 + x74, x48 + x77 + 1, x49 + x74 + x77 + x79, x50 + 1, x51 + x74 + 1, x52 + 1, x53 + x74 + x77 + x79, x54 + x74, x55 + x77, x56 + x79 + 1, x57 + x74, x58, x59 + x79 + 1, x60 + x74 + x77 + x79 + 1, x61 + x74 + x79, x62 + x79, x63 + x79, x64 + x77 + 1, x65 + x74 + x77, x66 + x79, x67 + x74 + x77, x68 + x79, x69 + x74 + x77 + 1, x70 + x79 + 1, x71 + x77 + 1, x72 + x79, x73 + x74 + x77 + x79, x75 + x77 + x79, x76 + x77 + x79 + 1, x78, x80 + 1 ] > time VarietySequence(I); [ [ 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1 ], [ 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1 ], [ 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1 ], [ 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1 ] ] Time: 0.010 > #$1; 4 Total time: 79672.400 seconds, Total memory usage: 14433.89MB