> load "HPPC_code.magma"; Loading "HPPC_code.magma" => HPPC attack with n=30, d=10 [Auto dense detection: 1] ******************** FAUGERE F4 ALGORITHM ******************** Coefficient ring: GF(2) Rank: 30 Order: Graded Reverse Lexicographical (sparse monomial) Reduced exponents (solution over GF(2)) Dynamic full columns method Sparse bits: 5, max deg: 12 Matrix kind: Packed GF(2) Datum size: 0 Max pairs count: -1 Queue sort Stop at 7 linear(s) Initial length: 60 Inhomogeneous *** DENSE VARIANT *** [F4 mat test; length 60] Echelon time: 0.000 Initial echelonization rank: 30 Initial queue setup time: 0.000 Initial queue length: 186 ******* STEP 1 Basis length: 30, queue length: 186, step degree: 3, num pairs: 186 Basis mon data (KB): 0.234, average length: 0.008 60 field pair(s) 312 unsorted pair polynomial(s) 255 distinct pair polynomial(s), 0.000 4526 columns Num new polynomials: 186 (72.9%), min deg: 2 [60], av deg: 2.7 Degree counts: 2:60 3:126 New max step: 1, time: 0.004[r] Step 1 time: 0.004[r], mat/total: (IB:0.000 + RA:0.000 + E:0.000 = 0.000)/0.005[r], mem: 32.1MB, max: 144.2MB ******* STEP 2 Basis length: 216, queue length: 1214, step degree: 3, num pairs: 836 Basis mon data (KB): 1.688, average length: 0.008 120 field pair(s) 1552 unsorted pair polynomial(s) 1143 distinct pair polynomial(s), 0.000 4526 columns Num new polynomials: 596 (52.1%), min deg: 2 [60], av deg: 2.9 Degree counts: 2:60 3:536 New max step: 2, time: 0.020 Step 2 time: 0.020, mat/total: (IB:0.000 + RA:0.000 + E:0.000 = 0.000)/0.030, mem: 32.1MB, max: 144.2MB ******* STEP 3 Basis length: 812, queue length: 6098, step degree: 3, num pairs: 1380 Basis mon data (KB): 6.344, average length: 0.008 120 field pair(s) 2640 unsorted pair polynomial(s) 2144 distinct pair polynomial(s), 0.000 4526 columns Num new polynomials: 960 (44.8%), min deg: 3 [960], av deg: 3.0 Degree counts: 3:960 New max step: 3, time: 0.113[r] Step 3 time: 0.112[r], mat/total: (IB:0.000 + RA:0.000 + E:0.000 = 0.000)/0.144[r], mem: 32.1MB, max: 144.2MB ******* STEP 4 Basis length: 1772, queue length: 33500, step degree: 4, num pairs: 30105 Basis mon data (KB): 13.844, average length: 0.008 33 pairs eliminated 4833 field pair(s) 55311 unsorted pair polynomial(s) 41771 distinct pair polynomial(s), 0.000 31931 columns Num new polynomials: 30 (0.1%), min deg: 1 [29], av deg: 1.0 Degree counts: 1:29 2:1 Number of linears: 29 New max step: 4, time: 1.590[r] Step 4 time: 1.589[r], mat/total: (IB:0.000 + RA:0.000 + E:0.000 = 0.000)/1.746[r], mem: 32.1MB, max: 144.2MB STOP at 29 linears Reduce 1802 final polynomial(s) by 1802 1772 skipped and 1 divisor-redundant polynomial(s) removed; time: 0.000 Skip final dense interreduction FOR NOW Final number of polynomials: 1801 Final basis length: 29 Number of pairs: 27341, number of field pairs: 5133, total: 32474 Max step: 4, time: 1.590 Max num entries matrix: 0 by 0 Max num rows matrix: 0 by 0 Approx mat cost: 0, sym red cost: 0 Total pair setup time: 0.000 Total symbolic reduction time: 0.000 Total column sort time: 0.000 Total row sort time: 0.000 Total matrix time: 0.000 Total new polys time: 0.000 Total queue update time: 0.000 Total other time: 1.746 ****** ****** Total Faugere F4 time: 1.746[r], real time: 1.746 Found 29 linear(s); restart with extended basis [ x_1 + 1, x_2 + x_30 + 1, x_3 + 1, x_4, x_5, x_6 + 1, x_7 + 1, x_8, x_9 + x_30, x_10 + x_30, x_11 + 1, x_12 + 1, x_13, x_14, x_15 + x_30, x_16 + 1, x_17, x_18 + 1, x_19, x_20 + x_30, x_21 + 1, x_22 + x_30, x_23 + x_30 + 1, x_24 + 1, x_25 + x_30, x_26, x_27 + x_30 + 1, x_28 + 1, x_29 + x_30 + 1 ] ******************** FAUGERE F4 ALGORITHM ******************** Coefficient ring: GF(2) Rank: 30 Order: Graded Reverse Lexicographical (bit vector word) Reduced exponents (solution over GF(2)) Matrix kind: Packed GF(2) Datum size: 0 Max pairs count: -1 Queue sort Initial length: 89 Inhomogeneous Initial queue setup time: 0.000 Initial queue length: 96 ******* STEP 1 Basis length: 59, queue length: 96, step degree: 2, num pairs: 30 Basis total mons: 7060, average length: 119.661 0 field pair(s) Number of pair polynomials: 30, at 466 column(s), 0.000 Average length for reductees: 194.93 [30], reductors: 4.28 [464] Symbolic reduction time: 0.000, column sort time: 0.000 30 + 464 = 494 rows / 466 columns out of 466 (100.000%) Density: 3.4035% / 5.0904% (15.86/r), total: 7835 (0.0MB) Before ech memory: 32.1MB, max: 144.2MB Row sort time: 0.000 0.000 + 0.000 + 0.000 = 0.000 [0] After ech memory: 32.1MB, max: 144.2MB No new polynomials Queue insertion time: 0.000 New max step: 1, time: 0.000 Step 1 time: 0.000; P:0.0, S:0.0, M:0.0, Q:0.0, O:0.0, T:0.0 Mem: 32.1MB, max: 144.2MB ******* STEP 2 Basis length: 59, queue length: 66, step degree: 3, num pairs: 66 Basis total mons: 7060, average length: 119.661 66 pairs eliminated No pairs to reduce Pair elimination time: 0.000 Reduce 59 final polynomial(s) by 59 30 skipped and 0 divisor-redundant polynomial(s) removed; time: 0.000 Interreduce 29 (out of range [0 .. 58] = 59) polynomial(s) Symbolic reduction time: 0.000 Column sort time: 0.000 29 + 0 = 29 rows / 31 columns Density: 6.0067% / 17.929% (1.8621/r), total: 54 (0.0MB) Row sort time: 0.000 0.000 + 0.000 + 0.000 = 0.000 [29] Total reduction time: 0.000 Reduction time: 0.000 Final number of polynomials: 59 Final basis length: 29 Number of pairs: 30 Max step: 1, time: 0.000 Max num entries matrix: 494 by 466 Max num rows matrix: 494 by 466 Approx mat cost: 330202, sym red cost: 7889 Total pair setup time: 0.000 Total symbolic reduction time: 0.000 Total column sort time: 0.000 Total row sort time: 0.000 Total matrix time: 0.000 Total new polys time: 0.000 Total queue update time: 0.000 Total other time: 0.000 Total Faugere F4 time: 0.000, real time: 0.002 Time: 1.750